Abstract
Under categorial grammars that have powerful rules like composition, a simple n-word sentence can have exponentially many parses. Generating all parses is inefficient and obscures whatever true semantic ambiguities are in the input. This paper addresses the problem for a fairly general form of Combinatory Categorial Grammar, by means of an efficient, correct, and easy to implement normal-form parsing technique. The parser is proved to find exactly one parse in each semantic equivalence class of allowable parses; that is, spurious ambiguity (as carefully defined) is shown to be both safely and completely eliminated.
Introduction
Combinatory Categorial Grammar (CCG) is a powerful formalism for natural language processing, particularly effective at modeling complex linguistic phenomena like coordination and extraction. However, its flexibility introduces a significant computational challenge: spurious ambiguity. This occurs when multiple syntactic derivations result in the same semantic interpretation. In many cases, the number of possible parses for a single sentence grows exponentially with sentence length, even when only a few distinct meanings exist.
The Challenge of Spurious Ambiguity
The core of the problem lies in the associative nature of CCG's composition rules. For instance, a sequence of categories can often be combined in multiple orders—such as left-branching versus right-branching—without altering the final semantic output. This redundancy forces parsers to perform unnecessary work, exploring hundreds or thousands of equivalent paths. A notable example cited in the research involves a sentence that yields 252 distinct parses, despite having only two valid semantic readings. This "spuriousness" is not merely a nuisance; it represents a fundamental efficiency bottleneck for CCG-based systems.
Normal-Form Parsing Methodology
To address this, the author introduces a normal-form parsing technique designed to prevent the generation of redundant constituents—a strategy described as "birth control" for constituents. The approach relies on two primary strategies:
- Structural Constraints for Pure CCG: For a general CCG, the author defines declarative constraints that restrict how rules can be applied. Specifically, the output of a rightward composition rule is prohibited from serving as the left argument for another rightward rule. Similarly, the output of a leftward composition rule cannot be the right argument for another leftward rule. These constraints are implemented by "tagging" categories (e.g.,
-fcfor forward composition) to block invalid combinations, effectively forcing a canonical branching structure. - Canonicalizing CKY Parser: For more restricted grammars where simple constraints might inadvertently block valid parses, a modified Cocke-Kasami-Younger (CKY) algorithm is proposed. This version computes a "Normal Form" (NF) for every constituent. By using a hash table for $O(1)$ lookups, the parser ensures that if multiple derivations produce the same NF, only one representative is retained in the chart.
Theoretical Foundations
The validity of this method is supported by two critical theorems regarding semantic equivalence, defined "intensionally" as the recipe for combining word meanings:
- Theorem 1 (Safety): The constraints are "safe," meaning they do not eliminate any unique semantic interpretations. Every valid meaning remains reachable through at least one normal-form parse.
- Theorem 2 (Completeness): The method is "complete" in its elimination of redundancy; every distinct normal-form parse corresponds to a unique semantic meaning.
Results and Impact
By enforcing these constraints, the parser reduces the search space from exponential (often following Catalan numbers) to a size exactly equal to the number of true semantic ambiguities. Because these checks can be performed in constant time during the parsing process, the algorithm maintains the standard polynomial time complexity ($O(n^3)$) typical of context-free grammar parsing, while drastically improving practical performance. In the previously mentioned case of a sentence with 252 parses, the normal-form parser correctly generates only the two unique semantic readings.
Limitations and Future Directions
While highly effective for structural ambiguity, the method has limitations. It treats type-raising primarily as a lexical property; if type-raising were allowed as a free grammatical rule, it would introduce new forms of ambiguity not covered by this specific normal form. Additionally, the method focuses on structural equivalence rather than "accidental" semantic equivalence caused by specific lexical choices (e.g., commuting adverbs). Future work might also explore how to select the most linguistically "natural" derivation among equivalent options to better reflect discourse or intonational focus.
Summary updated