A structure-sharing parser for lexicalized grammars

Roger Evans, David WeirCOLING 1998

TL;DR

This paper introduces a novel precompilation technique for lexicalized grammars, transforming them into finite state automata. By merging and minimizing these automata, the authors achieve significant structure sharing, leading to more efficient parsing without altering the underlying grammar formalism. This approach promises to speed up parsing by processing common substructures only once.

What Problem Does This Paper Address?

Parsing with wide-coverage lexicalized grammars, such as Tree-Adjoining Grammars (TAGs), is computationally expensive. A key challenge arises from the fact that many elementary structures within these grammars share common substructures. Conventional parsing algorithms often process these shared substructures multiple times, leading to duplicated computation. While previous work has explored compiling grammars into automata, this paper aims to enhance structure sharing by introducing automaton minimization and a more refined parsing strategy that separates recognition from parse recovery.

Methods

The core of the paper's contribution lies in its automaton-based approach to parsing. The authors propose transforming elementary grammar structures into finite state automata. The key innovations are:

  • Automaton Construction: Elementary grammar structures are converted into finite state automata that represent the traversal of these structures during parsing.
  • Merging and Minimization: Multiple automata (representing different elementary trees) are merged into a single automaton. Crucially, standard minimization algorithms are applied to this merged automaton. This step is vital for maximizing structure sharing. Unlike previous methods that restricted merging based on final states, this approach annotates transitions with the set of trees passing through them, enabling arbitrary merging.
  • Two-Phase Parsing: The parsing process is divided into two phases:
  • Recognition: This phase focuses on determining if an input string can be parsed by the grammar, identifying the root label of recognized trees.
  • Parse Recovery: This phase reconstructs the actual derivation tree(s) by backtracking through the recognition process. This separation allows for more efficient handling of shared structures.
  • Formal Treatment: The paper provides formal algorithms for constructing, merging, and minimizing the automata, as well as for the recognition and parse recovery phases.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic and theoretical aspects of grammar compilation and parsing, rather than empirical evaluation on specific datasets. Table 1 presents statistics from a previous study by Carroll et al. (1998) on a wide-coverage DTG grammar, which serves as an example of the potential compaction achieved.

Key Insights and Ideas

  • Automata as a Unified Representation: Representing grammar structures as automata provides a more abstract and unified view, allowing for sharing of computations that might not be apparent at the tree level.
  • Minimization is Key to Sharing: The paper highlights that applying standard automaton minimization techniques after merging is crucial for maximizing structure sharing. This is a significant improvement over approaches that might limit merging due to annotated final states.
  • Transition Annotations Enable Arbitrary Merging: Annotating transitions with the set of trees passing through them is a clever way to overcome the limitations of merging automata with distinct final states, enabling more comprehensive structure sharing.
  • Separation of Recognition and Recovery: Decoupling the recognition phase from the parse recovery phase offers a more structured and potentially efficient parsing strategy, especially when dealing with complex, shared grammar structures.

Key Results

The paper presents a formal framework and algorithms for structure-sharing parsing. While not reporting new empirical results, it builds upon and extends previous work. The key "results" are the proposed algorithms and the theoretical justification for their effectiveness in achieving greater structure sharing. Table 1 from Carroll et al. (1998) is cited to illustrate the significant compaction achieved by similar techniques, showing a reduction in the number of states and transitions in minimized automata compared to merged ones. For example, for the verb "give" (337 trees), the merged automaton has 2494 states and 3177 transitions, while the minimized automaton reduces this to 83 states and 233 transitions, with an average of 20.25 trees per state.

Limitations and Future Work

  • Assumptions on Elementary Trees: The presented algorithms assume elementary trees have a single anchor and a single spine. The authors acknowledge that some trees have secondary anchors or more complex structures, and suggest that the approach can be extended to handle these cases.
  • Formal vs. Empirical Improvements: The authors state that their approach offers empirical rather than formal improvements in performance. In the worst case, where no structure is shared, the performance might not improve.
  • Nondeterminism in Tree Recovery: The parse recovery process can involve nondeterminism, and exploring all possible paths would lead to an AND/OR derivation tree. The authors mention that search can be reduced by including pointers in items, but this comes at the cost of increased parsing time.
  • Future Work: The paper suggests exploring the extension of the approach to handle more complex tree structures and comparing it with other parsing optimization techniques, such as those from LR parsing.

Summary updated

BibTeX
@inproceedings{evans1998structure,
  author = {Roger Evans and David Weir},
  title = {{A structure-sharing parser for lexicalized grammars}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1998},
}
Figure