tailieunhanh - Báo cáo khoa học: "Know When to Hold'Em: Shuffling Deterministically in a Parser for Non concatenative Grammars*"

Nonconcatenative constraints, such as the shuffle relation, are frequently employed in grammatical analyses of languages that have more flexible ordering of constituents than English. We show how it is possible to avoid searching the large space of permutations that results from a nondeterministic application of shuffle constraints. The results of our implementation demonstrate that deterministic application of shuffle constraints yields a dramatic improvement in the overall performance of a head-corner parser for German using an HPSG-style grammar. 1 (1995), in which linear order constraints are taken to apply to domains distinct from the local trees formed by syntactic combination,. | 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 . Email kasper calcagno pcdavis @ Abstract Nonconcatenative constraints such as the shuffle relation are frequently employed in grammatical analyses of languages that have more flexible ordering of constituents thím English. We show how it is possible to avoid searching the large space of permutations that results from a nondeterministic application of shuffle constraints. The results of our implementation demonstrate that deterministic application of shuffle constraints yields a dramatic improvement 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 Grammar framework most computational implementations embody the limiting assumption that the constituents of phrases are combined only by concatenation. The few parsing algorithms that have been proposed to handle more flexible linearization constraints 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 recent development of the head-corner parser van Noord 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 . the shuffle relation makes parsing too inefficient for most practical applications. On the other hand grammatical analyses of languages that have more flexible ordering .