Linguistic formalisms like Lexical Functional Grammar (LFG), Head-Driven Phrase Structure Grammar (HPSG), and Tree Adjoining Grammar (TAG) provide elegant frameworks for capturing the complex, long-distance dependencies of natural language. However, executing these grammars computationally poses a significant challenge. Traditionally, parsers for these formalisms relied on a multi-stage pipeline: first, a context-free backbone is parsed to establish syntactic structure; second, a collection of feature constraints or functional equations is extracted; and finally, a separate constraint-satisfaction engine solves these equations to produce a final semantic or functional representation.
This multi-stage pipeline introduces substantial computational overhead. The core insight of compiling unification grammars into Definite Clause Grammars (DCGs) in Prolog is that this separation is unnecessary. By mapping linguistic features directly onto logic programming variables, syntactic parsing and constraint satisfaction can happen simultaneously through Prolog's native unification mechanism.
The Intuition: Variables as Feature Slots
To understand why this translation works, consider how an LFG functional structure (f-structure) or an HPSG attribute-value matrix tracks grammatical information like number, gender, or case. In a traditional pipeline, a rule might declare that a verb phrase inherits its subject's features, creating an equation like (↑ SUBJ NUM) = (↓ NUM).
In a DCG translation, these abstract equations are replaced by shared logic variables embedded directly within the parsing predicates. As explained in A PROLOG Implementation of Lexical Functional, grammatical categories are compiled into Prolog predicates where their arguments serve as containers for feature structures.
When a sentence is parsed, Prolog traverses the words and instantiates these variables. For example, matching the word "writes" instantly binds an uninstantiated number variable to singular. Because this variable is shared across the clause's predicates, the constraint propagates instantly to the subject noun phrase. If the subject is "they", Prolog's unification fails immediately, and its built-in backtracking mechanism discards that parse path. As Reyle et al. note, using logic variables to represent feature slots eliminates the need to build and solve an independent system of equations after parsing.
Linguistic Rule: S -> NP VP [Constraint: NP's agreement = VP's agreement]
│
▼ (Compilation)
DCG Clause: s(Agrmt) --> np(Agrmt), vp(Agrmt).
Interleaving Syntax and Semantics
By translating grammar rules annotated with functional schemata into DCGs, the construction of the underlying functional or semantic representation becomes a byproduct of the parse itself. Frey et al. and Yasukawa demonstrate that intricate linguistic phenomena, such as functional control and long-distance dependencies, can be resolved inline.
Instead of building a full syntax tree and then traversing it to resolve anaphora or long-distance movement, the target representation—whether it is an LFG f-structure or a discourse representation structure—is assembled incrementally. Eisele et al. and Oliva show that representing these structures as attribute-value pairs allows a simple merge predicate to handle feature sharing and detect structural contradictions on the fly. This declarative translation bridges the gap between high-level linguistic theory and executable code, as demonstrated by systems like INKA (Phillips et al.), which compile domain-specific natural language directly into executable Prolog rules.
Extending to Tree Adjoining Grammars
The strategy of compiling complex formalisms into logic programs is not limited to phrase-structure grammars like LFG. It has also been successfully applied to mildly context-sensitive formalisms like Tree Adjoining Grammars (TAGs).
TAGs operate on trees rather than strings, using operations like "adjoining" to insert one tree into the middle of another. Early theoretical work by Vijay-Shanker et al. and Weir et al. established a formal equivalence between TAGs and Head Grammars by showing that the "foot node" where a tree splits during adjoining behaves exactly like the "split point" in string-wrapping operations.
This structural insight allows modern surface realizers and generators to linearize TAG processing. As shown by Gardent et al., a complex feature-based TAG can be compiled into a Regular Tree Grammar (RTG) to represent its derivation trees tractably. From there, Gardent et al. demonstrate that this intermediate RTG can be translated directly into a DCG executable in Prolog. This conversion allows developers to use Prolog's native query mechanism to traverse the grammar automatically, making tasks like natural language generation and surface realization highly space-efficient.
Ensuring Termination
While compiling grammars into DCGs leverages Prolog's speed, it inherits a classic logic programming risk: infinite loops. Because standard Prolog uses a top-down, depth-first search strategy, left-recursive grammar rules or empty string expansions can cause the parser to loop infinitely, rendering the parser undecidable.
To make this translation practical, the target DCGs must be constrained. Dymetman addresses this by introducing a two-step grammar transformation specifically for offline-parsable DCGs. A grammar is offline-parsable if its context-free structural backbone guarantees that a sentence of length $n$ cannot have an infinitely large derivation tree. By applying a formal transformation to these grammars before compilation, the resulting Prolog code is mathematically guaranteed to terminate and remain complete, ensuring that the parser will find all valid structural interpretations without getting trapped in non-terminating branches.
Key Foundational Work
A Prolog Implementation of Lexical Functional Grammar as a Base for a Natural Language Processing System (1983) — contributed 5 concept elements to this direction.
A PROLOG Implementation of Lexical Functional Grammar (1983) — contributed 5 concept elements to this direction.
A PROLOG Implementation of Lexical Functional Grammar (1983) — contributed 1 concept elements to this direction.