TL;DR
This paper tackles the challenge of building practical natural language parsers by combining the strengths of lexicon-driven and phrase-structure-based approaches. They propose a novel implementation using a "graph-structured stack" to efficiently handle the non-determinism inherent in parsing, enabling a more robust and comprehensive parsing system.
What Problem Does This Paper Address?
Building effective natural language parsers is a complex task. Two dominant paradigms exist: lexicon-driven formalisms (like Categorial Grammar or HPSG) and phrase-structure-based formalisms (like DCG or GPSG). Lexicon-driven methods excel at capturing linguistic universals and flexible word order, but struggle with language-specific, "uninteresting" constructions like dates or numerical expressions. Phrase-structure-based methods, with their explicit rules, handle these low-level details well but can be less elegant for broader linguistic phenomena. The problem is that practical parsers need both capabilities. Ignoring low-level details makes a parser unusable for real-world text, while relying solely on phrase structure can lead to overly complex and less generalizable systems. This paper aims to bridge this gap by proposing a unified parsing framework.
Methods
The core of the paper's contribution lies in its approach to parsing and handling non-determinism.
- Shift-Reduce Parsing as a Unifying Framework: The authors first generalize both lexicon-driven and phrase-structure-based parsing into the common framework of shift-reduce parsing. In this model, words are "shifted" onto a stack, and then sequences of words or constituents on the stack are "reduced" into higher-level constituents.
- Graph-Structured Stack: To manage the inherent non-determinism (multiple possible reductions or shifts at any given point), they introduce the "graph-structured stack." This data structure allows for:
- Splitting: When multiple reduction options exist for the top of the stack, the stack is "split" to explore each possibility.
- Combining: If a new element needs to be shifted onto multiple branches of the stack, it's done only once, merging those branches.
- Local Ambiguity Packing: Identical states reached through different parsing paths are merged, preventing redundant computation.
- Integration: The paper then details how this graph-structured stack can be used to implement both lexicon-driven parsing (where reductions are guided by lexicon entries) and phrase-structure-based parsing (guided by explicit grammar rules). The main contribution is showing how these two can be combined within this unified framework.
Datasets
Not discussed in the paper. The paper focuses on the theoretical and algorithmic aspects of parsing rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- The "Uninteresting" is Crucial: A key insight is that while linguists might focus on "interesting" phenomena, practical NLP systems must handle the mundane, language-specific details (like dates, times, and numerical expressions) effectively. These often require the explicit rule-based power of phrase structure grammars.
- Shift-Reduce as a Universal Model: Framing both parsing approaches as variations of shift-reduce parsing provides a clean theoretical basis for unification.
- Graph-Structured Stack for Efficiency: The graph-structured stack is presented as a crucial mechanism for efficiently handling the combinatorial explosion of possibilities in non-deterministic parsing, making polynomial-time parsing achievable.
- Flexibility in Combination: The paper suggests two primary ways to combine the approaches: either enhance generalized LR parsing with lexicon-driven rules or enhance lexicon-driven parsing with phrase-structure rules, offering flexibility based on the specific needs of a system.
Key Results
The paper doesn't present quantitative results from a specific parser implementation. Instead, its key results are theoretical and algorithmic:
- A unified framework for lexicon-driven and phrase-structure-based parsing using shift-reduce parsing.
- The introduction and explanation of the graph-structured stack as an efficient mechanism for handling non-determinism in parsing.
- A clear proposal for how to combine the two parsing paradigms within this framework, making it suitable for practical applications.
Limitations and Future Work
- Practical Implementation Details: While the paper outlines the approach, the specific implementation details of combining the two parsing methods and the performance characteristics of such a combined system are not fully explored.
- Empirical Evaluation: The paper lacks empirical evaluation on real-world datasets to demonstrate the effectiveness and efficiency of the proposed combined parsing strategy.
- Future Work: The authors implicitly suggest that further work would involve building and evaluating such a combined parser. They also mention that the graph-structured stack is an enhancement to generalized LR parsing, implying that further exploration of its application in various parsing contexts is possible.
Summary updated