Show simple item record

dc.contributor.authorDion, Bernard A.en_US
dc.description.abstractA 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.en_US
dc.publisherUniversity of Wisconsin-Madison Department of Computer Sciencesen_US
dc.titleLocally Least-Cost Error Correctors for Context-Free and Context-Sensitive Parsersen_US
dc.typeTechnical Reporten_US

Files in this item


This item appears in the following Collection(s)

  • CS Technical Reports
    Technical Reports Archive for the Department of Computer Sciences at the University of Wisconsin-Madison

Show simple item record