Hybrid Grammars for Discontinuous Parsing

Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 1370–1381, Dublin, Ireland, August 23-29 2014. Hybrid Grammars for Discontinuous Parsing Mark-Jan Nederhof School of Computer Science University of St Andrews KY16 9SX, UK Heiko Vogler Department of Computer Science Technische Universit¨at Dresden D-01062 Dresden, Germany Abstract We introduce the concept of hybrid grammars, which are extensions of synchronous grammars, obtained by coupling of lexical elements. One part of a hybrid grammar generates linear struc- tures, another generates hierarchical structures, and together they generate discontinuous struc- tures. This formalizes and generalizes some existing mechanisms for dealing with discontinuous phrase structures and non-projective dependency structures. Moreover, it allows us to separate the degree of discontinuity from the time complexity of parsing. 1 Introduction Discontinuous phrases occur frequently in languages with relatively free word order, and adequate de- scription of their structure requires special care (Kathol and Pollard, 1995; M¨uller, 2004). Even for languages such as English, with a relatively rigid word order, there is a clear need for discontinuous structures (McCawley, 1982; Stucky, 1987). Early treebanks for English (Marcus et al., 1993) have often represented discontinuity in a way that makes it tempting to ignore it altogether, certainly for the purposes of parsing, whereas recent approaches tend to represent discontinuity in a more overt form, sometimes after transformation of existing treebanks (Choi and Palmer, 2010; Evang and Kallmeyer, 2011). In many modern treebanks, discontinuous struc- tures have been given a prominent status (B¨ohmov´a et al., 2000). Classes of trees without discontinuity can be specified as the sets of parse trees of context-free gram- mars (CFGs). Somewhat larger classes can be specified by tree substitution grammars (Sima’an et al., 1994) and regular tree grammars (Brainerd, 1969; G´ecseg and Steinby, 1997). Practical parsers for these three formalisms have running time O(n3), where n is the length of the input sentence. Discontinuous structures go beyond their strong generative capacity however. Similarly, non-projective dependency structures cannot be obtained by traditional dependency grammars. See (Rambow, 2010) for discussion of the relation between constituent and dependency structures and see (Maier and Lichte, 2009) for a comparison of discontinuity and non-projectivity. One way to solve the above problems has been referred to as pseudo-projectivity, i.e. a parser produces a projective structure, which in a second phase is transformed into a non-projective structure (Kahane et al., 1998; McDonald and Pereira, 2006; Nivre and Nilsson, 2005). In particular, this may involve lifting, whereby one end point of a dependency link moves across a path of nodes. A related idea for discontinuous phrase structure is the reversible splitting conversion of (Boyd, 2007). See also (Johnson, 2002; Campbell, 2004; Gabbard et al., 2006). As shown by (Nivre, 2009), the second phase of pseudo-projective dependency parsing can be inter- leaved with the first, by replacing the usual one-way input tape by an additional stack, or buffer. Where This work is licenced under a Creative Commons Attribution 4.0 International License. Page numbers and proceedings footer are added by the organizers. …

Content truncated to 500 words