Constraining a Deterministic Parser

Joan Bachenko, Donald Hindle, Eileen FitzpatrickAAAI 1983

Abstract

This paper explores the application of Noam Chomsky’s Government and Binding (GB) theory to deterministic parsing. Researchers at the Naval Research Laboratory demonstrate that a parser can accurately structure English sentences by adhering to a "Left Corner Constraint" (LCC), which limits the parser's view to a constituent's leftmost element and lexical category. By utilizing abstract subjects (DELTA nodes), the model efficiently identifies complex verb complements without backtracking, offering a robust framework for real-time natural language processing.

Introduction

In the early 1980s, natural language processing faced a significant trade-off between computational efficiency and linguistic depth. Deterministic parsers, which build structures "indelibly" without backtracking, were fast but often struggled with syntactic ambiguities, such as distinguishing between verb complements (required) and optional adjuncts. Previous models often relied on "annotated surface structures"—heavy feature bundles that recorded internal phrase properties. This research investigates whether a more constrained approach, using only the first piece of information encountered in a phrase, can achieve accurate results.

Methods

The authors extend the deterministic parsing model developed by Mitchell Marcus (1980), which uses a stack of incomplete nodes and a buffer of three complete constituents. The primary innovation is the Left Corner Constraint (LCC). Under this constraint, the parser is restricted from accessing any information about a constituent other than its syntactic category (e.g., NP, S) and its "left corner"—the leftmost terminal and its category.

To handle "subjectless" phrases like infinitives (e.g., "to sleep"), the authors integrate the concept of abstract subjects (DELTA nodes) from GB theory. By positing an invisible subject at the leftmost position, every clause type becomes uniquely identifiable by its left corner. This allows the parser to maintain determinism while handling diverse clausal structures.

A typical clausal structure (S-bar) used in the parser, illustrating the decomposition into COMP and S (NP, Aux, VP).

Key Insights and Results

The implementation demonstrates that most syntactic decisions in English can be made "at the gate." By knowing a phrase's category and its first word, the parser can correctly attach it to the tree. The use of GB framework constructs like DELTA nodes provides a consistent anchor for the LCC across various clause types, including declaratives, infinitives, and -ing phrases.

Key findings include:

  • Deterministic Success: The parser successfully distinguishes complements from adjuncts for various verb types (e.g., think vs. leave) using only left-corner information.
  • Generalization: The LCC applies effectively across nouns, adjectives, and prepositions, suggesting it is a general property of English grammar.
  • Efficiency through Restriction: Restricting the parser's view prevents it from becoming bogged down in internal phrase details, leading to "indelible" structures that are highly efficient for real-time applications, such as military message interpretation.

Limitations and Future Work

While the LCC is powerful, the authors note specific areas where the constraint requires special complications:

  1. Complex PPs: Prepositional phrases containing wh- words (e.g., "from behind which cars") require looking deeper than the left corner to identify the wh- feature.
  2. Agreement: Matching features like "plural" or "human" between a subject and a verb requires projecting information up from the head of a phrase, which technically bypasses the LCC.
  3. Idioms: Recognizing idioms like "make headway" requires the parser to look past the left corner to identify specific lexical combinations.

Future research aims to integrate semantic interpretation rules to monitor argument structure more effectively, ensuring verbs do not take more complements than allowed.

Summary updated

BibTeX
@inproceedings{bachenko1983constraining,
  author = {Joan Bachenko and Donald Hindle and Eileen Fitzpatrick},
  title = {{Constraining a Deterministic Parser}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure