Efficient Normal-Form Parsing for Combinatory Categorial Grammar

Efficient Normal-Form Parsing for Combinatory Categorial Grammar* Jason Eisner Dept. of Computer and Information Science University of Pennsylvania 200 S. 33rd St., Philadelphia, PA 19104-6389, USA j eisner@linc, cis. upenn, edu Abstract Under categorial grammars that have pow- erful rules like composition, a simple n-word sentence can have exponentially many parses. Generating all parses is ineffi- cient and obscures whatever true semantic ambiguities are in the input. This paper addresses the problem for a fairly general form of Combinatory Categorial Grammar, by means of an efficient, correct, and easy to implement normal-form parsing tech- nique. The parser is proved to find ex- actly one parse in each semantic equiv- alence class of allowable parses; that is, spurious ambiguity (as carefully defined) is shown to be both safely and completely eliminated. 1 Introduction Combinatory Categorial Grammar (Steedman, 1990), like other "flexible" categorial grammars, suffers from spurious ambiguity (Wittenburg, 1986). The non-standard constituents that are so crucial to CCG's analyses in (1), and in its account of into- national focus (Prevost ~ Steedman, 1994), remain available even in simpler sentences. This renders (2) syntactically ambiguous. (1) a. Coordination: [[John likes]s/NP, and [Mary pretends to like]s/NP], the big galoot in the corner. b. Extraction: Everybody at this party [whom [John likes]s/NP] is a big galoot. (2) a. John [likes Mary]s\NP. b. [.John likes]s/N P Mary. The practical problem of "extra" parses in (2) be- comes exponentially worse for longer strings, which can have up to a Catalan number of parses. An *This material is based upon work supported under a National Science Foundation Graduate Fellowship. I have been grateful for the advice of Aravind Joshi, Nobo Komagata, Seth Kulick, Michael Niv, Mark Steedman, and three anonymous reviewers. exhaustive parser serves up 252 CCG parses of (3), which must be sifted through, at considerable cost, in order to identify the two distinct meanings for further processing. 1 (3) the galoot in the corner NP]N N (N\N)/NP NP]N N that I said Mary (N\N)](S/NP) S/(S\NP) (S\NP)]$ S](S\NP) pretends to (S\NP)](Sin f \NP) (Sin f \NP)/(Sstem \NP) like (Sstem\NP)/NP This paper presents a simple and flexible CCG parsing technique that prevents any such explosion of redundant CCG derivations. In particular, it is proved in §4.2 that the method constructs exactly one syntactic structure per semantic reading--e.g., just two parses for (3). All other parses are sup- pressed by simple normal-form constraints that are enforced throughout the parsing process. This ap- proach works because CCG's spurious ambiguities arise (as is shown) in only a small set of circum- stances. Although similar work has been attempted in the past, with varying degrees of success (Kart- tunen, 1986; Wittenburg, 1986; Pareschi & Steed- man, 1987; Bouma, 1989; Hepple & Morrill, 1989; KSnig, 1989; Vijay-Shanker & Weir, 1990; Hepple, 1990; Moortgat, 1990; ttendriks, 1993; Niv, 1994), this appears to be the first full normal-form result for a categorial formalism having more than context- free power. 2 Definitions and Related Work CCG may be regarded as a generalization of context- free …

Content truncated to 500 words