A Generalized Greibach Normal Form for Definite Clause Grammars

A Generalized Greibach Normal Form for Definite Clause Grammars Marc Dymetman CCRIT, Communications Canada 1575 boul. Chomedey Laval (Qutbec) H7V 2X2, Canada dymetman@ccrit.doc.ca Abstract 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 the transformed context-free grammar not only generates the same strings as the original grammar, but also preserves their degrees of ambiguity (this last prop- erty does not hold for the GNF). The GGNF seems to be the first normal form result for DCGs. It provides an explicit factorization of the potential sources of uudeeidability for the parsing prob- lem, and offers valuable insights on the computational structure of unification grammars in general. 1 Introduction From the point of view of decidability, the parsing prob- lem with a definite clause grammar is much more com- plex than the corresponding problem with a context-free grammar. The parsing problem with a context-live gram- mar is decidable, i.e. there exists an algorithm which de- termines whethex a given string is accepted or not by the grammar; t by contrast, the parsing problem with a deft- nite clause grammar is undecidable, even if the auxiliary Prolog predicates are restricted to be unifications. 2 t For instance the standard top-down parsing algorithm using a GNF of the grammar. 2This assumption, or a similar one, is always made when the decidability proparfies of logical (or unification) grammars are studied. The reason is simple: if the auxiliary predicates are defined through an unrestricted Prolog program, there is no means of guaranteeing that calling some auxill~y predicate will not result in nontexmination, for reasons quite independent from the structure of the grammar under consideration. The In other words, there does not exist, in general, an al- gorithm for deciding whether a definil~ clause grammar DCGI accepts a string String, i.e. whether there exists some linguistic structure S such that DCG1 "analyses String into S'. On the other hand, ander the condi- tion that DCCx is offline-parsable, that is, under the condition that the context-free skeleton of DCG1 is not infinitely ambiguous, then the parsing problem is indeed decidable [7]. The fact that the parsing problem with DCGt is de- cidable in theory should be carefully distinguished from the fact that a given algorithm for parsing is able to ex- ploit this potentiality. A parsing algorithm for which this is the case, that is, an algorithm which is able, …

Content truncated to 500 words