tailieunhanh - Báo cáo khoa học: "Efficient Normal-Form Parsing for Combinatory Categorial Grammar*"

Under categorial grammars that have powerful rules like composition, a simple n-word sentence can have exponentially many parses. Generating all parses is inefficient 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 technique. The parser is proved to find exactly one parse in each semantic equivalence class of allowable parses; that is, spurious ambiguity (as carefully defined) is shown to be both safely and completely eliminated. . | 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 Abstract Under categorial grammars that have powerful rules like composition a simple n-word sentence can have exponentially many parses. Generating all parses is inefficient 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 technique. The parser is proved to find exactly one parse in each semantic equivalence 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 g NP. and Mary pretends to like S Np the big galoot in the corner. b. Extraction Everybody at this party whom John likesjg pjp is a big galoot. 2 a. John likes Mary s NP- b. John likes g Mp Mary. The practical problem of extra parses in 2 becomes 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 3 the .