A New Parsing Algorithm for Combinatory Categorial Grammar

A New Parsing Algorithm for Combinatory Categorial Grammar Marco Kuhlmann Department of Computer and Information Science Linköping University, Sweden marco.kuhlmann@liu.se Giorgio Satta Department of Information Engineering University of Padua, Italy satta@dei.unipd.it Abstract We present a polynomial-time parsing algo- rithm for CCG, based on a new decomposition of derivations into small, shareable parts. Our algorithm has the same asymptotic complex- ity, O.n6/, as a previous algorithm by Vijay- Shanker and Weir (1993), but is easier to un- derstand, implement, and prove correct. 1 Introduction Combinatory Categorial Grammar (CCG; Steedman and Baldridge (2011)) is a lexicalized grammar for- malism that belongs to the class of so-called mildly context-sensitive formalisms, as characterized by Joshi (1985). CCG has been successfully used for a wide range of practical tasks including data-driven parsing (Clark and Curran, 2007), wide-coverage se- mantic construction (Bos et al., 2004; Kwiatkowski et al., 2010; Lewis and Steedman, 2013) and machine translation (Weese et al., 2012). Several parsing algorithms for CCG have been presented in the literature. Earlier proposals show running time exponential in the length of the input string (Pareschi and Steedman, 1987; Tomita, 1988). A breakthrough came with the work of Vijay-Shanker and Weir (1990) and Vijay-Shanker and Weir (1993) who report the first polynomial-time algorithm for CCG parsing. Until this day, this algorithm, which we shall refer to as the V&W algorithm, remains the only published polynomial-time parsing algorithm for CCG. However, we are not aware of any practical parser for CCG that actually uses it. We speculate that this has two main reasons: First, some authors have argued that linguistic resources available for CCG can be covered with context-free fragments of the formalism (Fowler and Penn, 2010), for which more efficient parsing algorithms can be given. Sec- ond, the V&W algorithm is considerably more com- plex than parsing algorithms for equivalent mildly context-sensitive formalisms, such as Tree-Adjoin- ing Grammar (Joshi and Schabes, 1997), and is quite hard to understand, implement, and prove correct. The V&W algorithm is based on a special decom- position of CCG derivations into smaller parts that can then be shared among different derivations. This sharing is the key to the polynomial runtime. In this article we build on the same idea, but develop an alternative polynomial-time algorithm for CCG parsing. The new algorithm is based on a different decomposition of CCG derivations, and is arguably simpler than the V&W algorithm in at least two re- spects: First, the new algorithm uses only three basic steps, against the nine basic steps of the V&W parser. Second, the correctness proof of the new algorithm is simpler than the one reported by Vijay-Shanker and Weir (1993). The new algorithm runs in time O.n6/ where n is the length of the input string, the same as the V&W parser. We organize our presentation as follows. In Sec- tion 2 we introduce CCG and the central notion of derivation trees. In Section 3 we start with a simple but exponential-time parser for CCG, from which we derive our polynomial-time …

Content truncated to 500 words