A Simple Reconstruction of GPSG

Stuart M. ShieberCOLING 1986

TL;DR

This paper proposes a method to simplify the complex axiomatic system of Generalized Phrase Structure Grammar (GPSG) by translating its principles into a more manageable unification-based formalism called PATR-II. This reconstruction offers a clearer, more computationally amenable understanding of GPSG, paving the way for easier implementation and analysis of its expressive power.

What Problem Does This Paper Address?

Generalized Phrase Structure Grammar (GPSG) is a powerful linguistic theory that describes language using a set of universal and language-specific constraints. However, the axiomatic system developed in the seminal work "Generalized Phrase Structure Grammar" by Gazdar, Klein, Pullum, and Sag is notoriously complex. This complexity, while enabling rich linguistic analyses, makes the theory challenging to fully grasp and computationally implement. The authors aim to address this by finding a "simpler description" of the same theory, not by altering the linguistic claims, but by reformulating the underlying formal machinery.

Methods

The core contribution of this paper is a procedural method for compiling GPSG grammars into the PATR-II formalism. Instead of directly characterizing well-formed linguistic trees (as GPSG's axiomatic system does), the proposed method first characterizes the GPSG axioms themselves procedurally. These procedural characterizations are then translated into PATR-II rules.

The process involves several key steps, focusing on the feature instantiation principles of GPSG:

  • Immediate Dominance (ID) Rules: These are directly translated into unordered PATR rules.
  • Feature Instantiation Principles: The paper details how principles like the Control Agreement Principle (CAP), Foot Feature Principle (FFP), and Head Feature Convention (HFC) are translated. This involves carefully defining how feature values are inherited or instantiated, and crucially, how these principles interact and take precedence over each other.
  • Precedence Ordering: A significant insight is the identification of an implicit precedence ordering among GPSG's principles (e.g., CAP > FFP > HFC > FSD). This ordering is leveraged to simplify the application of constraints, allowing for sequential application rather than simultaneous checking.
  • PATR-II Formalism: The paper utilizes a unification-based grammar formalism, PATR-II, which allows for schematic representation of constraints without enumerating all ground instances. This is key to avoiding the combinatorial explosion of rules that plagued earlier compilation attempts.

The paper also briefly touches upon how Linear Precedence (LP) rules and Feature Cooccurrence Restrictions (FCRs) could be handled, though these are not fully elaborated.

Datasets

Not discussed in the paper. The paper focuses on the formal translation of linguistic theory rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Simplification through Formalism Translation: The most significant insight is that the complexity of GPSG's axiomatic system can be substantially reduced by translating it into a more computationally tractable formalism like PATR-II. This doesn't diminish GPSG's linguistic power but makes it more accessible.
  • The Power of Precedence Ordering: Identifying and leveraging the implicit precedence ordering among GPSG's principles is crucial. This allows for a sequential application of constraints, mirroring the "blindness" of earlier principles to later ones, which simplifies the overall system.
  • Unification as a Core Mechanism: The paper highlights the suitability of unification-based formalisms for representing linguistic constraints schematically, avoiding the need to generate all possible instantiations of rules.
  • A Path to Computational Implementation: By providing a clear compilation method into PATR-II, the paper offers a concrete step towards the computational implementation of GPSG, which is often a bottleneck for complex linguistic theories.
  • Measuring Expressiveness: The ease or difficulty of encoding GPSG devices in PATR-II can serve as a measure of their expressiveness and indispensability within the GPSG framework.

Key Results

The paper presents a procedural algorithm for compiling GPSG grammars into PATR-II. While no quantitative results (like accuracy improvements or speedups) are provided, the key result is the demonstration that such a compilation is possible and leads to a simpler, more defined, and computationally amenable representation of GPSG. An example demonstrates the translation of a specific GPSG ID rule and the application of several feature instantiation principles within the PATR-II framework.

Limitations and Future Work

The authors acknowledge several limitations and suggest avenues for future research:

  • LP Rules and FCRs: The paper does not fully detail the compilation of Linear Precedence (LP) rules and Feature Cooccurrence Restrictions (FCRs). Two possibilities for LP rules are discussed (run-time vs. compile-time interpretation), and for FCRs, modifications to the category lattice or checking at each step are suggested.
  • Ordering of HFC and CAP: A potential paradox is identified regarding the ordering of the Head Feature Convention (HFC) and the Control Agreement Principle (CAP). The HFC might need to apply before the CAP for semantic type determination, but the CAP might need to apply after the HFC for feature instantiation. This could lead to an ordering cycle or inadmissibility of local sets of nodes, a problem left open for resolution.
  • Complex FSDs: The paper assumes simple default values for features, whereas Gazdar et al. use more complex boolean conditions. Modifications for these complex FSDs are noted as potentially straightforward but not fully explored.
  • Implementation: The algorithm presented has not yet been implemented.
  • Further Exploration of Expressiveness: The authors suggest that analyzing the compilation process can provide insights into the expressiveness and necessity of various GPSG devices.

Summary updated

BibTeX
@inproceedings{shieber1986simple,
  author = {Stuart M. Shieber},
  title = {{A Simple Reconstruction of GPSG}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1986},
}
Figure