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.