Know When to Hold 'Em: Shuffling Deterministically in a Parser for Nonconcatenative Grammars

Know When to Hold 'Em: Shuffling Deterministically in a Parser for Nonconcatenative Grammars* Robert T. Kasper, Mike Calcagno, and Paul C. Davis Department of Linguistics, Ohio State University 222 Oxley Hall 1712 Neil Avenue Columbus, OH 43210 U.S.A. Email: {kasper,calcagno,pcdavis) @ling.ohio-state.edu Abstract Nonconcatenative constraints, such as the shuffle re- lation, are frequently employed in grammatical anal- yses of languages that have more flexible ordering of constituents than English. We show how it is pos- sible to avoid searching the large space of permuta- tions that results from a nondeterministic applica- tion of shuffle constraints. The results of our imple- mentation demonstrate that deterministic applica- tion of shuffle constraints yields a dramatic improve- ment in the overall performance of a head-corner parser for German using an HPSG-style grammar. 1 Introduction Although there has been a considerable amount of research on parsing for constraint-based grammars in the HPSG (Head-driven Phrase Structure Gram- mar) framework, most computational implementa- tions embody the limiting assumption that the con- stituents of phrases are combined only by concate- nation. The few parsing algorithms that have been proposed to handle more flexible linearization con- straints have not yet been applied to nontrivial grammars using nonconcatenative constraints. For example, van Noord (1991; 1994) suggests that the head-corner parsing strategy should be particularly well-suited for parsing with grammars that admit discontinuous constituency, illustrated with what he calls a "tiny" fragment of Dutch, but his more re- cent development of the head-corner parser (van No- ord, 1997) only documents its use with purely con- catenative grammars. The conventional wisdom has been that the large search space resulting from the use of such constraints (e.g., the shuffle relation) makes parsing too inefficient for most practical ap- plications. On the other hand, grammatical anal- yses of languages that have more flexible ordering of constituents than English make frequent use of constraints of this type. For example, in recent work by Dowty (1996), Reape (1996), and Kathol " This research was sponsored in part by National Science Foundation grant SBR-9410532, and in part by a seed grant from the Ohio State University Office of Research; the opin- ions expressed here are solely those of the authors. (1995), in which linear order constraints are taken to apply to domains distinct from the local trees formed by syntactic combination, the nonconcate- native shuffle relation is the basic operation by which these word order domains are formed. Reape and Kathol apply this approach to various flexible word-order constructions in German. A small sampling of other nonconcatenative op- erations that have often been employed in linguistic descriptions includes Bach's (1979) wrapping oper- ations, Pollard's (1984) head-wrapping operations, and Moortgat's (1996) extraction and infixation op- erations in (categorial) type-logical grammar. What is common to the proposals of Dowty, Reape, and Kathol, and to the particular analysis implemented here, is the characterization of nat- ural language syntax in terms of two interrelated but in principle distinct sets of constraints: (a) con- straints on an unordered hierarchical structure, pro- jected from …

Content truncated to 500 words