Presented at AAAI-83, MCHART represents a significant architectural shift in the development of natural language processing (NLP) tools. Rather than functioning as a single, rigid parser, MCHART was designed as a "meta-shell"—a modular framework that manages the complex bookkeeping of chart parsing while allowing researchers to swap out search strategies and grammatical formalisms with ease.
The Architectural Challenge: Decoupling Parsing Components
In the early 1980s, building a natural language parser was typically a monolithic task. If a researcher wanted to test a new search strategy (such as switching from depth-first to breadth-first) or implement a new grammatical formalism, they often had to rewrite the entire system from scratch.
The author of MCHART identified a critical need to separate three distinct concerns in parsing software:
- Essential Bookkeeping: Managing the "chart," the underlying data structure representing the sentence being parsed.
- Scheduling Issues: Determining the search strategy or the order in which paths are explored.
- Grammatical Formalisms: Defining the actual linguistic rules of the language.
MCHART provides a standardized engine to handle the bookkeeping, offering clean, modular interfaces for scheduling and grammar definition.
The MCHART Framework: Agendas and Signals
MCHART is built upon the active chart parsing methodology. In this model, a "chart" consists of vertices and edges. Inactive edges represent completed constituents (e.g., a fully identified Noun Phrase), while active edges represent hypotheses or incomplete constituents (e.g., a Verb looking for a following Noun Phrase to complete a Verb Phrase).
The core innovation of MCHART lies in two specific mechanisms:
- The Agenda: This is a multi-level priority queue system. Instead of hard-coding the order of operations, MCHART places "function applications" on an agenda. By simply changing the queue discipline (e.g., LIFO for depth-first or FIFO for breadth-first), a user can alter the entire search behavior of the parser without modifying the underlying grammar.
- Signals: MCHART utilizes an event-driven interface. When the system performs a basic operation, such as adding an edge to the chart, it raises a "signal." Users can define custom responses to these signals to implement various parsing styles, such as top-down or bottom-up rule invocation.
Implemented in several Lisp dialects (UCILISP, FranzLisp, and Interlisp), the system was designed for high portability across the AI laboratories of the era.
Applications and Experimental Utility
While MCHART is a framework rather than a specific model trained on a dataset, its utility was demonstrated through the implementation of several diverse parsing systems, including:
- Context-free phrase structure grammars.
- Recursive Transition Networks (RTNs).
- Augmented Transition Networks (ATNs).
- Generalized Phrase Structure Grammar (GPSG).
Key Results
The framework proved successful in both educational and high-level research contexts. At the Open University, students with no prior experience were able to convert a context-free parser into an RTN parser within a single week using MCHART. For research, the author used the framework to develop a large-scale system for GPSG, allowing for the rapid investigation of complex linguistic phenomena, such as cross-serial dependencies, in just a few days.
Discussion and Future Directions
The primary "aha moment" of MCHART is the realization that the "Fundamental Rule" of chart parsing—how active and inactive edges combine—can be treated as a modular hook. This allows a single engine to support wildly different linguistic theories. Furthermore, by treating parsing as a series of tasks on an agenda, the system elegantly handles natural language ambiguity without traditional, cumbersome backtracking.
However, this flexibility comes with a trade-off in efficiency. As a generalized framework with multiple layers of abstraction, MCHART may be slower than specialized, hand-coded parsers. The author also noted that future work should focus on "lexical access"—how the system retrieves words from a dictionary—suggesting that tree-structured lexicons could improve performance.
MCHART concludes with a call to the AI community to move away from "re-inventing the wheel" and toward building upon shared, modular frameworks to collectively advance the field of natural language understanding.
Summary updated