Paper: A Simple Transformation For Online-Parsable Grammars And Its Termination Properties

ACL ID C94-2199
Title A Simple Transformation For Online-Parsable Grammars And Its Termination Properties
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1994
Authors

We present, in easily reproducible terms, a simple transformation for offline-parsable grammars which results in a provably terminating parsing pro- gram directly top-down interpretable in Prolog. The transformation consists in two steps: (1) removal of empty-productions, followed by: (2) left-recursion elimination. It is related both to left-corner parsing (where the grammar is compiled, rather than inter- preted through a parsing program, and with the ad- vantage of guaranteed termination in the presence of empty productions) and to the Generalized Greibach Normal Form for I)CGs (with the advantage of imple- mentation simplicity). 1 Motivation Definite clause grammars (DCGs) are one of the sim- plest and most widely used unification grammar for- malisms. They represent a direct augmentat...