Abstract
While Prolog is widely recognized for its native top-down backtracking parsers (Definite Clause Grammars), this paper demonstrates that the language is equally capable of supporting efficient, deterministic, and bottom-up parsing strategies. By utilizing Prolog's unification and the "cut" operator, we can implement LL(k), LR(k), and Marcus-style parsers that avoid the performance pitfalls of standard backtracking, such as left recursion and exponential time complexity.
Introduction
In the early 1980s, Prolog emerged as a powerful tool for Natural Language Processing (NLP) because its Definite Clause Grammar (DCG) facility allowed for the rapid development of top-down backtracking parsers. However, these standard parsers faced three primary challenges:
- Left Recursion: Standard top-down parsers can enter infinite loops when encountering left-recursive grammar rules.
- Inefficiency: Backtracking often results in redundant parsing of the same sentence fragments, leading to exponential time complexity.
- Determinism: Linguistic theories, notably those of Mitchell Marcus (1980), suggest that human parsing is largely deterministic and does not rely on exhaustive backtracking.
This paper explores how to implement these more sophisticated, deterministic strategies within the Prolog framework.
Parsing Methodologies
The implementation builds from basic deterministic structures to complex natural language architectures.
Deterministic LL(k) and Shift-Reduce
To achieve determinism in a top-down LL(k) parser, the Prolog "cut" operator (!) is used alongside explicit lookahead. This forces the parser to commit to a single rule once a match is identified, pruning the search space.
For bottom-up parsing, a shift-reduce architecture is introduced. This stack-based approach "shifts" input words onto a stack and "reduces" them into higher-level categories (e.g., combining a determiner and a noun into a noun phrase) whenever the top of the stack matches a grammar rule.
The Marcus Parser
The centerpiece of this work is the implementation of a Marcus-style parser. This architecture utilizes a buffer of upcoming symbols and "packets" of rules that are dynamically activated or deactivated based on the current state of the parse tree. These concepts map cleanly onto Prolog predicates, demonstrating the language's utility as a high-level implementation tool for linguistic theory.
Evaluation and Results
The system was evaluated using a set of complex English sentences on a compiled DEC-10 Prolog implementation. The results demonstrated a linear relationship between sentence length and parsing time, a significant improvement over backtracking methods. For instance, a simple sentence like "John has scheduled a meeting for Wednesday" was parsed in 70ms, while a more complex passive structure took 84ms. A long sentence involving auxiliary verb chains was parsed in 145ms.
While these times were not as fast as specialized low-level code of the era, the implementation remained highly extensible and maintained predictable performance.
Discussion and Conclusion
The primary insight of this work is that Prolog's power is not limited to its default search strategy. Its unification and list-processing capabilities make it an excellent meta-language for building custom parsing engines. The "cut" operator is essential for engineering these efficient systems, allowing developers to encode deterministic logic directly into the grammar rules.
In conclusion, deterministic bottom-up designs are well-suited for natural language processing, and Prolog provides a natural environment for their realization. Future work involves expanding grammar coverage and optimizing the underlying stack operations to further improve speed.
Summary updated