An alternative LR algorithm for TAGs

Mark-Jan NederhofCOLING 1998

TL;DR

This paper introduces a novel LR parsing algorithm for Tree-Adjoining Grammars (TAGs), addressing a flaw in a previous incorrect algorithm. The new method simplifies the parsing process, making it more akin to traditional context-free grammar parsing and facilitating straightforward construction of derived trees and feature computation.

What Problem Does This Paper Address?

Parsing natural language efficiently is a long-standing challenge. While LR parsing techniques have proven highly effective for context-free grammars, extending them to more powerful formalisms like Tree-Adjoining Grammars (TAGs) has been difficult. A previous attempt to adapt LR parsing for TAGs by Schabes and Vijay-Shanker (1990) was found to be overly complex and, more critically, incorrect. This paper aims to provide a correct and simpler LR parsing algorithm for TAGs, bridging the gap between the efficiency of LR parsing and the expressive power of TAGs for natural language.

Methods

The core contribution is a new LR parsing algorithm for TAGs. The authors present a detailed construction of the LR table and the automaton that operates on it. Key aspects of their approach include:

  • Simplified Construction: The algorithm is designed to be much simpler than its predecessor, closely mirroring the structure of LR parsing for context-free grammars.
  • Incorporation of Reductions: A novel aspect is the explicit incorporation of subtree reductions, which is crucial for handling the tree-adjoining operations.
  • LR State Definition: The algorithm defines LR states as sets of "items," which are essentially productions with a dot indicating progress. The closure and goto functions are adapted to handle tree structures and adjunctions.
  • Handling Auxiliary Trees and Subtrees: The method distinguishes between elementary trees and subtrees of elementary trees, defining specific sets of "items" for each.
  • Deterministic Automata for Cross-Sections: To efficiently recognize required string patterns (cross-sections) within the stack, the authors construct deterministic finite automata. This is a key mechanism for matching parts of trees during parsing.

Datasets

Not discussed in the paper. The paper uses a small example grammar (Figure 1) and refers to the English grammar developed by the XTAG project for implementation details, but no specific datasets for training or evaluation are mentioned.

Key Insights and Ideas

  • Correctness and Simplicity are Achievable: The paper demonstrates that a correct and significantly simpler LR parsing algorithm for TAGs is possible, overcoming the limitations of prior work.
  • Bridging Context-Free and Tree-Adjoining Parsing: The new algorithm shows how many useful properties from context-free LR parsing can be carried over to TAG parsing, making the transition smoother for researchers familiar with both.
  • The Importance of Subtree Reductions: Explicitly handling subtree reductions is identified as a critical component for correctly parsing TAGs.
  • Deterministic Recognition of Tree Structures: The use of deterministic finite automata to recognize specific string patterns (cross-sections) within the parser's stack is an elegant solution for efficiently matching tree components.

Key Results

The paper presents the algorithm and its theoretical underpinnings. While quantitative results are not the primary focus, the authors discuss the implementation for a large English grammar. They note that the size of the generated LR table is "prohibitively large" (over 46 MB for storage in Prolog), with the majority consumed by the goto functions. However, the time for table generation was acceptable (around 25 minutes). The automata for recognizing cross-sections were found to be small. The key qualitative result is that the new algorithm correctly parses the language defined by the example grammar, unlike the incorrect algorithm it replaces.

Limitations and Future Work

  • Table Size: The most significant limitation highlighted is the prohibitive size of the generated LR table for large grammars, posing a challenge for practical implementation.
  • Hidden Left Recursion: The paper acknowledges the presence of "hidden left recursion" in grammars like English, which is a known issue in traditional LR parsing that can preclude nondeterministic backtracking. The authors suggest tabular realization as a potential solution, which will be the subject of further research.
  • Extensions: The authors mention that the algorithm can be straightforwardly extended to handle tree substitution (another common operation in modern TAGs) and the computation of derived trees or features, indicating promising avenues for future work.
  • Empty String Labels: The paper briefly touches upon the technical problem introduced by allowing empty string labels on leaves and suggests a solution involving extending items with an extra component.

Summary updated

BibTeX
@inproceedings{nederhof1998alternative,
  author = {Mark-Jan Nederhof},
  title = {{An alternative LR algorithm for TAGs}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1998},
}
Figure