Syntactic and Semantic Parsability

Geoffrey K. PullumCOLING 1984

This paper explores the intricate relationship between syntactic structure, semantic meaning, and the computational challenges of parsing natural languages. It argues that while context-free grammars (CFGs) are a useful starting point, a complete understanding of natural language requires considering semantic filtering and potentially more powerful grammatical formalisms.

TL;DR

This paper investigates the computational complexity of natural language parsing, arguing that semantic considerations are crucial and that context-free grammars may not be sufficient. It explores the implications of languages potentially being non-context-free and proposes more powerful grammatical frameworks, highlighting the ongoing debate about the formal underpinnings of human language.

What Problem Does This Paper Address?

The paper tackles the fundamental question of how to computationally represent and process natural languages (NLs). Traditionally, parsing has been viewed as a syntactic task, analyzing sentences into their constituent parts. However, the author argues that semantic motivations always underlie this process, meaning that understanding meaning is inseparable from parsing. This leads to a deeper inquiry: what are the formal language-theoretic properties of NLs, and what are the implications for parsing algorithms? Specifically, the paper questions whether NLs are regular sets, context-free languages (CFLs), or deterministic context-free languages (DCFLs), and what happens if they are not. It also examines how semantic filtering can affect the expressive power of grammars and explores more powerful grammatical formalisms beyond CFGs.

Methods

The paper employs a theoretical and analytical approach, drawing heavily on formal language theory and computational linguistics. Key methods include:

  • Distinguishing Parsing Types: The author clearly defines different types of parsing algorithms: recognition (membership), parsing (syntactic analysis), and translation (semantic representation). Crucially, it distinguishes between "all-paths parsers" (yielding all possible analyses) and "one-path parsers" (yielding a single analysis), which is vital for understanding ambiguity.
  • Language Classifications: The paper delves into established language classes like regular sets, context-free languages (CFLs), and deterministic context-free languages (DCFLs), discussing their properties and limitations in modeling NLs.
  • Theoretical Arguments: It presents theoretical arguments, often based on set theory and formal language properties (like closure under intersection), to demonstrate why certain NL phenomena might push languages beyond the CFL class.
  • Exploration of Grammatical Frameworks: The paper surveys and discusses various grammatical formalisms, including context-free phrase structure grammars (CF-PSGs), head grammars, and unification grammars, evaluating their expressive power and computational tractability.
  • Semantic Filtering: A core concept explored is "semantic filtering," where semantic rules prune syntactically generated but semantically nonsensical structures, thereby altering the effective language defined by the grammar.

Datasets

Not discussed in the paper. The paper is primarily theoretical and analytical, using linguistic examples and hypothetical constructions rather than empirical datasets for training or evaluation.

Key Insights and Ideas

  • Semantics Drives Syntax: The paper strongly asserts that parsing is never purely syntactic; semantic goals are always the underlying motivation. This means that understanding how humans derive meaning is crucial for building effective parsers.
  • Ambiguity is Not Necessarily Non-DCFL: While ambiguity is a hallmark of NLs, the paper clarifies that an ambiguous grammar does not automatically mean a language is not a DCFL. A DCFL can be generated by an ambiguous grammar, and a deterministic parser can still be developed for it.
  • Non-Context-Freeness is Plausible: The paper presents compelling theoretical arguments and linguistic examples (e.g., from Moru, Bambara, and Swiss German) that suggest some natural languages might indeed be non-context-free. This challenges the long-held assumption that all NLs are CFLs.
  • Semantic Filtering Enhances Power: The concept of semantic filtering is shown to be a powerful mechanism. By using semantic rules to reject syntactically generated strings, a grammar can effectively define a language with greater expressive power than its underlying syntactic rules alone would suggest, potentially even non-CFLs from CFGs.
  • Beyond CFGs: Head Grammars and Others: The paper introduces and discusses more powerful grammatical formalisms like head grammars, which offer greater expressive power than CFGs but are still computationally tractable, suggesting they might be better suited for certain linguistic phenomena.
  • The "Garden Path" Phenomenon: The paper connects the theoretical concept of one-path vs. all-paths parsers to the psychological phenomenon of "garden-path sentences," where human parsing can fail in ways analogous to deterministic parsers.

Key Results

  • English as a CFL/DCFL is Open: The paper argues that it has not been definitively proven that English is not a CFL, and the question of whether it is a DCFL has not been adequately addressed.
  • Bambara as a Potential Non-CFL: The paper highlights ongoing research suggesting that languages like Bambara, with complex reduplication and compounding, may exhibit non-context-free properties.
  • Head Grammars as a Tractable Alternative: Head grammars are presented as a formalism with greater expressive power than CFGs but with a computationally manageable recognition problem (polynomial time, albeit with a high exponent).
  • Semantic Filtering Can Create Non-CFLs: A formal example demonstrates how semantic filtering applied to a CFG can result in a language that is not context-free.

Limitations and Future Work

  • Lack of Definitive Proof for Non-CFL NLs: While strong arguments are presented, the paper acknowledges that definitive, published demonstrations of NLs being non-CFL are still emerging.
  • Formalizing Reduplication: The paper identifies the need for formalisms that directly capture "repeat the morpheme-string" operations, suggesting current approaches (semantic filtering, head grammars) might not be the most intuitive or linguistically accurate for phenomena like Bambara noun reduplication.
  • Evaluating Grammatical Frameworks: The author expresses a need for a unified, implemented formalism that can rigorously compare the expressive power and computational tractability of various proposed grammars (head grammars, LFG, unification grammars, etc.) to avoid subjective claims about their superiority.
  • Psycholinguistic Implications: The paper touches upon the connection between computational parsing models and human language processing (e.g., garden-path sentences) but suggests further exploration is needed.
  • Future Research Directions: The paper points towards continued investigation into the formal properties of NLs, the development of more powerful yet tractable grammatical frameworks, and the integration of semantic and syntactic processing.

Summary updated

BibTeX
@inproceedings{pullum1984syntactic,
  author = {Geoffrey K. Pullum},
  title = {{Syntactic and Semantic Parsability}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}
Figure