Head Corner Parsing for Discontinuous Constituency

Head Corner Parsing for Discontinuous Constituency Gertjan van Noord Lehrstuhl ffir Computerlinguistik Universit~t des Saarlandes Im Stadtwald 15 D-6600 Saarbrficken 11, FRG vannoord@coli.uni-sb.de Abstract I describe a head-driven parser for a class of gram- mars that handle discontinuous constituency by a richer notion of string combination than ordinary concatenation. The parser is a generalization of the left-corner parser (Matsumoto et al., 1983) and can be used for grammars written in power- ful formalisms such as non-concatenative versions of HPSG (Pollard, 1984; Reape, 1989). 1 Introduction Although most formalisms in computational lin- guistics assume that phrases are built by string concatenation (eg. as in PATR II, GPSG, LFG and most versions of Categorial Grammar), this assumption is challenged in non-concatenative grammatical formalisms. In Pollard's dissertation several versions of 'qlead wrapping" are defined (Pollard, 1984). In the analysis of the Australian free word-order language Guugu Yimidhirr, Mark Johnson uses a 'combine' predicate in a DCG-like grammar that corresponds to the union of words (Johnson, 1985). Mike Reape uses an operation called 'sequence union' to analyse Germanic semi-free word or- der constructions (l~ape, 1989; Reape, 1990a). Other examples include Tree Adjoining Gram- mars (Joshi et al., 1975; Vijay-Shankar and Joshi, 1988), and versions of Categorial Gram- mar (Dowry, 1990) and references cited there. Motivation. There are several motivations for non-concatenative grammars. First, specialized string combination operations allow elegant lin- guistic accounts of phenomena that are otherwise notoriously hard. Examples are the analyses of Dutch cross serial dependencies by head wrap- ping or sequence union (Reape, 1990a). Furthermore, in non-concatenative grammars it is possible to relate (parts of) constituents that belong together semantically, but which are not adjacent. Hence such grammars facilitate a sim- ple compositional semantics. In CF-based gram- mars such phenomena usually are treated by com- plex 'threading' mechanisms. Non-concatenative grammatical formalisms may also be attractive from a computational point of view. It is easier to define generation algorithms if the semantics is built in a systemat- ically constrained way (van Noord, 1990b). The semantic-head-driven generation strategy (van Noord, 1989; Calder ef al., 1989; Shieber et al., 1989; van Noord, 1990a; Shieber et al., 1990) faces problems in case semantic heads are 'dis- placed', and this displacement is analyzed us- ing threading. However, in this paper I sketch a simple analysis of verb-second (an example of a displacement of semantic heads) by an oper- ation similar to head wrapping which a head- driven generator processes without any problems (or extensions) at all. Clearly, there are also some computational problems, because most 'standard' parsing strategies assume context-free concatena- tion of strings. These problems are the subject of this paper. The task. I will restrict the attention to a class of constraint-based formalisms, in which operations on strings are defined that are more powerful than concatenation, but which opera- tions are restricted to be nonerasing, and linear. The resulting class of systems can be character- ized as Linear Context-Free Rewriting Systems 114 (LCFRS), augmented with feature-structures (F- LCFRS). For a discussion of the properties …

Content truncated to 500 words