An approach to automating syntax error detection recovery, and correction for LR(k) grammars.

Abstract

An automatic, language-independent syntax error detection, recovery, and correction system for LR(k) grammars is proposed. The requirement is made that the reverse of the grammar involved is also LR(k). The implications and justification for this requirement are discussed. Given that the grammar is both LR(k) and RL(k), forward and reverse parsers localize errors and define left and right error context providing a strong base from which error analysis may proceed. Possible deterministic and heuristic corrective actions to follow error analysis are presented. The definition and selection of keys from the set of terminal symbols for the grammar which enable the reverse parser to be engaged upon error detection are discussed. A model of the proposed system, implemented in an XPL compiler for a large ALGOL-like grammar, is described and the results of test programs are exampled and discussed. Possible extensions to the system are presented and areas requiring further analysis are defined.