A New Transformation into Deterministically Parsable Form for Natural Language Grammars

Nigel R. Ellis, Roberto Garigliano, Richard G. Morgan


Abstract
Marcus demonstrated that it was possible to construct a deterministic grammar/interpreter for a subset of natural language [Marcus, 1980]. Although his work with PARSIFAL pioneered the field of deterministic natural language parsing, his method has several drawbacks: • The rules and actions in the grammar / interpreter are so embedded that it is difficult to distinguish between them. • The grammar / interpreter is very difficult to construct (the small grammar shown in [Marcus, 1980] took about four months to construct). • The grammar is very difficult to maintain, as a small change may have several side effects. This paper outlines a set of structure transformations for converting a non-deterministic grammar into deterministic form. The original grammar is written in a context free form; this is then transformed to resolve ambiguities.
Anthology ID:
1993.iwpt-1.7
Volume:
Proceedings of the Third International Workshop on Parsing Technologies
Month:
August 10-13
Year:
1993
Address:
Tilburg, Netherlands and Durbuy, Belgium
Editors:
Harry Bunt, Robert Berwick, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Bernard Lang, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
61–72
Language:
URL:
https://aclanthology.org/1993.iwpt-1.7
DOI:
Bibkey:
Cite (ACL):
Nigel R. Ellis, Roberto Garigliano, and Richard G. Morgan. 1993. A New Transformation into Deterministically Parsable Form for Natural Language Grammars. In Proceedings of the Third International Workshop on Parsing Technologies, pages 61–72, Tilburg, Netherlands and Durbuy, Belgium. Association for Computational Linguistics.
Cite (Informal):
A New Transformation into Deterministically Parsable Form for Natural Language Grammars (Ellis et al., IWPT 1993)
Copy Citation:
PDF:
https://aclanthology.org/1993.iwpt-1.7.pdf