Introduction
Jason Eisner’s 1995 paper is a landmark in computational linguistics, providing a robust solution to the efficiency challenges of parsing with Combinatory Categorial Grammar (CCG). By introducing a "normal-form" parsing technique, Eisner successfully eliminated spurious ambiguity—a phenomenon where a single semantic interpretation is represented by multiple, redundant syntactic derivations.
The Challenge of Spurious Ambiguity
CCG is prized for its flexibility, allowing categories to combine in various orders to handle complex linguistic structures like coordination and extraction. However, this flexibility is a double-edged sword. In a standard CCG, a simple sentence like "John likes Mary" can be parsed as [John [likes Mary]] or [[John likes] Mary]. Both result in the same semantic meaning, but the parser must track both paths.
As sentences grow longer, the number of these redundant paths explodes, following a Catalan series. A complex noun phrase can generate hundreds of distinct parse trees for just a few semantic readings. Previous solutions were often either incomplete (missing valid parses) or computationally expensive, requiring the parser to perform complex semantic comparisons at every step.
Methodological Solution: Normal-Form Constraints
Eisner’s breakthrough was a purely syntactic approach. Instead of semantic checking, he defined a Normal Form (NF)—a canonical way to construct any given constituent.
Rule-Based Constraints
The core of the method lies in declarative constraints. For instance, Rule (7) prevents a constituent created by "forward composition" from immediately serving as the left-hand argument of another forward composition. This constraint forces the parser into a specific, predictable branching structure, typically preferring right-branching for forward chains.
Category Tagging
To implement these constraints efficiently, Eisner proposed "tagging" CCG categories. Categories are marked with suffixes like -FC (Forward Composition), -BC (Backward Composition), or -OT (Other). The grammar rules are then restricted to only allow specific tag combinations, effectively hard-coding the normal-form logic into the parser's basic operations.
Key Insights: Systematic Ambiguity
Eisner observed that spurious ambiguity is not random; it arises systematically from associative "chains" of categories (e.g., $A/B, B/C, C/D$). Because these chains follow predictable mathematical patterns, they can be tamed through structural restrictions.
By treating a parse tree as a "static recipe" for meaning, Eisner’s parser practices "birth control" for constituents. It prevents redundant structures from ever being created in the chart, transforming an exponential-time search into a polynomial-time process.
Results and Impact
The proposed normal-form parser is both safe (it never loses a valid reading) and complete (it eliminates all spurious redundancy). In practical tests on "nightmare" sentences, the parser reduced the search space from 252 possible parses down to just 2.
Crucially, detecting violations of these constraints adds only a constant-time overhead to the parsing process. This made Eisner’s method significantly faster and more practical than any contemporary alternative. It was the first comprehensive normal-form result for a categorial formalism with power beyond context-free grammars.
Summary updated