Chart Parsing According to the Slot and Filler Principle

Peter HellwigCOLING 1988

TL;DR

This paper introduces a novel chart parsing algorithm that leverages a dependency grammar and a "slot and filler" principle. This approach allows for the representation of complex syntactic and semantic information directly within lexical items, enabling more flexible and efficient parsing, particularly for discontinuous constituents.

What Problem Does This Paper Address?

Traditional parsers often rely on phrase structure grammars and rule-based systems, which can struggle with the nuances of natural language, especially phenomena like discontinuous constituents (e.g., "What did John eat?"). Representing the intricate relationships between words and their complements, along with morpho-syntactic and functional-syntactic information, poses a significant challenge. Existing methods often require separate phases for different types of information or struggle to handle non-contiguous grammatical structures effectively.

Methods

The paper proposes a chart parsing algorithm based on a lexicalized dependency grammar. Instead of abstract rules, grammatical relationships are embedded within the lexical entries themselves. The core innovation is the slot and filler principle, where lexical items contain "slots" representing expected dependents and their required properties. The parser uses a chart (a well-formed substring table) to store intermediate parsing results.

Key aspects of the method include:

  • Dependency Structure: Focuses on the relationship between lexemes and their complements, abstracting from simple concatenation.
  • Complex Categories: Uses feature structures (sets of parameters and values) for rich linguistic information, unified through a unification mechanism.
  • Lexicalization: Syntactic relationships are part of lexical descriptions, allowing for easier modification without affecting the entire grammar.
  • Slot and Filler: Lexical items have slots for dependents, which are filled by other lexical items or structures.
  • Chart Parsing: Employs a chart to store and combine parsed segments efficiently, avoiding backtracking.
  • Discontinuous Segments: A novel mechanism using bit strings to represent segment extensions allows the parser to handle discontinuous constituents by tracking word inclusion and exclusion.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Lexicalization is Powerful: Embedding grammatical information directly into words simplifies grammar updates and reduces the risk of unforeseen side effects compared to rule-based systems.
  • Dependency Unification is Elegant: Combining dependency structures with feature unification allows for a parallel treatment of syntactic and semantic features, a more integrated approach than some existing formalisms.
  • Slots as the Key to Structure: The "slot and filler" mechanism provides a flexible way to build complex structures by matching expected dependents with available constituents.
  • Bit Strings for Discontinuity: The use of bit strings to represent segment extensions is a clever and effective way to manage discontinuous constituents within a chart parsing framework. This allows for a more comprehensive representation of natural language phenomena.

Key Results

The paper demonstrates the mechanism with an example sentence ("Flying planes can be dangerous") and outlines how the chart evolves through lexicon lookup and slot-filling. It also illustrates the handling of discontinuous segments with a question ("What does Gudrun feed to her cat?"). The authors state that the parser is fully implemented and applied to German, French, and English.

Limitations and Future Work

The authors acknowledge that the notation used in the figures is simplified and that a detailed categorization was omitted for brevity. They also mention that the chart representation for discontinuous segments involves alternating ones and zeros in bit strings, with trailing zeros omitted, which implies a specific implementation detail. Future work would likely involve further refinement of the feature structures, expansion of the lexicon, and potentially more extensive empirical evaluation across different languages and complex linguistic phenomena.

Summary updated

BibTeX
@inproceedings{hellwig1988chart,
  author = {Peter Hellwig},
  title = {{Chart Parsing According to the Slot and Filler Principle}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1988},
}
Figure