Miguel A. Alonso, Djamé Seddah, Éric Villemonte de la Clergerie Proceedings of the Fifth International Workshop on Tree Adjoining Grammar and Related Frameworks (TAG+5). 2000.
Abstract
This paper details the practical implementation of a compiler for Tree Adjoining Grammar (TAG) parsers within the DyALog system. By using 2-stack automata as an intermediate representation and applying a dynamic programming interpretation, the authors achieve efficient tabular parsing with a worst-case time complexity of $O(n^6)$.
Introduction
Tree Adjoining Grammars (TAGs) offer significant advantages for natural language modeling due to their ability to handle complex syntactic dependencies. However, the increased expressive power of TAGs compared to Context-Free Grammars comes with a computational cost. Practical application requires efficient parsing strategies, typically implemented via tabular methods (chart parsing) to avoid redundant computations. This paper describes the implementation of a compiler for TAG parsers within the DyALog system, focusing on the transition from high-level grammar descriptions to efficient, executable tabular parsers.
The 2-Stack Automaton Framework
The core of the compilation strategy involves using a 2-stack automaton (2SA) as an intermediate representation. While standard push-down automata utilize a single stack, the 2SA employs a "Master Stack" for primary tree traversal and an "Auxiliary Stack" to manage the "bookkeeping" required during adjunction—the process where an auxiliary tree is inserted into another tree.
The system defines specific transitions to handle these operations:
- ACALL/ARET: Transitions for calling and returning from an adjunction at a node.
- FCALL/FRET: Transitions for calling and returning from the foot of an auxiliary tree.
By modulating how node arguments and position variables are handled within these transitions, the compiler can generate different parsing strategies (e.g., Earley-like or bottom-up) without altering the underlying engine.
Tabular Parsing and Optimization
To achieve efficiency, the 2SA derivations are interpreted using dynamic programming. The computation is broken down into "items"—tabulable fragments of the derivation. Several optimizations are employed to maintain a worst-case time complexity of $O(n^6)$ and space complexity of $O(n^5)$:
- Meta-transitions: Related call and return transitions are grouped to simplify execution logic.
- Projections: To manage memory, stored items are "projected" by removing components unnecessary for future lookups.
- Partial Applications: Complex rules are decomposed so the engine combines only one item with one transition at a time, keeping the logic lean.
The complexity of these traversals, as shown in the figure above, highlights the necessity of efficient item management and the role of the auxiliary stack in tracking the "context" of an adjunction. Instead of saving a full snapshot of the stacks, the system saves "mini-configurations"—just enough information to resume the computation later.
Evaluation and Results
The system was evaluated using both "pathological" grammars designed to test worst-case scenarios and a non-lexicalized French XTAG-like grammar consisting of 50 trees. On a Pentium II 450MHz machine, the compiled parser processed sentences of 3 to 15 words in 0.5 to 2 seconds. The implementation demonstrated that TAG support could be integrated into an existing logic programming system (DyALog) primarily through compiler modifications, leveraging the robustness of the underlying abstract machine.
Conclusion
The use of 2-stack automata provides a powerful abstraction for TAG parsing, bridging linguistic theory and dynamic programming. Key insights include the "modulation" of position variables to support multiple parsing strategies and the use of "mini-configurations" to minimize the state stored in the chart. Future work focuses on validating the effectiveness of projections and further factorizing tree traversals to share work between similar tree structures.
Summary updated