Interactive Incremental Chart Parsing

Interactive Incremental Chart Parsing Mats Wirdn Department of Computer and Information Science LinkSping University S-58183 LinkSping, Sweden mgw@ida.liu.se Abstract This paper presents an algorithm for incremental chart parsing, outlines how this could be embed- ded in an interactive parsing system, and discusses why this might be useful. Incremental parsing here means that input i8 analysed in a piecemeal fash- ion, in particular allowing arbitrary changes of previ- ous input without exhaustive reanalysis. Interactive parsing means that the analysis process is prompted immediately at the onset of new input, and possibly that the system then may interact with the user in order to resolve problems that occur. The combina- tion of these techniques could be used as a parsing kernel for highly interactive and ~reactive" natural- language processors, such as parsers for dialogue systems, interactive computer-aided translation sys- tems, and language-sensitive text editors. An incre- mental chart parser embodying the ideas put for- ward in this paper has been implemented, and an embedding of this in an interactive parsing system is near completion. 1 Background and Introduction 1.1 The Problem Ideally, a parser for an interactive natural-language system ought to analyse input in real time in such a way that the system produces an analysis of the in- put while this is being received. One aspect of this is that the system should be able to gkeep up ~ with This research has been supported by the National Swedish Board for Technical Development. The system is imple- mented on machines donated by the Xerox Corporation through their University Grants Program. I would like to thank several people for fruitful discussions on the topics of this paper, in particular Lars Ahrenberg (also for commenting on drafts), Bernt Nilsson, and Peter Fritzson; furthermore Nile D~Ibiick, Arne JSnsson, Magnus Merkel, Henry Thompson, and an anonymous referee. In addition, I would like to thank Ulf Dahl~n, Ass Detterfelt, Mikael Karle- son, Per Larsee, Jukka Nylund, and Michael Spicar for imple- menting (the interactive portion of) LIPS. new input that, piece by piece, is entered from left to right. Another aspect is that it ought to be able to keep up also with piecemeal changes of previous input. For example, in changing one word in the be- ginning of some utterance(s), one would not want all the input (either from the beginning or from the change point) to be completely reanalysed. From the perspective of efficiency as well as of modelling intelligent behaviour, the amount of processing re- quired to analyse an update ought to be somehow correlated with the difficulty of this update. Thus, a necessary (but not sufficient) condition for realiz- ing a real-time parsing system as suggested above is an interactive and incremental parsing system. The goal of this paper is to develop a basic machinery for incremental chart parsing and to outline how this could be embedded in an interactive parsing system. 1.2 Incremental Parsing The word "incremental ~ has been used in two dif- fering senses in the (parsing) literature. The …

Content truncated to 500 words