A Grammar Formalism and Parser for Linearization-based HPSG

Michael W. Daniels, W. Detmar MeurersCOLING 2004

TL;DR

This paper introduces GIDLP, a novel grammar formalism designed to efficiently handle languages with flexible word order, a common challenge in linguistics. They also present a parser that leverages GIDLP's explicit encoding of word order constraints, significantly reducing parsing complexity compared to traditional methods.

What Problem Does This Paper Address?

Many languages, like German, exhibit relatively free constituent order, meaning words can appear in various positions without changing the sentence's core meaning. Traditional phrase structure grammars struggle with this, often requiring an explosion of rules to account for all possible word order permutations. Linearization-based Head-Driven Phrase Structure Grammar (HPSG) approaches attempt to address this by separating word order constraints from the basic syntactic structure, allowing these constraints to operate over domains larger than just local tree structures. However, existing grammar formalisms and parsers haven't adequately supported direct encoding and efficient processing of these linearization-based HPSG theories, leading to either inefficient parsing or a lack of robust word order constraint handling.

Methods

The core contribution is the Generalized ID/LP (GIDLP) grammar format. GIDLP extends traditional Immediate Dominance/Linear Precedence (ID/LP) grammars by explicitly encoding:

  • Dominance: The hierarchical structure of constituents.
  • Precedence: Linear ordering constraints between elements.
  • Linearization Domain Information: Crucially, GIDLP allows these order domains to extend beyond local trees, capturing discontinuous constituents and flexible word order.

Key features of GIDLP include:

  • Compaction Statements: These define how daughter domains combine into larger domains. "Contiguity" ensures a compacted domain covers a single, unbroken stretch of terminals, while "LP Locality" restricts precedence constraints to elements within the same compacted domain, acting as a barrier.
  • Rule-Level and Global Constraints: Precedence and compaction constraints can be specified for individual rules or globally across the grammar.

The paper also presents a parser based on Earley's algorithm, adapted for GIDLP. The novelty lies in how it integrates GIDLP's word order constraints directly into the parsing process:

  • Bitvectors for Coverage: To handle discontinuous constituents, edge coverage is represented using bitvectors instead of simple start/end positions.
  • Negative and Positive Masks (n-mask, p-mask): These bitvectors are added to parser edges. The n-mask restricts where subsequent constituents can be placed, while the p-mask encodes mandatory positions based on immediate precedence constraints. This allows the parser to prune invalid parses early, rather than using a generate-and-test approach.

Datasets

Not discussed in the paper. The paper uses example sentences for illustration and evaluation, but no formal datasets are described.

Key Insights and Ideas

  • Explicit Domain Handling is Key: The ability to define and constrain "order domains" that can span across local tree boundaries is fundamental to efficiently handling free word order.
  • Compaction as a Barrier: The concept of "LP Locality" through domain compaction is a powerful mechanism. It prevents precedence constraints from "leaking" into unrelated parts of the structure, simplifying constraint management.
  • Integrating Constraints into Parsing: Instead of treating word order as a post-processing step, GIDLP and its parser embed these constraints directly into the parsing engine. This allows for significant efficiency gains by pruning the search space early.
  • Bitvectors for Discontinuity: Representing coverage with bitvectors is an elegant solution to the problem of discontinuous constituents in parsing algorithms.

Key Results

The paper demonstrates the effectiveness of GIDLP and its parser through an example grammar for a fragment of German.

  • Rule Reduction: A GIDLP grammar with 10 syntactic rules was compared to a flattened CFG equivalent. The CFG required 201 rules to handle a limited case (two adverbs), highlighting the combinatorial explosion GIDLP avoids.
  • Parsing Efficiency: In an experiment with four sample sentences, the GIDLP parser generated 89% fewer active edges compared to a standard CFG/Earley parser. While the GIDLP parser was slower in this specific instance (attributed to atomic categories), the authors expect it to be faster for full HPSG feature structures due to the reduced edge count.

Limitations and Future Work

  • Atomic Categories: The current parser implementation uses atomic categories, which impacts performance. Future work will focus on optimizing for HPSG's rich feature structures.
  • Further Optimization Techniques: The authors plan to explore additional techniques for optimized parsing.
  • Application to Feature-Based Grammars: The ultimate goal is to apply the parser to full HPSG grammars.
  • Generalization: The paper aims to encourage research into general optimizations for linearization-based HPSG processing.

Summary updated

BibTeX
@inproceedings{daniels2004grammar,
  author = {Michael W. Daniels and W. Detmar Meurers},
  title = {{A Grammar Formalism and Parser for Linearization-based HPSG}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2004},
}
Figure