Efficient Normal-Form Parsing for Combinatory Categorial Grammar

Jason Eisner

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.

Figure 2: CCG parses illustrating standard derivations (a, c) and the blocking of redundant structures (b) via normal-form constraints.

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.

Figure 4: Different syntactic bracketings (a, b) of an associative chain that result in the same semantic lambda expression (c).

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

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.
BibTeX
@inproceedings{eisner1996efficient,
  author = {Jason Eisner},
  title = {{Efficient Normal-Form Parsing for Combinatory Categorial Grammar}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1996},
  url = {https://openreview.net/forum?id=ryE3soeubS},
}
Figure