Computer Sciences Dept.

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

Bernard A. Dion

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.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home