A Least-Cost Error Corrector for LR(1)-Based Parsers

Abstract

An error corrector working with LR(1) parsers and variations such as SLR(1) and LALR(1) is studied. The corrector is able to correct and parse any input string. Upon detection of a syntax error, it operates by deleting 0 or more input symbols and inserting a terminal string that guarantees the first non-deleted symbol to be accepted by the parser. The total correction costs, as defined by a table of deletion and insertion costs, is minimized.