Efficient techniques for parsing with tree automata

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 2042–2051, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Efficient techniques for parsing with tree automata Jonas Groschwitz and Alexander Koller Department of Linguistics University of Potsdam Germany groschwi|akoller@uni-potsdam.de Mark Johnson Department of Computing Macquarie University Australia mark.johnson@mq.edu.au Abstract Parsing for a wide variety of grammar for- malisms can be performed by intersecting finite tree automata. However, naive im- plementations of parsing by intersection are very inefficient. We present techniques that speed up tree-automata-based pars- ing, to the point that it becomes practically feasible on realistic data when applied to context-free, TAG, and graph parsing. For graph parsing, we obtain the best runtimes in the literature. 1 Introduction Grammar formalisms that go beyond context-free grammars have recently enjoyed renewed atten- tion throughout computational linguistics. Clas- sical grammar formalisms such as TAG (Joshi and Schabes, 1997) and CCG (Steedman, 2001) have been equipped with expressive statistical mod- els, and high-performance parsers have become available (Clark and Curran, 2007; Lewis and Steedman, 2014; Kallmeyer and Maier, 2013). Synchronous grammar formalisms such as syn- chronous context-free grammars (Chiang, 2007) and tree-to-string transducers (Galley et al., 2004; Graehl et al., 2008; Seemann et al., 2015) are being used as models that incorporate syntac- tic information in statistical machine translation. Synchronous string-to-tree (Wong and Mooney, 2006) and string-to-graph grammars (Chiang et al., 2013) have been applied to semantic parsing; and so forth. Each of these grammar formalisms requires its users to develop new algorithms for parsing and training. This comes with challenges that are both practical and theoretical. From a theoretical per- spective, many of these algorithms are basically the same, in that they rest upon a CKY-style pars- ing algorithm which recursively explores substruc- tures of the input object and assigns them non- terminal symbols, but their exact relationship is rarely made explicit. On the practical side, this parsing algorithm and its extensions (e.g. to EM training) have to be implemented and optimized from scratch for each new grammar formalism. Thus, development time is spent on reinventing wheels that are slightly different from previous ones, and the resulting implementations still tend to underperform. Koller and Kuhlmann (2011) introduced Inter- preted Regular Tree Grammars (IRTGs) in order to address this situation. An IRTG represents a language by describing a regular language of derivation trees, each of which is mapped to a term over some algebra and evaluated there. Gram- mars from a wide range of monolingual and syn- chronous formalisms can be mapped into IRTGs by using different algebras: Context-free and tree- adjoining grammars use string algebras of differ- ent kinds, graph grammars can be captured by us- ing graph algebras, and so on. In addition, IRTGs come with a universal parsing algorithm based on closure results for tree automata. Implementing and optimizing this parsing algorithm once, one could apply it to all grammar formalisms that can be mapped to IRTG. However, while Koller and Kuhlmann show that asymptotically optimal …

Content truncated to 500 words