tailieunhanh - Báo cáo khoa học: "POLYNOMIAL TIME PARSING OF COMBINATORY CATEGORIAL GRAMMARS*"

In this paper we present a polynomial time parsing 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 forest 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. | 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 parsing 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 forest 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 combined. There has been considerable interest in parsing 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 argument structure to a string. In 9 we noted that a CCG can also generate exponentially many genuinely ambiguous non-spurious derivations. This constitutes a problem for the approaches cited above since it results 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 Wittenberg for helpful discussions. trees can be extracted in the second phase. Rather than enumerating all parses