The Semantics of Grammar Formalisms Seen as Computer Languages

Fernando C. N. Pereira, Stuart M. ShieberCOLING 1984

TL;DR

This paper proposes viewing grammar formalisms for natural language processing as a special case of computer languages. By applying denotational semantics, the authors provide a rigorous mathematical framework for understanding these formalisms, leading to a unified view of feature systems and suggesting new operations for linguistic analysis.

What Problem Does This Paper Address?

Computational linguistics has developed numerous grammar formalisms for natural language processing. However, the design and understanding of these formalisms have often relied on informal explanations, examples, and implementation details, rather than precise mathematical specifications. This lack of rigor leads to confusion, wasted effort, and difficulty in comparing different formalisms. The paper argues that by treating grammar formalisms as computer languages, we can leverage established techniques like denotational semantics to provide clear, compositional, and mathematically sound definitions of their meaning. This approach aims to bridge the gap between linguistic intuition and formal rigor, similar to how denotational semantics clarified programming language design.

Methods

The core of the paper's methodology is the application of denotational semantics, specifically domain theory pioneered by Scott and Strachey.

  • Domain Theory: This mathematical framework is used to model the meaning of programming language constructs as partial functions between abstract data objects. The paper adapts this to model feature structures and descriptions used in grammar formalisms.
  • Information Systems: The authors use Scott's information systems approach to construct the domain of feature structure descriptions. This involves defining propositions (equations), consistency, entailment, and deductive closure to formally capture partial information.
  • Feature Structures and Descriptions: The paper defines feature structures as partial functions from labels (features) to values. Descriptions are then introduced as sets of equations that constrain these feature structures. The domain of descriptions, denoted by D, is built using information systems.
  • Grammar Formalism Semantics: For grammar formalisms, the paper defines a domain Pk representing transduction relations (associations between strings and their descriptions). Rules are then given denotations as mappings from Pk to Pk, which combine string-description pairs through concatenation and unification. The overall grammar denotation is the least fixed point of these rule denotations, applied in parallel.

The approach is novel in its systematic application of denotational semantics to grammar formalisms, moving beyond ad-hoc definitions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Grammar Formalisms as Computer Languages: This core idea allows leveraging decades of research in programming language semantics for linguistics.
  • Unified View of Feature Systems: The paper shows that feature systems in GPSG, LFG, and PATR-II are special cases of a single, abstract construction based on domain theory.
  • Feature Generalization: A key mathematical operation, feature generalization (greatest-lower-bound on descriptions), is identified. This operation is not explicitly available in many current formalisms but is shown to be useful for modeling linguistic phenomena like coordination.
  • Distinction Between Feature Structures and Descriptions: The paper emphasizes the importance of distinguishing between the actual data objects (feature structures) and the partial information used to constrain them (descriptions). This distinction is often blurred in existing literature and can lead to ambiguities.
  • Compositionality and Rigor: Denotational semantics provides a compositional way to define the meaning of grammar constructs, ensuring that the meaning of a whole is derived from the meanings of its parts through well-defined operations.

Key Results

  • A formal, denotational semantics is provided for a simple grammar formalism, demonstrating the applicability of the approach.
  • The mathematical structures developed for feature systems reveal an operation of feature generalization, which the authors suggest can partially account for the effect of coordination on syntactic features.
  • The paper shows that feature systems in GPSG, LFG, and PATR-II can be unified under a single abstract construction derived from domain theory.
  • The approach offers a rigorous way to define unification, instantiation, and generalization, fundamental operations in many grammar formalisms.

Limitations and Future Work

  • Complexity of Domain Theory: The paper acknowledges that domain theory is mathematically complex, but argues its benefits (inherent partiality, technical economy, suggestiveness, extensibility) outweigh the complexity, especially for formalisms dealing with partial information.
  • Focus on Equational Constraints: The current work primarily deals with simple equational constraints. Future work is planned to extend the approach to handle negative and disjunctive constraints.
  • Modeling Coordination: While generalization is shown to help model coordination, the paper suggests that further work might be needed to fully model phenomena like number agreement in coordinated noun phrases.
  • Broader Applicability: The authors express optimism that this approach can be extended to analyze a wider range of grammar formalisms and linguistic phenomena, potentially leading to a higher standard of research in computational linguistics.

Summary updated

BibTeX
@inproceedings{pereira1984semantics,
  author = {Fernando C. N. Pereira and Stuart M. Shieber},
  title = {{The Semantics of Grammar Formalisms Seen as Computer Languages}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}

Loading related content...

Figure