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.
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