Some Comments on Algorithm and Grammar in the Automatic Parsing of Natural Languages

Paul L. GarvinCOLING 1965

TL;DR

This paper critically examines the common assertion that separating parsing algorithms from grammars simplifies natural language processing (NLP) systems. The author argues that for adequate parsing of natural languages, especially for machine translation, context-sensitivity is crucial, making this separation less beneficial than often claimed. The paper proposes a modular approach with an executive routine and subroutines as a more effective structural principle.

What Problem Does This Paper Address?

The paper tackles the prevailing belief in the NLP community that separating the parsing algorithm from the grammar rules offers significant advantages in terms of simplicity and ease of maintenance. This separation is often advocated for automatic parsing programs, particularly those used in machine translation. The core of the problem lies in whether this separation truly leads to a simpler and more efficient system when dealing with the complexities of natural language, which inherently requires understanding context. The author questions the efficacy of this approach when grammars need to be sufficiently context-sensitive to accurately recognize syntactic units and their functions, a prerequisite for sentence-by-sentence machine translation.

Methods

The paper doesn't present a novel algorithm or a new dataset. Instead, it offers a critical analysis and a conceptual argument. The author's "method" is to dissect the claims made by proponents of algorithm-grammar separation. This involves:

  • Defining Context-Free vs. Context-Sensitive Grammars: The author clarifies these terms, emphasizing that context-sensitive grammars consider both internal structure and external functioning, which is essential for natural language.
  • Challenging the Simplicity Claim: The paper argues that the claimed simplicity of a separate grammar table with a constant algorithm is illusory when dealing with context-sensitive grammars. The complexity shifts from the algorithm to the grammar table itself, and modifications become less straightforward.
  • Re-evaluating Input Data: The author questions the view that grammar tables are simply input data, arguing they are more akin to processing parameters.
  • Proposing an Alternative Structure: The paper advocates for a modular design, comprising an executive main routine and specialized subroutines, as a more robust and manageable structure for parsing programs.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Context-Sensitivity is Key: The paper strongly emphasizes that natural language parsing, especially for machine translation, requires a high degree of context-sensitivity. This means that simple context-free approaches are insufficient, and the complexity of context must be handled.
  • Separation's Simplicity is an Illusion: The author argues that the perceived simplicity of separating algorithm and grammar breaks down when grammars need to be context-sensitive. The complexity is merely shifted to the grammar rules, making them harder to manage.
  • Grammar Rules as Parameters, Not Just Input: The paper suggests that grammar rules function more as parameters that guide the processing rather than raw input data to be processed.
  • Modular Design as a Better Alternative: The author proposes that a parsing program should be structured as an executive routine with self-contained, interchangeable subroutines. This modularity offers better organization and maintainability than the algorithm-grammar separation.

Key Results

This paper is primarily theoretical and argumentative, so it does not present quantitative results. The "results" are conceptual:

  • The argument for the simplicity of separating algorithm and grammar is deemed "far from convincing."
  • The paper establishes that for adequate natural language parsing, a system needs to be capable of modification in terms of increasing context-sensitivity, not just a fixed range.
  • A modular design with an executive routine and subroutines is presented as a more satisfactory structural principle for parsing programs.

Limitations and Future Work

  • Limitations: The paper acknowledges that its discussion is restricted to the area of automatic parsing of natural languages, with a particular focus on machine translation. The author's opinion is explicitly stated as the basis for some arguments. The paper also doesn't delve into specific implementation details of the proposed modular structure.
  • Future Work: The paper raises the "further question of the functions and design of the executive routine and subroutines," implying that this is an area ripe for further investigation and development. The concept of "analytic modules" and "housekeeping modules" suggests a direction for designing these subroutines.

Summary updated

BibTeX
@inproceedings{garvin1965some,
  author = {Paul L. Garvin},
  title = {{Some Comments on Algorithm and Grammar in the Automatic Parsing of Natural Languages}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1965},
}
Figure