An Earley Parsing Algorithm for Range Concatenation Grammars

Laura Kallmeyer, Wolfgang Maier, Yannick ParmentierACL 2009

TL;DR

This paper introduces novel CYK and Earley parsing algorithms for Range Concatenation Grammars (RCGs), a powerful formalism for describing complex linguistic phenomena. By employing a "parsing as deduction" framework and a clever "constraint propagation" technique, their Earley parser significantly reduces the number of intermediate parsing states, leading to more efficient parsing.

What Problem Does This Paper Address?

Natural language is incredibly complex, with phenomena like long-distance scrambling and intricate grammatical structures that go beyond the capabilities of simpler grammar formalisms like context-free grammars. Range Concatenation Grammars (RCGs) offer a more expressive power, capable of handling these challenging linguistic features. However, efficiently parsing sentences with RCGs has been a significant challenge. Previous RCG parsing algorithms, while functional, could generate a very large number of intermediate parsing states, making them computationally expensive. This paper aims to address this efficiency bottleneck by developing more optimized parsing algorithms for RCGs.

Methods

The authors present two main algorithmic contributions:

  • CYK-style Algorithm: They adapt the classic CYK (Cocke-Younger-Kasami) parsing algorithm to work with RCGs. This involves defining how RCG rules are applied within the CYK chart.
  • Earley-style Algorithm: Building on the CYK approach, they introduce an Earley-style parser. The key innovation here is the use of range boundary constraint propagation. Instead of guessing all possible range boundaries for variables and terminals upfront (as in some previous approaches), this method dynamically updates and refines constraints on these boundaries as parsing progresses. This "lazy" computation of ranges is central to their efficiency gains. The algorithm is framed within the "parsing as deduction" paradigm, which provides a formal basis for the parsing steps.

Datasets

The paper evaluates their algorithms on a specific language: $L = \{a^{2^n} | n \ge 0\}$. This language is used as an example of a non-semilinear language that RCGs can generate, highlighting the expressive power of the formalism. No other specific linguistic datasets are mentioned for evaluation.

Key Insights and Ideas

  • Constraint Propagation is Key: The most significant insight is that dynamically updating and propagating constraints on range boundaries, rather than pre-computing all possibilities, dramatically reduces the parsing complexity. This "late binding" of range information is crucial for efficiency.
  • RCGs are Powerful but Demanding: The paper underscores the expressive power of RCGs for capturing complex linguistic phenomena, while simultaneously highlighting the computational challenges associated with parsing them.
  • Earley's Adaptability: The Earley algorithm, known for its efficiency with context-free grammars, proves to be a suitable framework for developing optimized RCG parsers when augmented with constraint propagation.
  • "Parsing as Deduction": Framing the algorithms within this paradigm provides a principled way to derive parsing rules and ensure correctness.

Key Results

The primary result is the significant reduction in the number of generated items (parsing states) by their new Earley-style algorithm compared to a previously implemented directional top-down algorithm. For instance, when parsing the word $a^{16}$ (which corresponds to $2^4$), their Earley parser generated 100 items, while the older algorithm generated 539. This difference becomes even more pronounced for longer words, such as $a^{64}$, where the new algorithm produced 350 items versus 6969 for the older one. This demonstrates a substantial efficiency improvement.

Limitations and Future Work

The authors acknowledge that the use of constraints can make item comparisons more complex and computationally expensive. They suggest that for an efficient implementation, an integer-based representation of constraints and appropriate constraint-solving techniques are necessary.

Future work includes improving the Earley parser by allowing predicates on the right-hand side of clauses to be processed in any order, not just left-to-right. This would enable processing predicates whose range boundaries are known earlier, potentially leading to further optimizations.

Summary updated

BibTeX
@inproceedings{kallmeyer2009earley,
  author = {Laura Kallmeyer and Wolfgang Maier and Yannick Parmentier},
  title = {{An Earley Parsing Algorithm for Range Concatenation Grammars}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2009},
}
Figure