A Simple Transformation for ONine-Parsable Grammars and its Termination Properties

Marc DymetmanCOLING 1994 · OpenReview

Abstract

Definite Clause Grammars (DCGs) are a powerful extension of context-free grammars within logic programming, yet their parsing is generally undecidable in standard Prolog due to potential infinite loops. This paper introduces a straightforward two-step transformation—eliminating empty productions and left-recursion—specifically for Offline-Parsable (OP) grammars. The resulting transformation ensures that parsing terminates and finds all solutions, offering a simpler implementation path than complex algebraic methods like the Generalized Greibach Normal Form.

Introduction

Definite Clause Grammars (DCGs) provide a robust framework for natural language processing by integrating context-free structures with the unification-based power of Prolog. However, the standard top-down, depth-first search strategy of Prolog interpreters is susceptible to non-termination when encountering left-recursive rules (e.g., $NP \rightarrow NP\ PP$) or "empty" productions ($A \rightarrow \epsilon$).

To address this, the concept of offline-parsability (OP) is employed. A grammar is OP if its underlying context-free skeleton is not infinitely ambiguous. While theoretical results confirm that OP grammars are decidable, practical transformations to make them Prolog-compatible have often been mathematically dense. This work proposes a "simple transformation" that is both easy to implement and provably reliable for termination.

The Transformation Algorithm

The proposed method consists of two primary phases: the elimination of empty productions and the removal of left-recursion.

Empty-Production Elimination

The first phase adapts standard context-free grammar techniques for the unification-based environment of DCGs. The algorithm identifies rules that can derive an empty string and "folds" them into other rules. For instance, if a nonterminal can be empty, new versions of rules containing that nonterminal are generated—one where the nonterminal is present and one where it is omitted.

Figure 1: Illustration of the grammar transformation process, showing the elimination and folding of empty productions.

As shown in Figure 1, the transformation involves maintaining lists of rules (LIST1, LIST2) and identifying specific productions for deletion or modification. This iterative process is guaranteed to terminate provided the input grammar satisfies the offline-parsability constraint.

Left-Recursion Elimination

The core of the transformation involves re-encoding the grammar into a "generic" form using three specialized predicates:

  • g(X): A generic nonterminal representing an original category.
  • t(X): A predicate handling rules that initiate with a terminal symbol.
  • d(Y, X): An "immediate left-corner" predicate, signifying that category $Y$ can appear at the leftmost position of category $X$.

By replacing left-recursive rules with a structure based on the transitive closure of the left-corner relation (d_tc), the problematic recursion is converted into a right-leaning structure. This allows Prolog's top-down search to process the grammar without entering infinite loops.

Key Insights and Results

The primary contribution of this work is the Termination Guarantee. The paper demonstrates that a transformed DCG, when executed in Prolog using standard difference lists, will successfully enumerate all valid parses and terminate.

Furthermore, the transformation serves as a diagnostic tool: if the empty-production elimination phase fails to terminate, it indicates that the input grammar violates the offline-parsability constraint. While methods like the Generalized Greibach Normal Form (GGNF) handle a broader class of grammars, this approach prioritizes simplicity and ease of implementation for the OP subset, which covers the vast majority of natural language applications.

Conclusion

This transformation provides a practical bridge between linguistic theory and logic programming implementation. By focusing on the offline-parsable constraint, the author delivers an algorithm that is significantly easier to implement than previous algebraic approaches while maintaining rigorous termination properties. Future work may explore the scaling of this transformation for large-scale industrial grammars and provide more extensive empirical benchmarks.

Summary updated

BibTeX
@inproceedings{dymetman1994simple,
  author = {Marc Dymetman},
  title = {{A Simple Transformation for ONine-Parsable Grammars and its Termination Properties}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1994},
  url = {https://openreview.net/forum?id=YHarXEQV-8I},
}
Figure