An Assessment of Locally Least-Cost Error Recovery

Locally least-cost error recovery is a technique for recovering from syntax errors by editing the input string at the point of error detection. An informal description of a parser generator which implements the technique is given. The generator takes as input an extended BNF description of a language together with a set of primitive edit costs and outputs a recursive descent syntax analyser including error recovery. Criteria for assessment of the technique are offered. Using these criteria the technique is assessed with respect to a database of over 100 example programs, and compared with an alternative local error recovery technique, that of follow set error recovery. The conclusion is that locally least-cost error recovery is more effective than follow set error recovery but much less economical in its use of storage space. The least-cost parser also runs between 15 and 20% slower than the follow set parser.