Building a Parser That can Afford to Interact with Semantics

Kavi MaheshAAAI 1994

Abstract

Natural language understanding (NLU) systems face a persistent challenge in balancing syntactic processing with semantic feedback. While semantic information is crucial for pruning unlikely syntactic paths, the timing of this interaction is critical. This paper introduces Head-Signaled Left Corner (HSLC) Parsing, a hybrid strategy designed to optimize the interface between syntax and semantics. By delaying commitment to a parent structure until a syntactically "required" head is identified, HSLC minimizes local ambiguity while maintaining the benefits of incremental interpretation.

Introduction

In the field of computational linguistics, the sheer volume of possible syntactic structures for any given sentence often overwhelms automated parsers. While human cognition navigates these ambiguities with apparent ease, computer systems frequently struggle with the "timing problem" of semantic interaction.

To manage ambiguity, researchers often employ semantic feedback to prune the search space. However, the effectiveness of this feedback depends heavily on when it is triggered. Purely bottom-up parsers are often too cautious, waiting for exhaustive evidence before making a move and thus missing the predictive power of top-down expectations. Conversely, purely top-down parsers are often too eager, making early structural commitments that lead to extensive backtracking when initial predictions fail. This paper proposes a "Goldilocks zone" through a new parsing strategy: Head-Signaled Left Corner (HSLC) parsing.

The Parsing Eagerness Spectrum

HSLC parsing is built upon the foundation of Left Corner (LC) Parsing, which combines the bottom-up processing of a phrase's first constituent with the top-down prediction of the remaining structure. Within the LC framework, strategies vary based on their "eagerness"—the point at which a node is linked to its parent:

  • Arc Eager Left Corner (AELC): This approach links a node to its parent immediately, before any children are processed. While highly incremental, it is prone to false starts.
  • Arc Standard Left Corner (ASLC): This approach waits until all children of a phrase have been fully analyzed before linking to the parent. While accurate, it delays semantic interaction until the very end of a phrase, sacrificing the benefits of incrementality.

Head-Signaled Left Corner (HSLC) Parsing

Mahesh introduces HSLC parsing as the optimal middle ground. In this model, a node is linked to its parent—and subsequently interacts with the semantic analyzer—as soon as a predefined required child, or "head signal," is identified.

This required unit is defined syntactically to ensure the parser has enough information to make a stable commitment without waiting for optional adjuncts. Examples of these head signals include:

  • Noun Phrase (NP): The parser waits for the Noun (N).
  • Verb Phrase (VP): The parser waits for the Verb (V).
  • Prepositional Phrase (PP): The parser waits for the Noun Phrase (NP).

By focusing on these essential units, the parser can begin "meaning-making" immediately after the core of a phrase is identified. It does not need to wait for optional modifiers, such as trailing prepositional phrases or adjectives, which may appear to the right of the head. This allows for a system that is both cognitively plausible and computationally efficient.

Implementation in COMPERE

The HSLC algorithm was implemented within COMPERE, a sentence understanding system designed to balance autonomy and interaction. COMPERE provides a framework where syntactic and semantic modules can communicate incrementally. HSLC serves as the engine for this interaction, ensuring that the semantic module is not flooded with premature, ambiguous data from an eager parser, nor starved of information by a cautious one.

Insights and Theoretical Results

The primary contribution of HSLC is the reduction of local ambiguity. By waiting for the head signal, the parser avoids the "false starts" common in AELC. However, by not waiting for every optional constituent (as in ASLC), it maintains high speed and supports the incremental nature of human language processing.

A key distinction in this research is the difference between syntactic and semantic heads. In HSLC, the "required unit" is a syntactic designation used to drive the parse, which may not always align with semantic heads defined in other linguistic theories. This distinction allows the parser to remain robust across different grammatical structures while still facilitating deep semantic integration.

Conclusion and Future Work

Theoretical analysis suggests that HSLC parsing provides the necessary balance to enable efficient, incremental semantic interaction. While the architectural framework is robust, the author notes that empirical evaluation within the COMPERE system was ongoing at the time of publication. Future research is required to provide quantitative performance metrics, such as parse times and accuracy improvements on standard corpora like the Penn Treebank, to fully validate the efficiency gains of the HSLC approach in large-scale applications.

Summary updated

BibTeX
@inproceedings{mahesh1994building,
  author = {Kavi Mahesh},
  title = {{Building a Parser That can Afford to Interact with Semantics}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure