Sentence Disambiguation by a Shift-Reduce Parsing Technique

Sentence Disambiguation by a Shift-Reduce Parsing Technique* Stuart M. Shieber Abstract Artificial Intelligence Center SRI International 333 Ravenswood Avenue Menlo Park, CA 94025 Native speakers of English show definite and consistent preferences for certain readings of syntactically ambiguous sen- tences. A user of a natural-language-processing system would naturally expect it to reflect the same preferences. Thus, such systems must model in some way the linguistic performance as well as the linguistic competence of the native speaker. We have developed a parsing algorithm--a variant of the LALR(I} shift.-reduce algorithm--that models the preference behavior of native speakers for a range of syntactic preference phenomena reported in the psycholinguistic literature, including the recent data on lexical preferences. The algorithm yields the preferred parse deterministically, without building multiple parse trees and choosing among them. As a side effect, it displays ap- propriate behavior in processing the much discussed garden-path sentences. The parsing algorithm has been implemented and has confirmed the feasibility of our approach to the modeling of these phenomena. 1. Introduction For natural language processing systems to be useful, they must assign the same interpretation to a given sentence that a native speaker would, since that is precisely the behavior users will expect.. Consider, for example, the case of ambiguous sen- tences. Native speakers of English show definite and consistent preferences for certain readings of syntactically ambiguous sen- tences [Kimball, 1973, Frazier and Fodor, 1978, Ford et aL, 1982]. A user of a natural-language-processing system would naturally expect, it to reflect the same preferences. Thus, such systems must model in some way the lineuistie performance as well as the linguistic competence of the native speaker. This idea is certainly not new in the artificial-intelligence literature. The pioneering work of Marcus [Marcus, 1980] is per- haps the best. known example of linguistic-performance modeling in AI. Starting from the hypothesis that ~deterministic" parsing of English is possible, he demonstrated that certain performance "This research was supported by the Defense Advanced Research Proiects Agency under Contract NOOO39-80-C-0575 with the Naval Electronic Systems Command. The views and conclusions contained in this document are those of the author and should not be interpreted a.s representative of the oh~cial policies, either expressed or implied, of the Defense Advanced Research Projects Agency or the United States government. constraints, e.g., the difl]culty of parsing garden-path sentences, could be modeled. His claim about deterministic parsing was quite strong. Not only was the behavior of the parser required to be deterministic, but, as Marcus claimed, The interpreter cannot use some general rule to take a nondeterministic grammar specification and im- pose arbitrary constraints to convert it to a deter- ministic specification {unless, of course, there is a general rule which will always lead to the correct decision in such a case). [Marcus, 1980, p.14] We have developed and implemented a parsing system that. given a nondeterministic grammar, forces disambiguation in just the manner Marcus rejected (i.e. t .hrough general rules}; it thereby exhibits the same preference behavior that psycbolin- guists have attributed to …

Content truncated to 500 words