A Chart-based Method of ID/LP Parsing with Generalized Discrimination Networks

Surapant Meknavin, Manabu Okumura, Hozumi TanakaCOLING 1992

TL;DR

This paper introduces a novel chart-based parsing algorithm for languages with flexible word order (ID/LP grammars). By pre-compiling grammar rules into generalized discrimination networks (GDNs) for ID rules and Hasse diagrams for LP rules, and employing a bottom-up depth-first strategy, the authors achieve significant efficiency gains over existing methods.

What Problem Does This Paper Address?

Natural languages often exhibit significant word order variation. To handle this, grammars can be decomposed into Immediate Dominance (ID) rules (which specify the structure of constituents) and Linear Precedence (LP) rules (which specify the order of constituents). While this ID/LP formalism is elegant for describing flexible word order, efficiently parsing with it has been a challenge. Existing approaches either compile ID/LP grammars into other formalisms (like CFGs), leading to huge grammars and slow parsing, or attempt direct ID/LP parsing but face computational challenges. This paper aims to provide a direct ID/LP parsing method that is both efficient and retains the modularity of the ID/LP formalism.

Methods

The proposed method combines several key techniques:

  • Generalized Discrimination Networks (GDNs) for ID Rules: Instead of treating each ID rule separately, GDNs are used to represent commonalities between rules. This creates a compact representation of parsing states, reducing computation. GDNs allow for traversal based on incrementally obtained constraints, rather than a fixed order.
  • Hasse Diagrams for LP Rules: LP rules define a partial order. Hasse diagrams are used to represent this partial order, and precedence vectors are computed for each node. This allows for efficient checking of order legality at runtime using bitwise operations.
  • Bottom-up Depth-first Parsing Strategy: This strategy, inspired by the Word Incorporation (WI) algorithm, processes the input in an orderly fashion and completes processing at a vertex before moving on. This eliminates the need for duplicated edge checks, a significant source of overhead in traditional chart parsing.
  • Modified State Representation: The parsing state is expanded from a simple <Id, BitV> to a 4-tuple <Cat, Id, Pre, BitV> to accommodate category information, precedence vectors, and bit vectors for constraint satisfaction.

Datasets

Not discussed in the paper. The authors use a toy grammar (G1) for demonstration and comparison purposes.

Key Insights and Ideas

  • GDNs for Compactness: Representing ID rules with GDNs allows for sharing common substructures, leading to a more compact representation of parsing states compared to methods that treat each rule independently.
  • Hasse Diagrams for Efficient Order Checking: Pre-computing precedence vectors using Hasse diagrams transforms LP rule checking into efficient bitwise operations, significantly speeding up the process.
  • Bottom-up Depth-first for Eliminating Redundancy: The chosen parsing strategy inherently avoids re-processing already completed parts of the parse, eliminating the costly duplicated edge checks common in other chart parsers.
  • Integrated Approach: The power of the method comes from the synergistic combination of GDNs, Hasse diagrams, and the specific parsing strategy, rather than relying on a single novel component.

Key Results

The paper presents a comparison with Shieber's direct ID/LP parser and SDG+metarules. While specific quantitative results are presented in Figure 6, the key findings are:

  • GHW (the proposed parser) significantly outperforms Shieber's parser across various sentence lengths in terms of total parsing time.
  • For short sentences, SDG+metarules is faster at finding the first parse, but GHW surpasses it for longer sentences. This is attributed to GHW's initialization overhead, which becomes negligible for longer inputs.
  • The authors conclude that their method is more suited for parsing longer and more complicated sentences due to its efficiency gains.

Limitations and Future Work

  • Limited Grammar and Sentences: The authors acknowledge that their experiments were conducted with a toy grammar and artificial sentences. They suggest that further exploration with diverse grammars and real-world sentences is needed to confirm the effectiveness of their method.
  • Handling Ill-formed Input: Extending the parser to handle ill-formed input is identified as a direction for future work.
  • Exploration of Other Mechanisms: The authors note that other conventional chart parsing efficiency improvements could potentially be integrated into their algorithm.

Summary updated

BibTeX
@inproceedings{meknavin1992chart,
  author = {Surapant Meknavin and Manabu Okumura and Hozumi Tanaka},
  title = {{A Chart-based Method of ID/LP Parsing with Generalized Discrimination Networks}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1992},
}
Figure