Abstract
This paper presents a computationally efficient parser for Combinatory Categorial Grammar (CCG) designed to reflect human psycholinguistic constraints. By integrating a simple incremental scan-combine algorithm with a formal rewrite system, the parser maintains "maximally incremental" analyses while efficiently reconfiguring tree structures to accommodate late-arriving modifiers. The system addresses the challenge of spurious ambiguity in CCG and demonstrates that structural flexibility can be managed without exponential complexity.
Introduction
Human language processing is remarkably rapid and incremental; listeners resolve linguistic ambiguities almost as soon as words are perceived. Modeling this behavior computationally using Combinatory Categorial Grammar (CCG) presents a significant challenge. While CCG’s flexible, non-constituent structures (e.g., grouping a subject and verb before an object) align well with human incrementality, they also lead to "spurious ambiguity." A single sentence can yield hundreds of derivation trees that are semantically identical, potentially overwhelming standard parsers. This research seeks to develop a "simplest parser" that mimics human cognitive limits while navigating CCG’s structural flexibility.
Methods: The Simplest Parser
The proposed architecture rests on three pillars: a scan-combine algorithm, a viable analysis criterion, and a formal rewrite system.
Scan-Combine and Viable Analysis
The parser employs a basic shift-reduce style "scan-combine" algorithm. It scans words sequentially and attempts to combine them with preceding constituents based on CCG rules. To prevent the search space from exploding, the author introduces the Viable Analysis Criterion. Rather than relying on complex look-ahead tables, this criterion suggests that humans learn to prune "dead-end" category sequences through experience, acting as a statistical filter for garbage analyses.
The Formal Rewrite System
A core conflict in incremental parsing is the need for left-branching trees (to maintain incrementality) versus right-branching trees (to attach late modifiers like adverbs). To resolve this, the author introduces a formal rewrite system that "rotates" internal derivation structures without backtracking.
This system ensures that the parser can maintain a preferred incremental analysis while remaining capable of restructuring when necessary. The underlying grammar follows standard CCG combination rules, which provide the formal basis for these structural merges.
Key Insights and Results
The paper provides several theoretical and algorithmic breakthroughs:
- Parsimony as a Design Goal: The author argues that the human parser should not be more complex than the grammar it uses. The parser acts as a generic search algorithm for CCG.
- Computational Efficiency: The author proves the rewrite system is Strongly Normalizing and Church-Rosser. This implies that regardless of the order in which rewrite rules are applied, the parser will always reach a unique "normal form" tree in a finite number of steps.
- Complexity Proofs: The sequence of rule applications is at most quadratic ($n(n-1)/2$) relative to the number of nodes. Furthermore, an optimal strategy (applying rules closest to the root) reduces this to linear complexity ($O(n)$).
- Psycholinguistic Alignment: The model successfully accounts for why certain "garden path" sentences (e.g., "The flowers sent for the patient arrived") do not cause processing errors in humans, as the interpreter uses semantic information to prune parallel analyses maintained by the scan-combine algorithm.
Limitations and Future Work
While the model is robust, it does not yet address how humans recover from total parse failures (true "garden path" errors). Additionally, the "Viable Analysis Criterion" requires testing against broad-coverage CCG grammars to determine if the $n$-gram learning approach scales to real-world language. Future research will also focus on refining the parser's handling of "endocentric" categories on the right frontier to ensure completeness in complex reanalyses.
Summary updated