Phrase Structure Grammars and Natural Languages

Gerald Gazdar

Introduction

In the early 1980s, Gerald Gazdar published "Phrase Structure Grammars and Natural Languages," a seminal work that challenged the foundational assumptions of generative linguistics. Since the late 1950s, the linguistic community—led by Noam Chomsky—largely operated under the assumption that natural languages (NLs) were "context-sensitive" and could not be adequately described by context-free grammars. This assumption led to the development of Transformational Grammars, which, while mathematically powerful, are computationally intractable. Gazdar’s paper re-evaluates this stance, arguing that context-free phrase structure grammars (CF-PSGs) are both linguistically sufficient and computationally advantageous for artificial intelligence.

The Problem: Computational Intractability

The prevailing view was that simple phrase structure grammars could not account for complex linguistic phenomena like subject-verb agreement or long-distance dependencies (e.g., "Who do you think Felix said..."). Transformational Grammars addressed these by positing "movements" between deep and surface structures. However, these models often resulted in NP-hard or even undecidable parsing problems, creating a significant rift between theoretical linguistics and computational AI. Gazdar addresses this gap by questioning whether the proofs of context-free inadequacy were empirically sound or mathematically misunderstood.

Methodology: Enhancing Notation without Increasing Power

Gazdar employs Formal Language Theory to demonstrate that CF-PSGs can be made more expressive through better notation without increasing their underlying mathematical power. He introduces three primary notational devices:

  1. Complex Symbols (Features): Instead of atomic labels like NP or VP, he uses symbols with internal structure (e.g., NP[PLUR]) to handle features like number or gender.
  2. Rule Schemata: Templates that allow a single statement to represent a large set of related rules, particularly useful for coordination.
  3. Metarules: Functions that take existing grammar rules as input and generate new ones, such as automatically generating passive-voice rules from active-voice ones.
Extracted figure from page 3 of Phrase Structure Grammars and Natural Languages

Key Insights: The "Invalidity" of Previous Proofs

A core contribution of the paper is the systematic deconstruction of famous arguments against context-free languages. Gazdar argues that previous "proofs"—such as those involving Mohawk noun incorporation or English comparative clauses—either relied on flawed data or failed to mathematically prove that the resulting string sets were non-context-free. He posits that by using "slash categories," one can represent unbounded dependencies within a monostrata (single-level) representation, where the surface structure itself provides all the information needed for semantic interpretation.

Results: Handling Unbounded Dependencies and Agreement

Gazdar demonstrates that "slash categories" (e.g., S/NP, indicating a sentence missing a noun phrase) allow for the elegant handling of topicalization and wh-questions without requiring movement transformations.

Figure 1: A phrase structure tree utilizing slash categories (S/NP, VP/NP) to represent an unbounded dependency in the sentence "that kennel Sandy thinks Felix destroyed."

Furthermore, the "Head Feature Convention" allows for subject-verb agreement to be handled via simple feature-passing mechanisms. These methods maintain the $O(n^3)$ complexity of context-free parsing, offering a "much brighter" prospect for interaction between AI and theoretical linguistics by utilizing efficient, well-understood parsing algorithms like Earley or CKY.

Conclusion

While Gazdar does not claim to have definitively proven that all natural languages are context-free, he successfully argues that there is no compelling evidence to the contrary. By returning to context-free foundations, linguists can bridge the gap between formal theory and computational implementation. This work laid the groundwork for Generalized Phrase Structure Grammar (GPSG), a major movement that prioritized computational tractability in linguistic modeling.

Summary updated

BibTeX
@inproceedings{gazdar1983phrase,
  author = {Gerald Gazdar},
  title = {{Phrase Structure Grammars and Natural Languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1983},
}
Figure