The real-time spoken language interfaces such as real-time dialogue systems, simultaneous machine interpreting systems, etc, handle with the user's speech as their input and give the responses to users in real-time. In those interfaces, the user's speech input is first analyzed in the speech recognition module. So, the speech recognition result is inputted into the natural language processing module. The recognition result is obtained as the real-time continuous sequences of words. And the output unit and timing are not determinate. Moreover, since the speech recognition module produces some analyses in real-time, it often modifies the previous output after analyzing the following input. Therefore, in such interfaces, the natural language parser is required to analyse the input `` incrementally ''.

This paper proposes an effective incremental parsing method for real-time spoken language interfaces. The method performs in two way of incremental parsing: One is to handle with new input that, piece-by-piece, is entered from left to right, and produces analysis while it is being received. The other is to handle with such arbitrary changes of the input as insertion, deletion, and replacement efficiently . The basic approach is to exploit the parts of the previous analysis for the arbitrary change of the input. Moreover, the method newly defines the syntactic relation between strucures of the word sequences that are not adjacent. With the definition, the method exploits the syntactic information of all inputted words to eliminate the needless parsing operations before applying them. We implemented this method on a workstation and made an experiment with the spoken language corpora. We have confirmed that the method can be expected to be useful for the real-time spoken language interfaces.