A PROLOG Implementation of Government-Binding Theory

Robert J. KuhnsCOLING 1986

TL;DR

This paper presents a PROLOG-based parser that implements Chomsky's Government-Binding (GB) Theory. By leveraging GB's constraint-based modules (Theta, Binding, Control), the parser simultaneously determines syntactic structure, argument roles, and coreference relations without relying on extensive grammar rules or lexical subcategorization. This approach offers a more principled and potentially faster way to understand sentence structure and meaning.

What Problem Does This Paper Address?

Traditional natural language parsers often rely on large sets of explicit grammar rules and detailed lexical information (like subcategorization frames for verbs) to determine sentence structure. This can lead to complex and redundant systems. Furthermore, many parsers handle different linguistic phenomena (syntax, semantics, coreference) in separate stages, which doesn't reflect how humans seem to process language so fluidly.

This paper addresses these issues by proposing a parser grounded in Government-Binding (GB) Theory. GB theory, a significant development in linguistics, shifts the focus from a rule-based system to a system of interacting modules and universal principles that constrain possible sentence structures. The authors aim to show that by implementing these GB principles directly, a parser can be more modular, less reliant on explicit rules, and capable of determining syntactic, theta-role, and binding information simultaneously. This aligns with Chomsky's later ideas that parsers could be based on lexical properties and structure-determining principles rather than complex rule sets.

Methods

The core of the paper is the implementation of a parser in PROLOG that directly reflects the principles of Government-Binding Theory. Instead of traditional phrase structure rules, the parser operates based on GB modules:

  • X-bar Theory: Used to capture cross-categorial relations and specify constraints on underlying structures (e.g., Specifier-X-Complement). The parser doesn't need explicit rules for each category (N, V, A, P) but uses these general schemata.
  • Theta-Theory: Determines argument structure and theta-role assignments. The parser infers theta-roles based on lexical information and compositional assignment (head assigns to complement, head-complement pair assigns to specifier).
  • Binding Theory: Constrains the assignment of indices for coreference. The parser implements conditions on anaphors, pronominals, and R-expressions within their governing categories.
  • Control Theory: Determines the controller of PRO (an empty category).
  • Chains: Represents the history of movement. The parser constructs chains for constituents and their traces, and argues that Case and theta-roles are assigned to chains.
  • Projection Principle & Theta-Criterion: These principles ensure that theta-role assignments are consistent across different levels of syntactic representation (D-structure, S-structure, LF) and that each chain receives exactly one theta-role.

The parser uses PROLOG's unification and resolution capabilities to manage data structures (input buffer, processed nodes) and implement these principles. Key PROLOG predicates are described for creating nodes, inserting lexical items/traces/PROs, and defining relationships like "governing category" and "c-command." The parser aims for a deterministic approach with limited look-ahead, where structures are permanent once created.

Datasets

Not discussed in the paper. The paper focuses on the theoretical implementation and provides example sentences for illustration rather than empirical evaluation on a corpus.

Key Insights and Ideas

  • Principle-Based Parsing: The paper demonstrates that a parser can be effectively built on linguistic principles (like GB theory) rather than solely on explicit grammar rules. This offers a more elegant and potentially more robust parsing mechanism.
  • Simultaneous Processing: A major insight is the ability to determine syntactic structure, theta-relations, and binding/control relations simultaneously. This contrasts with multi-stage parsers and better reflects the perceived speed and integration of human language processing.
  • Reduced Lexical Burden: By using GB's subcategorization principles and theta-role assignments, the parser can infer structural requirements, reducing the need for explicit subcategorization features in the lexicon.
  • PROLOG as a Natural Fit: The authors highlight how PROLOG's logic programming paradigm, with its unification and backtracking capabilities, is well-suited for implementing constraint-based linguistic theories like GB.

Key Results

The paper describes the conceptual framework and implementation strategy for a GB-based parser. It provides two illustrative examples:

  • Example 1 (The instructor told the students to leave early): Demonstrates how the parser constructs NP and VP structures, infers theta-roles (goal, proposition), and uses X-bar theory to complete the parse.
  • Example 2 (The students were told to leave early): Illustrates how the parser handles passive voice, detects gaps (traces), assigns theta-roles to chains, and uses Binding Theory to co-index the subject ("the students") with the trace. It also shows how Control Theory is used to assign the agent role to PRO in the embedded infinitive.

While quantitative results are not presented, the qualitative outcome is a parser that can derive syntactic structure, theta-relations, and binding/control relations in an integrated manner.

Limitations and Future Work

  • Limited Scope: The parser currently focuses on A-positions (argument positions) for movement and chains.
  • Expository Simplification: For clarity, some PROLOG predicates and details of the implementation (like specific tree-walking algorithms) are suppressed or simplified in the paper.
  • Theta-Role Representation: A more substantive account of theta-role representations among chains is needed, beyond just assigning roles to individual chains.
  • Future Work: The authors plan to extend the parser to handle parasitic gaps, pronouns behaving as variables, and quantificational relations. They also aim to further reduce the number of explicit grammar rules and explore more sophisticated theta-role assignment mechanisms.

Summary updated

BibTeX
@inproceedings{kuhns1986prolog,
  author = {Robert J. Kuhns},
  title = {{A PROLOG Implementation of Government-Binding Theory}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1986},
}
Figure