Endocentric Constructions and the Cocke Parsing Logic

Jane J. RobinsonCOLING 1965

TL;DR

This paper explores how to simplify automatic syntactic analysis by separating grammatical rules from the routines that apply them, focusing on the Cocke parsing logic. It proposes methods to manage the complexity arising from endocentric constructions, particularly in English noun phrases, to improve efficiency and reduce storage requirements in parsing.

What Problem Does This Paper Address?

The core problem this paper addresses is the complexity and inefficiency in automatic syntactic analysis (ASA), specifically sentence structure determination (SSD). Traditional ASA methods often intertwined grammatical rules with the computer routines that applied them. This led to cumbersome, language-specific programs that required extensive rewriting for every new grammatical feature. The paper highlights that while parsing logics like the Cocke logic offer a way to disengage grammar from routines, they can still lead to issues, especially with "endocentric constructions" (like noun phrases where the core meaning is in one element, e.g., "men" in "old men"). These constructions, common in English, can lead to multiple, often redundant, analyses, increasing storage needs and processing time. The paper aims to find ways to simplify this process, particularly for languages like English, by refining the grammar and parsing logic to handle these constructions more efficiently.

Methods

The paper centers on the Cocke parsing logic (PL), a method devised by John Cocke in 1960. This logic operates on context-free phrase structure grammars (PSGs) and requires that each recognized structure be broken down into exactly two immediate constituents. The PL iterates through segments of increasing length, testing pairs of adjacent segments for valid constructions based on a grammar table.

The paper proposes two main strategies to address the complexity of endocentric constructions:

  1. Grammar Refinement and Rule Classification: Instead of complex rules, the paper suggests classifying rules and introducing an additional parameter to control the direction of parsing (left-to-right or right-to-left). This allows for more efficient handling of constructions by specifying an order of application. For example, rules for endocentric constructions can be marked to indicate whether they attach elements to the left or right of the head.
  2. Code Simplification and Duplication Reduction: The paper discusses how to reduce the number of duplicate codes generated by the parsing process. This involves writing grammar codes that reflect the ordering of elements within a phrase and differentiating them based on position. By carefully defining codes and restricting combinations, the number of structural assignments and intermediate constructions can be significantly reduced.

Datasets

Not discussed in the paper. The paper focuses on theoretical aspects and uses illustrative examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Disengaging Grammar from Routines: The Cocke PL is a significant step towards separating grammatical knowledge from the computational machinery that applies it, making grammars more adaptable.
  • Endocentric Constructions as a Challenge: These constructions, common in languages like English, pose a particular problem for parsing logic due to their potential for multiple, often redundant, structural analyses.
  • The Power of Directionality: Introducing a parameter to control parsing direction (left-to-right vs. right-to-left) can significantly simplify the handling of constructions, especially in languages with a preferred branching direction.
  • Code Design Matters: The way grammar codes are designed and structured can have a profound impact on efficiency. Codes that reflect element order and properties can help reduce duplicate analyses.
  • Theoretical vs. Practical Considerations: While theoretical elegance is important, practical concerns like storage and processing time necessitate clever grammar design and parsing strategies.

Key Results

The paper doesn't present quantitative results in terms of specific accuracy metrics or speedups on benchmark datasets. Instead, it demonstrates through examples how the proposed methods can:

  • Reduce the number of structural assignments: For a given noun phrase, the number of possible bracketings can be reduced from multiple options to a single, preferred one.
  • Alleviate storage problems: By eliminating duplicate codes and intermediate constructions, the memory footprint of the parsing process is decreased.
  • Improve processing efficiency: Fewer analyses and less data to store directly translate to faster parsing times.
  • Simplify grammar writing: Grouping rules by construction types and using specific tags (like 'A' for endocentric NPs) makes grammars more manageable.

Limitations and Future Work

The paper acknowledges that fully formalizing these methods can lead to increased complexity in codes and rules, potentially creating new storage and processing challenges. It also notes that the choice of parsing direction (left-to-right vs. right-to-left) is a grammatical consideration that doesn't affect the core logic of the PL but is important for language-specific optimization. The paper suggests that further work could explore how to adequately develop these theoretical-practical considerations, particularly in relation to Yngve's hypothesis about language asymmetry and its implications for preferred branching directions.

Summary updated

BibTeX
@inproceedings{robinson1965endocentric,
  author = {Jane J. Robinson},
  title = {{Endocentric Constructions and the Cocke Parsing Logic}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1965},
}
Figure