ERROR REPAIR IN SHIFT-REDUCE PARSERS

Local error repair of strings during CFG parsing requires the insertion and deletion of symbols in the region of a syntax error to produce a string that is error free. Rather than precalculating tables at parser generation time to assist in finding such repairs, this article shows how such repairs can be found during shift-reduce parsing by using the parsing tables themselves. This results in a substantial space saving over methods that require precalculated tables. Furthermore, the article shows how the method can be integrated with lookahead to avoid finding repairs that immediately result in further syntax errors. The article presents the results of experiments on a version of the LALR(1)-based parser generator Bison to which the algorithm was added.