A Forward Move Algorithm for LR Error Recovery

Abstract

A move algorithm, and some of its formal properties, is presented for use in a practical syntactic error scheme for LR parsers. The algorithm finds fragment (comparable to a valid prefix) just to the right of a point of error detection. For expositional purposes the algorithm is presented as parsing arbitrarily far beyond the point of error detection in a parallel mode, as long as all parses agree on the read or reduce action to be taken at each parse step. In practice the forward move is achieved serially by adding recovery states to the LR machine. Based on the formal properties of the forward move we propose an error algorithm that uses the accumulated right context. The performance of the algorithm is illustrated in a specific case and discussed in general.