Predictive Combinators: A Method for Efficient Processing of Combinatory Categorial Grammars

PREDICTIVE COMBINATORS" A METHOD FOR EFFICIENT PROCESSING OF COMBINATORY CATEGORIAL GRAMMARS Kent Wittenburg MCC, Human Interface Program 3500 West Balcones Center Drive Austin, TX 78759 Department of Linguistics University of Texas at Austin Austin, TX 78712 ABSTRACT Steedman (1985, 1987) and others have proposed that Categorial Grammar, a theory of syntax in which grammati- cal categories are viewed as functions, be augmented with operators such as functional composition and type raising in order to analyze • noncanonical" syntactic constructions such as wh- extraction and node raising. A consequence of these augmentations is an explosion of semantically equivalent derivations admitted by the grammar. The present work proposes a method for circumventing this spurious ambiguity problem. It involves deriving new, specialized combinators and replacing the orginal basic combinators with these derived ones. In this paper, examples of these predictive combin~tor8 are offered and their effects illustrated. An al- gorithm for deriving them, as well as s discussion of their semantics, will be presented in forthcoming work. Introduction In recent years there has been a resurgence of interest in Categorial Grammar (Adjukeiwicz 1935; Bar-Hillel 1953). The work of Steedman (1985, 1987) and Dowry (1987) is rep- resentative of one recent direction in which Categorial Gram- mar (CG) has been taken, in which the operations of func- tional composition and type raising have figured in analyses of "noncanonical" structures such as wh- dependencies and nonconstituent conjunction. Based on the fact that such operations have their roots in the ¢ombinator~/ c~lc~lua (Curry and Feys 1958), this line of Categorial Grammar has come to be known as Combinatory Categorial Grammar (CCG). While such an approach to syntax has been demonstrated to be suitable for computer implementation with unification-based grammar formalisms (Wittenburg 1986a), doubts have arisen over the efficiency with which such grammars can be processed. Karttunen (1986), for in- stance, argues for an alternative to rules of functional com- position and type raising in CGs on such grounds. 1 Other researchers working with Categorial Unification Grammars consider the question of what method to use for long-distance dependencies an open one (Uszkoreit 1986; Zeevat, Klein, and Calder 1986). The property of Combinatory Categorial Grammars that has occasioned concerns about processing is spurious am- biguity: CCGs that directly use functional composition and type raising admit alternative derivations that nevertheless result in fully equivalent parses from a semantic point of view. In fact, the numbers of such semantically equivalent derivations can multiply at an alarming rate. It was shown in Wittenburg (1986a) that even constrained versions of func- tional composition and type raising can independently cause the number of semantically equivalent derivations to grow at rates exponential in the length of the input string. 2 While this spurious ambiguity property may not seem to be a par- titular problem if a depth-first (or best-first) parsing algo- rithm is used-after all, if one can get by with producing just one derivation, one has no reason to go on generating the remaining equivalent ones-the fact is that both in cases where …

Content truncated to 500 words