How to Cover a Grammar

René LeermakersACL 1989 · DOI

Introduction

Parsing natural language is a foundational challenge in computational linguistics, complicated by the inherent ambiguity and structural complexity of human speech. Historically, the field has been divided into several distinct algorithmic "camps": chart parsers (such as Earley or CYK), LR-parsers (like Tomita’s), and automata-based methods (such as Lang’s simulation of non-deterministic pushdown automata). While these methods were developed independently, René Leermakers argues that this fragmentation obscures the fundamental logic of parsing. This paper introduces a unified formalism, demonstrating that these popular algorithms are variations of a single underlying strategy: transforming a general grammar into a bilinear cover and solving it with a generalized $O(n^3)$ parser.

The Unified Framework: Bilinear Covers and the C-Parser

The author proposes that parsing any context-free language can be distilled into a two-step process:

  1. Bilinear Transformation: A general grammar $G$ is transformed into a bilinear grammar $C(G)$. A grammar is bilinear if the right-hand side of every production rule contains at most two non-terminals. This serves as a generalization of the Chomsky Normal Form (CNF).
  2. The C-Parser: A generalized version of the CYK algorithm, termed the "C-Parser," is applied to this bilinear grammar. Because the grammar is bilinear, the C-Parser is guaranteed to operate in cubic time ($O(n^3)$) relative to the length of the input string.

The core innovation of this framework is the concept of a "cover." A grammar $C(G)$ is considered a cover for $G$ if it generates the same language and provides a mapping that allows for the reconstruction of the original parse trees. This perspective reveals that the primary difference between famous parsing algorithms is not their computational power, but rather how and when they construct this bilinear cover.

Reconciling Classical Algorithms

Leermakers demonstrates the flexibility of the cover framework by showing how it encompasses existing methods:

  • Earley’s Algorithm: This algorithm is essentially a method for generating a bilinear cover dynamically (on the fly) during the parsing process.
  • Tomita’s LR-Parser: This approach generates a bilinear cover statically, utilizing an LR(0) state machine to define the cover's structure before parsing begins.
  • Lang’s Algorithm: This method is shown to be a bilinear cover derived directly from the transitions of a non-deterministic pushdown automaton (NPDA).

To illustrate these theoretical connections, the paper utilizes a hand-crafted grammar of Dutch subordinate clauses. This example demonstrates how different covers—such as Earley versus Canonical Non-deterministic LR (CNLR)—represent identical linguistic structures through different formalisms.

The Canonical Non-deterministic LR-Parser (CNLR)

A significant contribution of the paper is the introduction of the Canonical Non-deterministic LR-parser (CNLR). By using LR(0) states to create a bilinear cover, the CNLR parser often results in a representation that is significantly smaller than the set of items produced by an Earley parser for practical natural language grammars.

Furthermore, the author addresses specific technical hurdles in LR-parsing. For instance, the paper provides a formal proof that the CNLR parser can handle cyclic grammars (where a symbol can derive itself), resolving a limitation previously associated with Tomita's original work. Additionally, the paper formalizes the use of "predict" functions to prune the parse matrix, allowing the parser to bypass sections of the grammar that cannot match the remaining input, thereby enhancing real-world performance.

Key Results and Complexity

The paper establishes several critical theoretical results:

  • Unified Complexity: Non-deterministic LR-automata are proven to be general parsers for all context-free grammars with an $O(n^3)$ complexity, matching the Earley algorithm.
  • Formal Equivalence: The paper provides a rigorous proof that Lang’s NPDA simulation is functionally equivalent to a restricted C-Parser acting on a specific bilinear grammar.

Limitations and Future Directions

Despite the elegance of the unified theory, certain practical challenges remain. While the CNLR cover is efficient for many grammars, the number of LR(0) states can, in the absolute worst case, grow exponentially relative to the grammar size (unlike Earley items, which grow linearly).

Additionally, the "space of bilinear covers" is vast. Identifying the optimal cover to minimize average-case parsing time for a specific grammar remains an open research question. Finally, the author notes that extending this bilinear theory to handle attribute grammars—which incorporate complex feature constraints used in production systems like the Rosetta translation system—is a necessary step for the framework to support modern, feature-rich linguistic models.

Summary updated

BibTeX
@inproceedings{leermakers1989how,
  author = {René Leermakers},
  title = {{How to Cover a Grammar}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1989},
  doi = {10.3115/981623.981640},
}
Figure