The process of error recovery in interactive parsers is addressed. The primary application of the concepts is in interactive programming systems that report errors at entry and permit their immediate correction.
Starting with a brief mathematical description of an extended context-free (ECF) syntax and a simple programming language expressed in ECF syntax, the authors introduce a series of generation schemes that successively improve the ability of the parser to recover from errors so that the error may be displayed and its correction entered. The ultimate challenge is to reset the parser’s scan to a point arbitrarily far back in the input stream, because the parser may have gone considerably beyond the point where correction is needed by the time it detects the error. Given the way parsers operate, this task is nontrivial.
After describing the penultimate error recovery method, the paper concludes with a description of the authors’ experience with a transducer writing system in which these principles have been implemented.
This paper would be of most interest to someone designing systems as described above. It is clearly written and well organized; the presentation of successively more powerful recovery methods nicely highlights the logic of progressing from one stage to the next. Helpful illustrative diagrams ably assist the exposition. An extensive list of 30 references completes a well-done work.