Incremental Parsing and Reason Maintenance

The purpose of this paper is to compare different ways of adopting reason-maintenance techniques in incremental parsing (and interpretation). A reasonmaintenance system supports incremental tbrmation and revision of beliefs. By viewing the construction of partial analyses of a text as analogous to forming beliefs about the meanings of its parts, a relation between parsing and reason maintenance can be conceived. In line with this, reason maintenance can bc used for realizing a strong notion of incremental parsing, allowing for revisions of previous analyses. Moreover, an assumption-based reason-maintenance system (ATMS) can be used to support eftieicnt comparisons of (competing) interpretations. The paper argues for an approach which is an extension of chart parsing, but which also can be seen as a system consisting of an inference engine (the parser proper) coupled with a simplified ATMS.  This paper focuses on the problem of incremental parsing (and to some extent interpretation); in particular, how reason-maintenance techniques can be used to achieve a strong notion of incrementality allowing for piecemeal construction, revision, and comp;~rison of partial analyses. Human language understanding is apparently incremental in the sense of proceeding in a piecemeal fashion, (ideally) carried out in small, grad= ual steps as each word is encountered (Tyler and Marslen-Wilson 1977, Marslen-Wilson and Tyler 1980). Work on incremental parsing and interpretation is typically motivated by a desire to model, or mimic, (aspects of) this behaviour, for example, Bobrow and Webber (1980), Ades and Steedman (1982), Mellish (1985), Pulman (1985), and Haddock (1987~ 1988~ 1990). tlowever, there are also clear-cut computational reasons for trying to attain incrernentality. Sparked This research has been supported by the National Swedish Board for Technical Development. off by the rapid development of increasingly powerful, distributed computer hardware, a paradigm of "immediate computation" is gaining popularity in interactive applications like WYSIWYG word processing, spreadsheet programs, and programminglanguage editors (Reps and Teitelbaum 1984, 1987). It is interesting to consider similar systems applied to interactive natural-language processing. The point is that incrementality is a prerequisite of the reactiw~, real~time-based behaviour of such systems. Furthermore, systems that mix for example deictic and natural-language input require that linguistic status be given to sentence fragments, thus demanding incremental analysis (Kobsa et al. 1986). One body of work which appears to be usefifl in incremental parsing and interpretation is r e , o n (or truth) maintenanceJ A reason-maintenance system (RMS) supports incremental formation and revision of beliefs. By viewing the construction of partial analyses of a text as analogous to forming beliefs about the meanings of its parts, a relation between parsing and reason maintenance can be conceived. An RMS is coupled with an inference engine (for example, a parser) which makes inferences within the problem domain, and the overall, combined system can be seen as an inferential problem solver. The RMS makes use of two data structures, nodes and justifications. A node represents a datum provided by the inference engine, such as an assumption or an inferred proposition. Whenever a datum is inferred from a conjunction of other data, the RMS records this dependency ms a justification which relates the respective nodes. The RMS thus keeps track of what data are believed and disbelieved, and why, given the inferences made so far. The traditional approach, justification-based reason maintenance, JTMS (Doyle 1979), is to maintain a (global) belief by associating with each node a status of in (indicating belief in the corresponding datum) or out (indicating lack of belief in the datum) such that every justification is satisfied. 2 The entire set of (consistent) in data make up the cur1 For an excellent introduction to reason maintenance, see Reinfrank (1989). 2I prefer the term "reason maintenance" but use the standard abbreviations "ATMS" and "JTMS" (where "T" stands for "truth" ).