Efficient parsing with Linear Context-Free Rewriting Systems

Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 460–470, Avignon, France, April 23 - 27 2012. c⃝2012 Association for Computational Linguistics Efficient Parsing with Linear Context-Free Rewriting Systems Andreas van Cranenburgh Huygens ING & ILLC, University of Amsterdam Royal Netherlands Academy of Arts and Sciences Postbus 90754, 2509 LT The Hague, the Netherlands andreas.van.cranenburgh@huygens.knaw.nl Abstract Previous work on treebank parsing with discontinuous constituents using Linear Context-Free Rewriting systems (LCFRS) has been limited to sentences of up to 30 words, for reasons of computational com- plexity. There have been some results on binarizing an LCFRS in a manner that min- imizes parsing complexity, but the present work shows that parsing long sentences with such an optimally binarized grammar re- mains infeasible. Instead, we introduce a technique which removes this length restric- tion, while maintaining a respectable accu- racy. The resulting parser has been applied to a discontinuous treebank with favorable results. 1 Introduction Discontinuity in constituent structures (cf. figure 1 & 2) is important for a variety of reasons. For one, it allows a tight correspondence between syntax and semantics by letting constituent struc- ture express argument structure (Skut et al., 1997). Other reasons are phenomena such as extraposi- tion and word-order freedom, which arguably re- quire discontinuous annotations to be treated sys- tematically in phrase-structures (McCawley, 1982; Levy, 2005). Empirical investigations demon- strate that discontinuity is present in non-negligible amounts: around 30% of sentences contain dis- continuity in two German treebanks (Maier and Søgaard, 2008; Maier and Lichte, 2009). Re- cent work on treebank parsing with discontinuous constituents (Kallmeyer and Maier, 2010; Maier, 2010; Evang and Kallmeyer, 2011; van Cranen- burgh et al., 2011) shows that it is feasible to directly parse discontinuous constituency anno- tations, as given in the German Negra (Skut et al., SBARQ SQ VP WHNP MD NP VB . What should I do ? Figure 1: A tree with WH-movement from the Penn treebank, in which traces have been converted to dis- continuity. Taken from Evang and Kallmeyer (2011). 1997) and Tiger (Brants et al., 2002) corpora, or those that can be extracted from traces such as in the Penn treebank (Marcus et al., 1993) annota- tion. However, the computational complexity is such that until now, the length of sentences needed to be restricted. In the case of Kallmeyer and Maier (2010) and Evang and Kallmeyer (2011) the limit was 25 words. Maier (2010) and van Cranen- burgh et al. (2011) manage to parse up to 30 words with heuristics and optimizations, but no further. Algorithms have been suggested to binarize the grammars in such a way as to minimize parsing complexity, but the current paper shows that these techniques are not sufficient to parse longer sen- tences. Instead, this work presents a novel form of coarse-to-fine parsing which does alleviate this limitation. The rest of this paper is structured as follows. First, we introduce linear context-free rewriting systems (LCFRS). Next, we discuss and evalu- ate binarization strategies …

Content truncated to 500 words