Methods for the automatic construction of error correcting parsers

Summary Methods for the automatic construction of error handling parsers are presented. The resulting parsers are capable of correcting all syntax errors by insertion and/or deletion of terminal symbols to the right of the error location. Thus, the output of the parser always corresponds to a syntactically valid program. This contributes significantly to the reliability and robustness of a compiler. The speed of parsing correct parts of a program is not affected by the presence of the error handling capability. The correction algorithm is easy to implement. Apart from the parsing tables only one character per parser state is required to control the correction process. The method is applicable to a wide class of stack automata including LL(k), LR(k), SLR(k), and LALR(k) parsers. It is shown that for LL(k) grammars error correction can be obtained as a byproduct of the canonical LL(k) parser generation. A similar result can be obtained for LR(k) grammars if the parser generator is slightly modified. The method has been successfully added to an LALR(1) parser generator.