A Generalized Greibach Normal Form for Definite Clause Grammars

Marc DymetmanCOLING 1992 · OpenReview

Abstract

Definite Clause Grammars (DCGs) provide a robust framework for describing languages by combining context-free rules with logical constraints. However, their reliance on Prolog's top-down, depth-first search makes them operationally fragile, particularly when faced with left-recursive rules. This paper introduces the Generalized Greibach Normal Form (GGNF), a universal transformation for DCGs. By factorizing a grammar into specific "unit" and "co-unit" components, GGNF ensures that any "offline-parsable" grammar will terminate in a standard Prolog engine. This approach preserves both declarative semantics and degrees of ambiguity, offering a formal solution to the long-standing problem of left-recursion in logic-based parsing.

Introduction

Definite Clause Grammars (DCGs) are a staple of computational linguistics and logic programming, allowing developers to describe complex languages by mixing context-free rules with logical constraints (unifications). Despite their power, they face two significant hurdles: undecidability and operational fragility. Because standard Prolog uses a top-down search strategy, left-recursive rules (e.g., vp -> vp, pp) lead to infinite loops, even if the grammar is theoretically decidable. While the Greibach Normal Form (GNF) exists for Context-Free Grammars (CFGs) to eliminate left-recursion, extending it to the more complex world of DCGs has historically been challenging. This paper bridges that gap by proposing a generalized form applicable to the broader class of Definite Grammar Schemes (DGS).

Methods: Grammar Factorization and Mixed Systems

The core of the GGNF transformation lies in partitioning the grammar's nonterminals and rules into three distinct sets based on their consumption of terminal symbols:

  • Initial Set (A): The starting point or entry points of the grammar.
  • Unit Nonterminals (U): Rules that generate only the empty string (ε). These are often the "hidden" sources of non-termination.
  • Co-unit Nonterminals (N): Rules that must consume at least one terminal symbol (a "word") before continuing.
Structural dependencies between grammar partitions A, N, and U in the GGNF transformation.

The mathematical heavy lifting is performed using "Mixed Systems," a generalization of algebraic systems and formal power series. This allows the author to treat grammar rules as equations and find "solutions" that preserve the original declarative semantics while changing the operational semantics (execution order). This factorization effectively "quarantines" the potential for infinite loops into the unit subgrammar.

Key Insights and Ideas

  • The "Textual Property" of Parsability: One of the most elegant results is that "offline-parsability"—a complex property to verify—becomes a simple textual check in GGNF: one simply looks for cycles in the unit rules.
  • Ambiguity Preservation: Standard GNF for CFGs often loses information about how many ways a string can be parsed. The GGNF variant presented here is specifically designed to preserve these degrees of ambiguity, making it more useful for linguistic analysis.
  • Universal Transformation: The transformation is "universal," meaning it works regardless of the specific interpretation of the auxiliary logic predicates, provided they are restricted to unifications.

Key Results and Termination Guarantees

The paper provides a formal existence proof: any DCG can be transformed into an equivalent GGNF. More importantly, it establishes a Termination Guarantee: for any offline-parsable DCG, a top-down Prolog implementation of its GGNF version will enumerate all solutions and terminate, effectively making the parser "strongly stable." When applied to simple CFGs, GGNF provides a new variant of the classical Greibach Normal Form that is superior in its handling of structural ambiguity.

Limitations and Future Work

While GGNF provides a powerful theoretical framework, some limitations remain. The termination guarantee relies on the auxiliary Prolog predicates being simple unifications (head clauses). If the user includes complex, non-terminating Prolog code inside the {} brackets of a DCG, GGNF cannot guarantee termination. Additionally, while the paper proves the transformation is possible, it does not provide a detailed analysis of the computational overhead or the potential "explosion" in the number of rules for very large, real-world grammars. Future work may focus on the development of fully automated grammar compilers leveraging this general form.

Summary updated

BibTeX
@inproceedings{dymetman1992generalized,
  author = {Marc Dymetman},
  title = {{A Generalized Greibach Normal Form for Definite Clause Grammars}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1992},
  url = {https://openreview.net/forum?id=DRTVMNHK6zT0},
}
Figure