A Symmetrical Approach to Parsing and Generation

Marc Dymetman, Pierre Isabelle, François PerraultCOLING 1990 · OpenReview

Introduction

In computational linguistics, achieving "reversibility"—the ability to use a single grammar for both parsing (understanding meaning from text) and generation (producing text from meaning)—remains a significant challenge. While parsing typically leverages string indices to navigate search spaces, generation lacks a direct equivalent, often resulting in inefficient search or infinite loops. Furthermore, many elegant grammar formalisms are left-recursive, causing standard top-down logic engines like Prolog to fail.

This paper introduces a unified framework where parsing and generation are treated as symmetrical processes derived from a single "Lexical Grammar." The authors propose the abstract concept of a guide—a generalized resource consumption mechanism—to transform declarative grammars into efficient, terminating programs.

Methodology: From Grammar to Program

The authors utilize Lexical Grammars (LG), a class of unification grammars where linguistic complexity is concentrated in the lexicon while structural rules remain simple and fixed. To make these grammars executable in a standard logic programming environment, they follow a multi-stage transformation process.

The transformation process from declarative Lexical Grammar rules to efficient, non-left-recursive programs.

The process begins with declarative Lexical Grammar rules (P0). By conservatively adding a parsing or generation guide, the authors derive guided programs (P1p and P1g). However, these initial programs remain left-recursive. To ensure termination and efficiency, a left-recursion elimination transformation is applied, resulting in non-left-recursive programs (P2p and P2g) that are logically equivalent to the original grammar but optimized for execution.

The Guide as a Unified Abstraction

The core innovation of this approach is the Guide. The authors argue that string indices in parsing and semantic subcategorization in generation are functionally identical: they represent a resource that must be consumed to progress toward a solution.

  • In Parsing: The guide is the list of words remaining to be analyzed. As the parser processes the input, the list shortens, ensuring the "guide-consumption condition" is met.
  • In Generation: The guide is a list of semantic structures (meanings) waiting to be expressed.
Illustration of the parsing guide being consumed as the sentence 'mary often visited notre dame' is processed.

By proving that the guide strictly decreases in size after every lexical access, the authors provide a formal guarantee of termination. This symmetry allows the same underlying algorithm to handle both directions of natural language processing.

Key Insights and Results

The research yields several critical insights into the nature of bidirectional NLP:

  • Semantic-Head Dominance: In generation, a "semantic-head" shares its meaning with the entire phrase. It consumes a portion of the semantic guide and dictates the requirements for its dependent "sisters."
  • Symmetry of Compositionality: Parsing is simplified by string concatenation, while generation is simplified by semantic composition. Treating these as duals enables a unified architectural approach.
  • Algorithmic Equivalence: The authors demonstrate that their transformed, non-left-recursive programs (P2) maintain full logical equivalence with the original grammar rules. No linguistic information is lost during optimization.

The resulting architecture provides a common program schema that can be instantiated for either task. These programs are directly implementable in Prolog and significantly narrow the search space by using the input (string or semantics) to constrain lexical access at every step.

Limitations and Future Work

While the framework is robust, several areas for further development remain:

  • Empty Productions: The current model assumes every lexical entry corresponds to at least one word, making it difficult to handle "traces" or empty categories common in complex syntax.
  • Extraposition: Handling words moved out of their standard positions requires a more complex "lexicographical" guide, which was not fully integrated into the primary model.
  • Semantic Complexity: The approach relies on specific types of semantic composition; highly complex semantics (e.g., unrestricted lambda-calculus) may challenge the guide's ability to effectively constrain generation.
  • Scaling: The model has been demonstrated on hand-crafted examples and is currently being tested within the larger CRITTER translation system to evaluate its performance on broader linguistic data.

Summary updated

BibTeX
@inproceedings{dymetman1990symmetrical,
  author = {Marc Dymetman and Pierre Isabelle and François Perrault},
  title = {{A Symmetrical Approach to Parsing and Generation}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1990},
  url = {https://openreview.net/forum?id=RVhL8VAfXI5Q},
}
Figure