More Web Proxy on the site http://driver.im/

Article

Free access

Comparing two grammar-based generation algorithms: a case study

Authors:

Miroslav Martinovic,

Tomek StrzalkowskiAuthors Info & Claims

ACL '92: Proceedings of the 30th annual meeting on Association for Computational Linguistics

Pages 81 - 88

https://doi.org/10.3115/981967.981978

Published: 28 June 1992 Publication History

Abstract

In this paper we compare two grammar-based generation algorithms: the Semantic-Head-Driven Generation Algorithm (SHDGA), and the Essential Arguments Algorithm (EAA). Both algorithms have successfully addressed several outstanding problems in grammar-based generation, including dealing with non-monotonic compositionality of representation, left-recursion, deadlock-prone rules, and nondeterminism. We concentrate here on the comparison of selected properties: generality, efficiency, and determinism. We show that EAA's traversals of the analysis tree for a given language construct, include also the one taken on by SHDGA. We also demonstrate specific and common situations in which SHDGA will invariably run into serious inefficiency and nondeterminism, and which EAA will handle in an efficient and deterministic manner. We also point out that only EAA allows to treat the underlying grammar in a truly multi-directional manner.

References

[1]

{C78} COLMERAUER, A. 1978. "Metamorphosis Grammars." In Natural Language Communication with Computers, Edited by L. Bolc. Lecture Notes in Computer Science, 63. Springer-Verlag, New York, NY, pp. 133--189.

Digital Library

[2]

{D90a} DYMETMAN, M. 1990. "A Generalized Greibach Normal Form for DCG's." CCRIT, Laval, Quebec: Ministere des Communications Canada.

[3]

{D90b} DYMETMAN, M. 1990. "Left-Recursion Elimination, Guiding, and Bidirectionality in Lexical Grammars." To Appear.

[4]

{DA84} DAHL, V., and ABRAMSON, H. 1984. "On Gapping Grammars." Proceedings of the Second International Conference on Logic Programming. Uppsala, Sweden, pp. 77--88.

[5]

{DI88} DYMETMAN, M., and ISABELLE, P. 1988. "Reversible Logic Grammars for Machine Translation." Proceedings of the 2nd International Conference on Theoretical and Methodological Issues in Machine Translation of Natural Languages. Carnegie-Mellon University, Pittsburgh, PA.

[6]

{DIP90} DYMETMAN, M., ISABELLE, P., and PERRAULT, F. 1991. "A Symmetrical Approach to Parsing and Generation." Proceedings of the 13th International Conference on Computational Linguistics (COLING-90). Helsinki, Finland, Vol. 3., pp. 90--96.

Digital Library

[7]

{GM89} GAZDAR, G., and MELLISH, C. 1989. Natural Language Processing in Prolog. Addison-Wesley, Reading, MA.

[8]

{K90} KAY, M. 1990. "Head-Driven Parsing." In M. Tomita (ed.), Current Issues in Parsing Technology, Kluwer Academic Publishers, Dordrecht, the Netherlands.

[9]

{K84} KAY, M. 1984. "Functional Unification Grammar: A Formalism for Machine Translation." Proceedings of the 10th International Conference on Computational Linguistics (COLING-84). Stanford University, Stanford, CA., pp. 75--78.

Digital Library

[10]

{N89} VAN NOORD, G. 1989. "An Overview of Head-Driven Bottom-Up Generation." In Proceedings of the Second European Workshop on Natural Language Generation. Edinburgh, Scotland.

[11]

{PS90} PENG, P., and STRZALKOWSKI, T. 1990. "An Implementation of A Reversible Grammar." Proceedings of the 8th Conference of the Canadian Society for the Computational Studies of Intelligence (CSCSI-90). University of Ottawa, Ottawa, Ontario, pp. 121--127.

Digital Library

[12]

{S90a} STRZALKOWSKI, T. 1990. "How to Invert A Natural Language Parser into An Efficient Generator: An Algorithm for Logic Grammars." Proceedings of the 13th International Conference on Computational Linguistics (COLING-90). Helsinki, Finland, Vol. 2., pp. 90--96.

Digital Library

[13]

