Chart Parsing and Rule Schemata in PSG

Henry ThompsonACL 1981 · DOI

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:

  1. Computational Explosion: Expanding every possible rule ahead of time was memory-intensive and slow.
  2. 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.

A completed chart parse for the sentence "Kim saw the child with the glass," demonstrating how constituents like NP, PP, and VP are layered within the graph.

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.

An illustration of the chart's internal state (Figure 3d in the original text), showing the interaction between active edges (searches) and inactive edges (completed constituents) during the instantiation of a Noun Phrase.

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

BibTeX
@inproceedings{thompson1981chart,
  author = {Henry Thompson},
  title = {{Chart Parsing and Rule Schemata in PSG}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1981},
  doi = {10.3115/981923.981966},
}
Figure