LR Parsers For Natural Languages

Masaru TomitaCOLING 1984

TL;DR

This paper introduces MLR parsers, an extension of traditional LR parsers, designed to handle the inherent ambiguity of natural language grammars. By employing a dynamic programming approach to manage multiply-defined parsing table entries, MLR parsers can efficiently generate all possible parse trees for ambiguous sentences without redundant processing, a significant improvement over existing methods.

What Problem Does This Paper Address?

Traditional LR parsers, widely used in compiler construction, are highly efficient for context-free languages because they rely on deterministic parsing tables. However, natural languages present two major challenges for these parsers:

  1. Ambiguity: Natural language grammars are inherently ambiguous, meaning a single sentence can have multiple valid interpretations (parse trees). Standard LR parsers cannot handle this ambiguity because their parsing tables would have multiply-defined entries, breaking the deterministic nature of the parsing process.
  2. Context-Freedom Assumption: While some argue natural languages are not strictly context-free, the authors propose that a sufficiently comprehensive grammar for practical natural language processing can still be context-free. The primary hurdle, therefore, is managing ambiguity.

Existing approaches to ambiguity in LR parsing often involve statically selecting a single parse tree, which is undesirable for natural language processing where multiple interpretations might be necessary for later disambiguation.

Methods

The core innovation is the MLR parser, which extends standard LR parsers to handle ambiguous grammars. The key techniques are:

  • Dynamic Programming for Ambiguity: Instead of failing on multiply-defined entries in the parsing table, MLR parsers use a dynamic programming approach. When a multiply-defined entry is encountered, the parser effectively "splits" into multiple parallel processes, each pursuing one of the possible actions.
  • Pseudo-Parallelism and Synchronization: These parallel processes are synchronized. When a process "shifts" a word, it waits for all other processes to also shift the same word. Crucially, if multiple processes reach the same state (i.e., have the same state number on top of their stack), they are merged into a single process. This merging mechanism ensures that any part of the input sentence is parsed only once in the same way, achieving parsing efficiency similar to chart parsing without explicitly maintaining a chart.
  • MLR Parsing Table Generator: The paper mentions that the parsing table generator is adapted from standard LR parser algorithms, with the modification to allow and handle multiple entries.

Datasets

Not discussed in the paper. The paper uses example grammars and sentences for demonstration purposes rather than formal datasets.

Key Insights and Ideas

  • Ambiguity is Manageable: The paper demonstrates that ambiguity in natural language grammars, a long-standing issue for LR parsers, can be effectively managed without sacrificing parsing efficiency.
  • Pseudo-Parallelism as an Efficiency Gain: The novel use of pseudo-parallelism and process merging allows MLR parsers to explore multiple parse paths simultaneously while avoiding redundant computations, making it more efficient than simple breadth-first or depth-first search.
  • Chart Parsing Analogy: The merging of processes in common states provides a similar efficiency benefit to the common subconstituent recognition in chart parsing, but without the overhead of maintaining a chart data structure.
  • Handling Multi-Part-of-Speech Words: The MLR parser offers an elegant solution for words that can function as multiple parts of speech (e.g., "that"), as demonstrated in the second example.

Key Results

The paper demonstrates the MLR parser's ability to:

  • Produce Multiple Parse Trees: For ambiguous sentences like "I saw the man with a telescope," the parser correctly generates two distinct parse trees.
  • Efficient Parsing: The pseudo-parallelism and process merging mechanism ensures that each part of the input sentence is parsed only once in the same manner, leading to efficient parsing.
  • Handle Lexical Ambiguity: The parser successfully handles words with multiple grammatical categories, as shown with the word "that" in the example "That information is important is doubtful."
  • Theoretical Determinism: Despite the pseudo-parallelism, the authors argue the approach is theoretically still deterministic because the number of parallel processes is bounded by the number of states in the parsing table.

Limitations and Future Work

  • Tractability of Parsing Table Size: A key concern raised is whether the size of the parsing table remains manageable as the size of the grammar grows. The paper includes a figure (Fig. 6) illustrating the relationship between grammar complexity and LR parsing table size, suggesting that table size grows proportionally to grammar size, which is a positive sign.
  • Implementation: The MLR parser and its generator have been implemented in MACLISP and are running on Tops-20.
  • Future Work: The authors imply that further exploration into the tractability of parsing table sizes for very large grammars would be beneficial. The system's ability to handle grammars with thousands of phrase structure rules, potentially generated by rule-schema and meta-rules, is a promising direction.

Summary updated

BibTeX
@inproceedings{tomita1984lr,
  author = {Masaru Tomita},
  title = {{LR Parsers For Natural Languages}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}
Figure