{S90b} STRZALKOWSKI, T. 1990. "Reversible Logic Grammars for Natural Language Parsing and Generation." Computational Intelligence Journal, Volume 6., pp. 145--171.

[14]

{S91} STRZALKOWSKI, T. 1991. "A General Computational Method for Grammar Inversion." Proceedings of a Workshop Sponsored by the Special Interest Groups on Generation and Parsing of the ACL. Berkeley, CA., pp. 91--99.

[15]

{SNMP89} SHIEBER, S. M., VAN NOORD, G., MOORE, R. C., and PEREIRA, F. C. N. 1989. "A Semantic-Head-Driven Generation Algorithm for Unification-Based Formalisms." Proceedings of the 27th Meeting of the ACL. Vancouver, B.C., pp. 7--17.

Digital Library

[16]

{SNMP90} SHIEBER, S. M., VAN NOORD, G., MOORE, R. C., and PEREIRA, F. C. N. 1990. "Semantic-Head-Driven Generation." Computational Linguistics, Volume 16, Number 1.

Digital Library

[17]

{W88} WEDEKIND, J. 1988. "Generation as Structure Driven Derivation." Proceedings of the 12th International Conference on Computational Linguistics (COLING-88). Budapest, Hungary, pp. 732--737.

Digital Library

Cited By

Minnen GGerdemann DGötz TAbney SHinrichs E(1995)Off-line optimization for Earley-style HPSG processingProceedings of the seventh conference on European chapter of the Association for Computational Linguistics10.3115/976973.976998(173-179)Online publication date: 27-Mar-1995
https://dl.acm.org/doi/10.3115/976973.976998
Martinovié MNagao MWilks Y(1994)Universal guides and finiteness and symmetry of grammar processing algorithmsProceedings of the 15th conference on Computational linguistics - Volume 210.3115/991250.991296(916-921)Online publication date: 5-Aug-1994
https://dl.acm.org/doi/10.3115/991250.991296
Takeda KPustejovsky J(1994)Tricolor DAGs for machine translationProceedings of the 32nd annual meeting on Association for Computational Linguistics10.3115/981732.981763(226-233)Online publication date: 27-Jun-1994
https://dl.acm.org/doi/10.3115/981732.981763

Comparing two grammar-based generation algorithms: a case study

Recommendations

Automatic grammar generation from two different perspectives
Lfg generation by grammar specialization

This article describes an approach to Lexical-Functional Grammar LFG generation that is based on the fact that the set of strings that an LFG grammar relates to a particular acyclic f-structure is a context-free language. We present an algorithm that ...
Tree insertion grammar: a cubic-time, parsable formalism that lexicalizes context-free grammar without changing the trees produced

Tree insertion grammar (TIG) is a tree-based formalism that makes use of tree substitution and tree adjunction. TIG is related to tree adjoining grammar. However, the adjunction permitted in TIG is sufficiently restricted that TIGs only derive context-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACL '92: Proceedings of the 30th annual meeting on Association for Computational Linguistics

June 1992

346 pages

Program Chair:
Henry S. Thompson
University of Edinburgh

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 28 June 1992

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 85 of 443 submissions, 19%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
254
Total Downloads

Downloads (Last 12 months)42
Downloads (Last 6 weeks)4

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Minnen GGerdemann DGötz TAbney SHinrichs E(1995)Off-line optimization for Earley-style HPSG processingProceedings of the seventh conference on European chapter of the Association for Computational Linguistics10.3115/976973.976998(173-179)Online publication date: 27-Mar-1995
https://dl.acm.org/doi/10.3115/976973.976998
Martinovié MNagao MWilks Y(1994)Universal guides and finiteness and symmetry of grammar processing algorithmsProceedings of the 15th conference on Computational linguistics - Volume 210.3115/991250.991296(916-921)Online publication date: 5-Aug-1994
https://dl.acm.org/doi/10.3115/991250.991296
Takeda KPustejovsky J(1994)Tricolor DAGs for machine translationProceedings of the 32nd annual meeting on Association for Computational Linguistics10.3115/981732.981763(226-233)Online publication date: 27-Jun-1994
https://dl.acm.org/doi/10.3115/981732.981763

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents