Optimal Parsing Strategies for Linear Context-Free Rewriting Systems

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 769–776, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Optimal Parsing Strategies for Linear Context-Free Rewriting Systems Daniel Gildea Computer Science Department University of Rochester Rochester, NY 14627 Abstract Factorization is the operation of transforming a production in a Linear Context-Free Rewrit- ing System (LCFRS) into two simpler produc- tions by factoring out a subset of the nontermi- nals on the production’s righthand side. Fac- torization lowers the rank of a production but may increase its fan-out. We show how to apply factorization in order to minimize the parsing complexity of the resulting grammar, and study the relationship between rank, fan- out, and parsing complexity. We show that it is always possible to obtain optimum parsing complexity with rank two. However, among transformed grammars of rank two, minimum parsing complexity is not always possible with minimum fan-out. Applying our factorization algorithm to LCFRS rules extracted from de- pendency treebanks allows us to find the most efficient parsing strategy for the syntactic phe- nomena found in non-projective trees. 1 Introduction Gómez-Rodríguez et al. (2009a) recently examined the problem of transforming arbitrary grammars in the Linear Context-Free Rewriting System (LCFRS) formalism (Vijay-Shankar et al., 1987) in order to reduce the rank of a grammar to 2 while minimiz- ing its fan-out. The work was motivated by the desire to develop efficient chart-parsing algorithms for non-projective dependency trees (Kuhlmann and Nivre, 2006) that do not rely on the independence assumptions of spanning tree algorithms (McDon- ald et al., 2005). Efficient parsing algorithms for general LCFRS are also relevant in the context of Synchronous Context-Free Grammars (SCFGs) as a formalism for machine translation, as well as the de- sire to handle even more general synchronous gram- mar formalisms which allow nonterminals to cover discontinuous spans in either language (Melamed et al., 2004; Wellington et al., 2006). LCFRS provides a very general formalism which subsumes SCFGs, the Multitext Grammars of Melamed et al. (2004), as well as mildly context-sensitive monolingual for- malisms such as Tree Adjoining Grammar (Joshi and Schabes, 1997). Thus, work on transforming general LCFRS grammars promises to be widely ap- plicable in both understanding how these formalisms interrelate, and, from a more practical viewpoint, de- riving efficient parsing algorithms for them. In this paper, we focus on the problem of trans- forming an LCFRS grammar into an equivalent grammar for which straightforward application of dynamic programming to each rule yields a tabular parsing algorithm with minimum complexity. This is closely related, but not equivalent, to the prob- lem considered by Gómez-Rodríguez et al. (2009a), who minimize the fan-out, rather than the parsing complexity, of the resulting grammar. In Section 4, we show that restricting our attention to factorized grammars with rank no greater than 2 comes at no cost in parsing complexity. This result may be sur- prising, as Gómez-Rodríguez et al. (2009a) com- ment that “there may be cases in which one has …

Content truncated to 500 words