Least-cost syntactic error repair using extended right context
Jon Mauney · Minds at UW (University of Wisconsin) · 1983
We present an extension to the locally least-cost repair method. Our algorithm examines several symbols to the right of the error point, and computes a least-cost repair to that entire region. The algorithm uses a modified context-free parser to consider all repairs in parallel; the parser used is that of Graham, Harrison, and Ruzzo. The repair algorithm is called only when an error is detected, and can be used in conjunction with LL(1) and LR(1) parsers. The size of the repaired region can be dynamically controlled, expanding to include all relevant context. We discuss ways to determine whether the region is large enough, and present a simple, practical test. We also present results of an initial implementation of the algorithm, and measurements of typical region sizes.