An Insertion Only Error Corrector for LR(1), LALR(1), SLR(1) 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. It chooses least-cost insertions (as defined by the user) in correcting syntax errors. Moreover, the error-corrector can be generated automatically from the grammar and a table of terminal symbol insertion costs. An algorithm that decides if a given LR(1) grammar is insert-correctable is presented. Correctness and linearity of the error-corrector is established.