Introduction
In the mid-1980s, the development of natural language (NL) interfaces was hindered by a fundamental trade-off: portability versus sophistication. Developers typically chose between semantically-based grammars—which are easy to build for specific domains but difficult to port—and syntactically-based grammars, which offer portability but suffer from massive syntactic ambiguity. General-purpose English grammars can produce hundreds or even thousands of valid parses for a single sentence, leading to a "combinatorial explosion" that makes exhaustive search impractical for interactive systems.
This paper introduces Astro, a best-first chart parser designed for the "Lingo" NL interface project. Astro navigates this complexity by combining Combinatory Categorial Grammars (CCG) with a heuristic, agenda-driven search, demonstrating that a linguistically principled parser can be fast enough for real-world applications.
The Astro Architecture
The Astro parser is built on several key technical pillars designed to balance linguistic power with computational efficiency.
Combinatory Categorial Grammar (CCG)
Unlike standard phrase-structure grammars, CCG handles complex linguistic phenomena—such as coordination and "wh-questions"—elegantly using a small set of rules. This allows the grammar to remain compact while maintaining high expressive power.
Best-First Chart Parsing
To avoid the pitfalls of exhaustive search, Astro employs a prioritized agenda. Instead of exploring every possible rule application (breadth-first) or following a single path to completion (depth-first), the system always executes the "best" action first based on a heuristic score. This allows the parser to focus on the most likely interpretations while suspending less promising paths.
Efficient Graph Unification
Astro represents linguistic features as graphs. Since full graph unification is computationally expensive, the system uses a "porous," non-destructive check function. This preliminary test determines if a rule might succeed before committing to the resource-intensive process of full unification.
Optimization Techniques
Beyond its core architecture, Astro introduces specific mechanisms to prune the search space and improve performance.
Heuristic Scoring
The agenda is ordered by a heuristic function that incorporates several factors:
- Span Length: Favoring longer phrases that cover more of the input.
- Rule Priorities: Intrinsic weights assigned to specific grammar rules.
- Statistical Likelihood: Incorporating the probability of certain word senses.
Extended Sister Relation
Unary rules (rules with a single child) are a common source of inefficiency because they can trigger in many contexts. Astro utilizes a novel "extended sister relation" to prune these "promiscuous" rules. By pre-calculating which types of phrases are permitted to appear adjacent to one another, the system can discard useless unary rule applications before they clutter the chart.
Evaluation and Insights
While the paper predates modern benchmarks like the Penn Treebank, it validates its approach through internal testing within the MCC Lingo project and references to earlier "Wizard-of-Oz" experiments that highlighted the extreme ambiguity of natural language.
The author reports an "overwhelming performance improvement" when transitioning from a non-selective, bottom-up design to the best-first approach. Furthermore, the parser's flexibility allows it to be "toggled" between finding a single "best" parse for end-users and exhaustive enumeration for grammar developers.
Conclusion and Future Work
Astro demonstrates that the agenda-driven control structure is a critical component for practical NL interfaces. However, several challenges remain. The current heuristic functions are hand-tuned through trial and error, suggesting a need for automated "credit assignment" schemes where the system learns to adjust its weights based on performance. Additionally, future work will explore better integration of local versus global context and real-time "cascading" designs that feed parsing results directly into semantic and pragmatic components.
Summary updated