Parsing Conjunctions Deterministically

PARSING CONJUNCTIONS DETERMINISTICALLY Donald W. Kosy The Robotics Institute Carnegie-Mellon University Pittsburgh, Pennsylvania 15213 ABSTRACT Conjunctions have always been a source of problems for natural language parsers. This paper shows how these problems may be circumvented using a rule.based, walt-and-see parsing strategy. A parser is presented which analyzes conjunction structures deterministically, and the specific rules it uses are described and illustrated. This parser appears to be faster for conjunctions than other parsers in the literature and some comparative timings are given. INTRODUCTION In recent years, there has been an upsurge of interest in tech- niques for parsing sentences containing coordinate conjunctions (and, or and but) [1,2,3,4,5,8,9]. These techniques are intended to deal with three computational problems inherent in conjunc- tion parsing: 1. Since virtually any pair of constituents of the same syntactic type may be conjoined, a grammar that ex- plicitly enumerates all the possibilities seems need- lessly cluttered with a large number of conjunction rules. 2. If a parser uses a top-down analysis strategy (as is common with ATN and logic grammars), it must hypothesize a structure for the second conjunct with- out knowledge of its actual structure. Since this structure could be any that parallels some con- stituent that ends at the conjunction, the parser must generate and test all such possibilities in order to find the ones that match. In practice, the combinatorial explosion of possibilities makes this slow. 3. It is possible for a conjunct to have "gaps" (ellipsed elements) which are not allowed in an unconjoined constituent of the same type. These gaps must be filled with elements from the other conjunct for a proper interpretation, as in: I gave Mary a nickel and Harry a dime. The paper by Lesmo and Torasso [9] briefly reviews which tech. niques apply to which problems before presenting their own ap- proach. Two papers in the list above [1,3] present deterministic, "wait. and-see" methods for conjunction parsing. In both, however, the discussion centers around the theory and feasibility of parsers that obey the Marcus determinism hypothesis [10] and operate with a limited-length Iookahead buffer. This paper examines the other side of the coin, namely, the practical power of the wait- and.see approach compared to strictly top-down or bottom-up methods. A parser is described that analyzes conjunction struc. tures deterministically and produces parse trees similar to those produced by Dahl & McCord's MSG system [4]. It is much faster than either MSG or Fong & Berwick's RPM device [5], and com- parative timings are given. We conclude with some descriptive comparisons to other systems and a discussion of the reasons behind the performance observed. OVERVIEW OF THE PARSER For the sake of a name, we will call the parser NEXUS since it is the syntactic component of a larger system called NEXUS. This system is being developed to study the problem of learning tech. nical concepts from expository text. The acronym stands for Non.Expert Understanding System. NEXUS is a direct descendent of READER, a parser written by Ginsparg at …

Content truncated to 500 words