Article

Free access

How to invert a natural language parser into an efficient generator: an algorithm for logic grammars

Author:

Tomek StrzalkowskiAuthors Info & Claims

COLING '90: Proceedings of the 13th conference on Computational linguistics - Volume 2

Pages 347 - 352

https://doi.org/10.3115/997939.997999

Published: 20 August 1990 Publication History

PDF eReader

Abstract

The use of a single grammar in natural language parsing and generation is most desirable for variety of reasons including efficiency, perspicuity, integrity, robustness, and a certain amount of elegance. In this paper we present an algorithm for automated inversion of a PROLOG-coded unification parser into an efficient unification generator, using the collections of minimal sets of essential arguments (MSEA) for predicates. The algorithm is also applicable to more abstract systems for writing logic grammars, such as DCG.

References

[1]

Colmerauer, Alain. 1982. PROLOG II: Manuel de reference et modele theorique. Groupe d'Intelligence Artificielle, Faculte de Sciences de Luminy, Marseille.

Google Scholar

[2]

Dymetman, Marc and Isabelle, Pierre. 1988. "Reversible Logic Grammars for Machine Translation." Proc. of the Second Int. Conference on Machine Translation, Pittsburgh, PA.

Google Scholar

[3]

Debray, Saumya, K. 1989. "Static Inference Modes and Data Dependencies in Logic Programs." ACM Transactions on Programming Languages and Systems. 11(3), July 1989, pp. 418--450.

Digital Library

Google Scholar

[4]

Grishman, Ralph. 1986. Proteus Parser Reference Manual. Proteus Project Memorandum #4, Courant Institute of Mathematical Sciences, New York University.

Google Scholar

[5]

Naish, Lee. 1986. Negation and Control in PROLOG. Lecture Notes in Computer Science, 238, Springer.

Digital Library

Google Scholar

[6]

Shieber, Stuart M., 1988. "A uniform architecture for parsing and generation." Proceedings of the 12th COLING, Budapest, Hungary, pp. 614--619.

Digital Library

Google Scholar

[7]

Shieber, Stuart, M., van Noord, Gertjan, Moore, Robert C. and Pereira, Fernando 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

Google Scholar

[8]

Shoham, Yoav and McDermott, Drew V. 1984. "Directed Relations and Inversion of PROLOG Programs." Proc. of the Int. Conference of Fifth Generation Computer Systems.

Google Scholar

[9]

Strzalkowski, Tomek, 1989. Automated Inversion of a Unification Parser into a Unification Generator. Technical Report 465, Courant Institute of Mathematical Sciences, New York University.

Google Scholar

[10]

Strzalkowski, Tomek, 1990. "An algorithm for inverting a unification grammar into an efficient unification generator." Applied Mathematics Letters, vol. 3, no. 1, pp. 93--96. Pergamon Press.

Crossref

Google Scholar

[11]

Strzalkowski, Tomek and Peng, Ping. 1990. "Automated Inversion of Logic Grammars for Generation." Proceedings of the 28th Annual Meeting of the ACL, Pittsburgh, PA.

Digital Library

Google Scholar

Cited By

View all

König ENagao MWilks Y(1994)Syntactic-head-driven generationProceedings of the 15th conference on Computational linguistics - Volume 110.3115/991886.991969(475-481)Online publication date: 5-Aug-1994
https://dl.acm.org/doi/10.3115/991886.991969
Gril RZampolli A(1992)Towards computer-aided linguistic engineeringProceedings of the 14th conference on Computational linguistics - Volume 210.3115/992133.992198(827-834)Online publication date: 23-Aug-1992
https://dl.acm.org/doi/10.3115/992133.992198
Martinovic MStrzalkowski TThompson H(1992)Comparing two grammar-based generation algorithmsProceedings of the 30th annual meeting on Association for Computational Linguistics10.3115/981967.981978(81-88)Online publication date: 28-Jun-1992
https://dl.acm.org/doi/10.3115/981967.981978

Recommendations

An efficient parser generator for natural language
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 1

We have developed a parser generator for natural language processing. The generator named "NLyacc" accepts grammar rules written in the Yacc format. NLyacc, unlike Yacc, can handle arbitrary context-free grammars using the generalized LR parsing ...
An efficient LR parser generator for tree-adjoining grammars
New developments in parsing technology

In this chapter we discuss practical LR-like parser generator models for Tree Adjoining Grammars (TAGs) and propose a new algorithm. The algorithm has been implemented and applied to two large coverage TAGs for English: the XTAG English grammar, and a ...
Bottom-up context-sensitive algorithms for Bengali parser in natural language processing

This paper embodies the design of parsing algorithms tangibly for a Bengali parser. To design parsing algorithms a detailed study on linguistics and grammar has been performed. A detailed study also has been made on the various techniques and algorithms ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLING '90: Proceedings of the 13th conference on Computational linguistics - Volume 2

August 1990

438 pages

Editor:
Hans Karlgren
KVAL Research Institute for Information Science, Stockholm, Sweden

Publisher

Association for Computational Linguistics

United States

Publication History

Published: 20 August 1990

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 1,537 of 1,537 submissions, 100%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
361
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

König ENagao MWilks Y(1994)Syntactic-head-driven generationProceedings of the 15th conference on Computational linguistics - Volume 110.3115/991886.991969(475-481)Online publication date: 5-Aug-1994
https://dl.acm.org/doi/10.3115/991886.991969
Gril RZampolli A(1992)Towards computer-aided linguistic engineeringProceedings of the 14th conference on Computational linguistics - Volume 210.3115/992133.992198(827-834)Online publication date: 23-Aug-1992
https://dl.acm.org/doi/10.3115/992133.992198
Martinovic MStrzalkowski TThompson H(1992)Comparing two grammar-based generation algorithmsProceedings of the 30th annual meeting on Association for Computational Linguistics10.3115/981967.981978(81-88)Online publication date: 28-Jun-1992
https://dl.acm.org/doi/10.3115/981967.981978

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Abstract

References

Cited By

Recommendations

An efficient parser generator for natural language

An efficient LR parser generator for tree-adjoining grammars

Bottom-up context-sensitive algorithms for Bengali parser in natural language processing

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations