Polynomial Time Parsing of Combinatory Categorial Grammars

POLYNOMIAL TIME PARSING OF COMBINATORY CATEGORIAL GRAMMARS* K. Vijay-Shanker Department of CIS University of Delaware Delaware, DE 19716 David J. Weir Department of EECS Northwestern University Evanston, IL 60208 Abstract In this paper we present a polynomial time pars- ing algorithm for Combinatory Categorial Grammar. The recognition phase extends the CKY algorithm for CFG. The process of generating a representation of the parse trees has two phases. Initially, a shared for- est is build that encodes the set of all derivation trees for the input string. This shared forest is then pruned to remove all spurious ambiguity. 1 Introduction Combinatory Categorial Grammar (CCG) [7, 5] is an extension of Classical Categorial Grammar in which both function composition and function application are allowed. In addition, forward and backward slashes are used to place conditions on the relative ordering of adjacent categories that are, to be com- bined. There has been considerable interest in pars- ing strategies for CCG' [4, 11, 8, 2]. One of the major problems that must be addressed is that of spurious ambiguity. This refers to the possibility that a CCG can generate a large number of (exponentially many) derivation trees that assign the same function argu- ment structure to a string. In [9] we noted that a CCG can also generate exponentially many genuinely am- biguous (non-spurious)derivations. This constitutes a problem for the approaches cited above since it re- suits in their respective algorithms taking exponential time in the worst case. The algorithm we present is the first known polynomial time parser for CCG. The parsing process has three phases. Once the recognizer decides (in the first phase) that an input can be generated by the given CCG the set of parse *This work was partially supported by NSF grant IRI- 8909810. We are very grateful to Aravind Joshi, Michael Niv, Mark Steedman and Kent Wittenburg for helpful discussior~. 1 trees can be extracted in the second phase. Rather than enumerating all parses, in Section 3, we describe how they can be encoded by means of a shared forest (represented as a grammar) with which an expoo en- tial number of parses are encoded using a polynomi- ally bounded structure. This shared forest encodes all derivations including those that are spuriously am- biguous. In Section 4.1, we show that it is possible to modify the shared forest so that it contains no spuri- ous ambiguity. This is done (in the third phase) by traversing the forest, examining two levels of nodes at each stage, detecting spurious ambiguity locally. The three stage process of recognition, building the shared forest, and eliminating spurious ambiguity takes poly- nomial time. 1.1 Definition of CCG A CCG, G, is denoted by (VT, VN, S, f, R) where VT is a finite set of terminals (lexical items), VN is a finite set of nonterminals (atomic categories), S is a dis- tinguished member of VN, f is a function that maps elements of VT to finite sets of categories, R is a fi- nite …

Content truncated to 500 words