Flexible Parsing

Philip J. Hayes, George V. MouradianACL 1980 · DOI

Abstract

In the early development of natural language interfaces, rigid syntactic grammars often failed when faced with the "messiness" of real-world human communication. This paper presents FlexP, a bottom-up, pattern-matching parser designed to handle ungrammatical input—including misspellings, restarts, and fragments—by employing semantic grammars and flexible continuation strategies.

Introduction

The challenge of natural language processing (NLP) in the late 1970s and early 1980s was the fragility of existing systems. Most parsers relied on Augmented Transition Networks (ATNs) or similar top-down syntactic structures. While theoretically sound, these systems were brittle; a single typo or a conversational restart would cause the entire parse to fail. For computers to be effective in domains like electronic mail or database management, they required a degree of "indifference" to grammatical deviations similar to that of human listeners.

The FlexP Architecture

FlexP (Flexible Parser) was developed at Carnegie-Mellon University to address these limitations. It introduced three fundamental shifts in parsing strategy:

  1. Bottom-Up Processing: Instead of predicting input from a top-down grammar, FlexP builds interpretations directly from the provided words. This allows the system to recognize fragments even if the beginning of a sentence is missing or garbled.
  2. Semantic Grammars: Rather than focusing on parts of speech (nouns, verbs), FlexP uses patterns based on meaning, such as "MessageDescription" or "Display." These patterns are linear and can be indexed by any constituent word.
  3. Heuristic Indexing: To maintain efficiency, the system uses heuristics to limit the activation of new patterns if a word can already be explained by an existing, partially matched structure.
Figure 1: Bottom-up mapping of input words to semantic patterns.

Handling Deviant Input

The core strength of FlexP lies in its ability to manage "deviant" input through parse suspension and continuation. When an unexpected word is encountered, the parser does not crash. It suspends the current parse and attempts to identify the new input as an interjection or the start of a restart.

Furthermore, the system is robust against omissions. Because it uses semantic patterns, it can often infer the intended meaning even if key components are missing. For example, in a MessageDescription pattern, if the head noun is omitted but a prepositional phrase like "about topic" is present, the system can still complete the parse.

Figure 6: Parsing fragmented input with missing components like the head noun.

Key Insights and Results

FlexP categorizes human linguistic "failures" into a taxonomy including misspellings, restarts, and interjections. By prioritizing semantic context over strict syntax, the system demonstrated qualitative success in handling complex real-world examples, such as "display for me messages dated June 17," where "for me" is treated as a separate, resumable fragment.

Limitations and Future Directions

While successful in limited domains, the authors noted that the heuristic-based approach might struggle with the ambiguity of larger, general-purpose grammars. Additionally, the system was designed for typed input and did not address the acoustic challenges of speech recognition. Future work suggested integrating vocabulary learning to allow the parser to infer the meaning of novel words based on their structural context.

Conclusion

FlexP represented a significant step toward more resilient human-computer interfaces. By moving away from rigid syntactic rules and toward flexible, meaning-driven patterns, it paved the way for systems that can interact with humans on their own, often messy, terms.

Summary updated

BibTeX
@inproceedings{hayes1980flexible,
  author = {Philip J. Hayes and George V. Mouradian},
  title = {{Flexible Parsing}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1980},
  doi = {10.3115/981436.981467},
}
Figure