L* Parsing: A General Framework for Syntactic Analysis of Natural Language

Eric K. Jones, Linton M. MillerAAAI 1994

Introduction

In the development of Natural Language Processing (NLP) during the 1990s, a significant tension existed between two primary parsing philosophies: the flexibility of chart parsing and the computational speed of table-driven LR parsing. Chart parsers, such as the Earley parser, allowed for sophisticated mixing of top-down and bottom-up strategies, facilitating early pruning of incorrect parses. However, they often suffered from high runtime overhead. Conversely, table-driven parsers like Generalized LR (GLR) were highly efficient but rigid, typically restricted to a fixed bottom-up strategy that struggled to incorporate "look ahead" or dynamic strategy shifts.

In their 1994 paper, Eric Jones and Linton Miller introduced L* Parsing, a framework designed to bridge this gap. L* offers a generalized table-driven algorithm that supports flexible, "eager" control strategies, combining the adaptability of chart parsing with the high performance of traditional LR systems.

The Flexibility-Efficiency Trade-off

Natural language is inherently ambiguous. A single sentence can yield numerous valid syntactic structures, many of which are semantically implausible. Efficient parsing requires the ability to discard unpromising partial parses as early as possible, often by integrating semantic or pragmatic information.

The authors identified a fundamental trade-off:

  • Chart Parsers: Highly flexible and easy to integrate with semantic "oracles," but slow due to significant constant-factor overhead at runtime.
  • Table-driven Parsers: Extremely fast by pre-computing work into tables, but limited by a fixed bottom-up approach that cannot easily halt a failing parse mid-stream based on external feedback.

The L* Algorithm: Eager Reduction

The core innovation of the L framework is Eager Reduction. In a standard LR parser, a rule (e.g., $NP \rightarrow Det + N$) is only reduced once all its constituents are identified. In contrast, an L parser can perform a reduction before the entire right-hand side of a rule is seen.

An eager parse tree for the sentence fragment 'Mary ate the...', showing the early proposal of a Verb Phrase (VP) and Sentence (S) node.

Key components of the L* method include:

  • Eager Reduction: Proposing a parent node (such as a Verb Phrase) as soon as a critical component (like the Verb) is encountered, even before subsequent components (like the Object NP) are processed.
  • Cascaded Reductions: Eager reductions can trigger further reductions higher up the tree, effectively generating top-down expectations.
  • State Equivalence Classes: To maintain efficiency, the algorithm groups similar parser states. This ensures that identical sub-trees are shared within the "parse forest" rather than being redundantly recomputed.
  • Oracle Integration: L* provides a formal mechanism to consult an external "oracle" (e.g., a semantic analyzer). If the oracle rejects a partial structure, the parser uses "kill pointers" to prune that branch without affecting shared valid structures.
Step-by-step trace of L* parsing showing the evolution of stack states and the corresponding tree construction.

Evaluation and Results

The authors evaluated L using custom toy grammars and a 327-rule feature grammar representing a subset of English. A key test involved the ungrammatical sentence: "Jim are the best man."*

Comparing L* to a standard GLR parser:

  • Standard GLR: Generated 34 nodes in the parse forest before identifying the sentence as invalid.
  • L* (with Eager Reduction): By checking subject-verb agreement eagerly, it rejected the sentence after generating only 18 nodes.

While L* exhibits a slight speed degradation for perfectly grammatical sentences due to the overhead of managing eager states, its ability to "fail fast" on ill-formed input makes it significantly more robust for real-world applications.

Conclusion

L* Parsing represents a foundational advancement in syntactic analysis. By allowing developers to tune the parser along the spectrum between top-down and bottom-up strategies, it provides a powerful tool for building intelligent, high-performance NLP systems. Future work suggested by the authors includes extending the framework to handle cyclic grammars and moving from binary oracle feedback to graded judgments.

Summary updated

BibTeX
@inproceedings{jones1994l,
  author = {Eric K. Jones and Linton M. Miller},
  title = {{L* Parsing: A General Framework for Syntactic Analysis of Natural Language}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure