Introduction
In the early 1980s, Henry Thompson presented a significant advancement in computational linguistics with MCHART, a modular framework designed for chart parsing. The work specifically addressed the challenges of implementing Phrase Structure Grammar (PSG)—a theory that, while linguistically elegant, introduced substantial computational hurdles such as category variables and unbounded dependencies.
The Problem: Computational Explosion
Linguistic theories like Gerald Gazdar’s PSG gained traction for their ability to describe complex language features (e.g., "Kim saw the man that Robin liked") using context-free rules. However, these grammars were "notationally rich," meaning a single rule schema could represent thousands of actual rules.
Traditional parsers faced two main issues:
- Computational Explosion: Expanding every possible rule ahead of time was memory-intensive and slow.
- Rigidity: Parsers were often hard-coded for specific grammars, making them difficult for linguists to use as experimental tools.
The MCHART Solution
Thompson’s MCHART, implemented in Lisp, treats parsing as a graph-building exercise. The "chart" is a directed graph where edges represent discovered constituents. By decoupling the core engine from specific linguistic formalisms, MCHART allows for a "mixed-initiative" approach that combines bottom-up and top-down processing.
The Fundamental Rule
The framework relies on the "Fundamental Rule" of chart parsing: when an active edge (a search for a constituent) meets an inactive edge (a completed constituent) that satisfies its requirements, a new edge is created. This ensures that every valid parse is found exactly once without redundant computation.
Key Insights
- On-the-fly Instantiation: Rather than pre-calculating every version of a rule, MCHART clones rules only when a matching word or phrase is found, significantly reducing memory overhead.
- Mixed-Initiative Parsing: To handle "slash categories" (representing gaps or traces in a sentence), MCHART uses bottom-up strategies for standard rules and top-down strategies to predict where a gap might occur. This prevents the system from erroneously "hallucinating" empty constituents.
- Declarative Power: The system was designed to be accessible to linguists, allowing them to express grammars in their own terms without needing deep programming expertise.
Results and Limitations
Thompson demonstrated that PSG’s most difficult features—including meta-rules and slash categories—could be implemented in a modular, non-ad-hoc way. While the framework prioritized modularity and pedagogical clarity over raw performance, it proved capable of supporting diverse formalisms like Augmented Transition Networks (ATNs).
One remaining challenge noted was the complexity of combining rule schemata for conjunctions with slash categories, which could still lead to "over-parsing" in certain scenarios. Future work aimed to expand the system into a directed generator and a broad-coverage parser for the wider linguistic community.
Summary updated