Paper: A Generalized Greibach Normal Form For Definite Clause Grammars

ACL ID C92-1057
Title A Generalized Greibach Normal Form For Definite Clause Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1992
Authors

An arbitrary definite clause grammar can be transforaled into a so-called Generalized Greibach Normal Form (GGNF), a generalization of the classical Greibach Nor- mat Form (GNF) for context-free grammars. The normalized definite clause grammar is declara- tively equivalent to the original definite clause grammar, that is, it assigns the same analyses to the same strings. Offline-parsability of the original grammar is reflected in an elementary textual property of the transformed gram- mar. When this property holds, a direct (top-down) Pro- log implementation of the normalized grammar solves the parsing problem: all solutions are enumerated on backtracking and execution terminates. When specialized to the simpler case of context-free grammars, the GGNF provides a variant to file GNF, where ...