Dynamic Strategy Selection in Flexible Parsing

Dynamic Strategy Selection in Flexible Parsing Jaime G. Carbonell and Philip J. Hayes Carnegie-Mellon University Pittsburgh, PA 15213 Abstract Robust natural language interpretation requires strong semantic domain models, "fall-soff" recovery heuristics, and very flexible control structures. Although single-strategy parsers have met with a measure of success, a multi.strategy approach is shown to provide a much higher degree of flexibility, redundancy, and ability to bring task-specific domain knowledge (in addition to general linguistic knowledge) to bear on both grammatical and ungrammatical input. A parsing algorithm is presented that integrates several different parsing strategies, with case-frame instantiation dominating. Each of these parsing strategies exploits different types of knowledge; and their combination provides a strong framework in which to process conjunctions, fragmentary input, and ungrammatical structures, as well as less exotic, grammatically correct input. Several specific heuristics for handling ungrammatical input are presented within this multi-strategy framework. 1. Introduction When people use language spontaneously, they o~ten do not respect grammatical niceties. Instead of producing sequences of grammatically well-formed and complete sentences, they often miss out or repeat words or phrases, break off what they are .saying and rephrase or replace it, speak in fragments, or use otherwise incorrect grammar. While other people generally have little trouble co'reprehending ungrammatical utterances, most' natural language computer systems are unable to process errorful input at all. Such inflexibility in parsing is a serious impediment to the use of natural language in interactive computer systems. Accordingly, we [6] and other researchers including Wemchedel and Black [14], and Kwasny and Sondhelmer [9], have attempted to produce flexible parsers, i.e. parsers that can accept ungrammatical input, correcting the errors whan possible, and generating several alternative interpretations if appropriate. While different in many ways, all these approaches to flexible parsing operate by applying a uniform parsing process to a uniformly represented grammar. Because of the linguistic performance problems involved, this uniform procedure cannot be as simple and elegant as the procedures followed by parsers based on a pure linguistic competence model, such as Parsifal [10]. Indeed, their parsing procedures may involve several strategies that are applied in a predetermined order when the input deviates from the grammar, but the choice of strategy never depends on the specific type of construction being parsed. In light of experience with our own flexible parser, we have come to believe that such uniformity is not conducive to good flexible parsing. Rather, the strategies used should be dynamically selected according to the type of construction being parsed. For instance, partial.linear pattern matching may be well suited to the flexible parsing of idiomatic phrases, or specialized noun phrases such as names, dates, or addresses (see also [5]), but case constructions, such as noun phrases with trailing prepositional phrases, or imperative phrases, require case-oriented parsing strategies. The undedying principle is simple: The ap~rol~riate knowledge must be brought to bear at the right time -- and it must not interfere at other times. Though the initial motivation for this approach sprang from the r~eeds of flexible parsing, such construction.specific …

Content truncated to 500 words