Efficient Incremental Processing With Categorial Grammar

EFFICIENT INCREMENTAL PROCESSING WITH CATEGORIAL GRAMMAR Abstract Some problems are discussed that arise for incremental pro- cessing using certain flezible categorial grammars, which in- volve either undesirable parsing properties or failure to allow combinations useful to incrementality. We suggest a new cal- culus which, though 'designed' in relation to categorial inter- pretatious of some notions of dependency grammar, seems to provide a degree of flexibility that is highly appropriate for in- cremental interpretation. We demonstrate how this grammar may be used for efficient incremental parsing, by employing normalisation techniques. Introduction A range of categorial grammars (CGs) have been proposed which allow considerable flexibility in the assignment of syntactic structure, a characteristic which provides for categorial treatments of extrac- tion (Ades & Steedman, 1982) and non-constituent coordination (Steedman, 1985; Dowty, 1988), and that is claimed to allow for incremental processing of natural language (Steedman, 1989). It is this lat- ter possibility that is the focus of this paper. Such 'flexible' CGs (FCGs) typically allow that grammatical sentences may be given (amongst oth- ers) analyses which are either fully or primarily left- branching. These analyses have the property of des- ignating many of the initial substrings of sentences as interpretable constituents, providing for a style of processing in which the interpretation of a sentence is generated 'on-line' as the sentence is presented. It has been argued that incremental interpretation may provide for efficient language processing -- by both humans and machines -- in allowing early fil- tering of thematically or referentially implausible readings. The view that human sentence processing is 'incremental' is supported by both introspective and experimental evidence. In this paper, we discuss FCG approaches and some problems that arise for using them as a ba- sis for incremental processing. Then, we propose a grammar that avoids these problems, and demon- strate how it may be used for efficient incremental processing. Mark Hepple University of Cambridge Computer Laboratory, New Museums Site, Pembroke St, Cambridge, UK. e-mail : mrhQuk, a¢. cam. ¢i Flexible Categorial Grammars CGs consist of two components: (i) a categorial lex- icon, which assigns to each word at least one syn- tactic type (plus associated meaning), (ii) a calculus which determines the set of admitted type combina- tions and transitions. The set of types (T) is defined recursively in terms of a set of basic types (To) and a set of operators (\ and/, for standard bidirectional CG), as the smallest set such that (i) To C T, (ii) if x,y E T, then x\y, x/y E T. 1 Intuitively, lexi- cal types specify subcategorisation requirements of words, and requirements on constituent order. The most basic (non-flexible) CGs provide only rules of application for combining types, shown in (1). We adopt a scheme for specifying the semantics of com- bination rules where the rule name identifies a func- tion that applies to the meanings of the input types in their left-to-right order to give the meaning of the result expression. (1) f: X/Y + Y =~ X (where f= …

Content truncated to 500 words