Locally Least-Cost Error Correctors for Context-Free and Context-Sensitive Parsers

Abstract

A model of error correction is presented. Upon detection of a syntax error, a locally least-cost corrector operates by deleting 0 or more input symbols and inserting a terminal string that guarantees that the first non-deleted symbol will be accepted by the parser. The total correction cost, as defined by a table of deletion and insertion costs, is minimized. Previous work with the LL(1) parsing technique is summarized and a locally least-cost error corrector for LR(1)-based parsers is developed. Correctness as well as time and space complexity are discussed. In particular, linearity is established in the case of a bounded depth parse stack. Implementation results are presented. Attributed grammars can be used to specify the context-sensitive syntax of programming languages. A formal presentation of Attribute-Free LL(1) parsing is given and a locally least-cost error corrector for AF-LL(1) parsers is developed for the case in which the attributes that control context-sensitive correctness have finite domains. The algorithm is shown to have the same properties as its LL(1) and LR(1) counterparts.