A Grammar Formalism and Parser for Linearization-based HPSG

A grammar formalism and parser for linearization-based HPSG Michael W. Daniels and W. Detmar Meurers Department of Linguistics The Ohio State University 222 Oxley Hall 1712 Neil Avenue Columbus, OH 43210 daniels|dm@ling.osu.edu Abstract Linearization-based HPSG theories are widely used for analyzing languages with relatively free constituent order. This paper introduces the Generalized ID/LP (GIDLP) grammar for- mat, which supports a direct encoding of such theories, and discusses key aspects of a parser that makes use of the dominance, precedence, and linearization domain information explicitly encoded in this grammar format. We show that GIDLP grammars avoid the explosion in the number of rules required under a traditional phrase structure analysis of free constituent or- der. As a result, GIDLP grammars support more modular and compact grammar encodings and require fewer edges in parsing. 1 Introduction Within the framework of Head-Driven Phrase Struc- ture Grammar (HPSG), the so-called linearization- based approaches have argued that constraints on word order are best captured within domains that extend beyond the local tree. A range of analyses for languages with relatively free constituent order have been developed on this basis (see, for example, Reape, 1993; Kathol, 1995; M¨uller, 1999; Donohue and Sag, 1999; Bonami et al., 1999) so that it is at- tractive to exploit these approaches for processing languages with relatively free constituent order. This paper introduces a grammar format that sup- ports a direct encoding of linearization-based HPSG theories. The Generalized ID/LP (GIDLP) format explicitly encodes the dominance, precedence, and linearization domain information and thereby sup- ports the development of efficient parsing algorithm making use of this information. We make this concrete by discussing key aspects of a parser for GIDLP grammars that integrates the word order do- mains and constraints into the parsing process. 2 Linearization-based HPSG The idea of discontinuous constituency was first in- troduced into HPSG in a series of papers by Mike Reape (see Reape, 1993 and references therein).1 The core idea is that word order is determined not at the level of the local tree, but at the newly intro- duced level of an order domain, which can include elements from several local trees. We interpret this in the following way: Each terminal has a cor- responding order domain, and just as constituents combine to form larger constituents, so do their or- der domains combine to form larger order domains. Following Reape, a daughter’s order domain enters its mother’s order domain in one of two ways. The first possibility, domain union, forms the mother’s order domain by shuffling together its daughters’ domains. The second option, domain compaction, inserts a daughter’s order domain into its mother’s. Compaction has two effects: Contiguity: The terminal yield of a compacted category contains all and only the terminal yield of the nodes it dominates; there are no holes or addi- tional strings. LP Locality: Precedence statements only con- strain the order among elements within the same compacted domain. In other words, precedence constraints cannot look into a compacted domain. Note that these are two …

Content truncated to 500 words