An Assessment of Locally Least-Cost Error Recovery

S. O. Anderson, R. C. Backhouse, E. H. Bugge, C. P. Stirling

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)15-24
Number of pages10
JournalThe Computer Journal
Issue number1
Publication statusPublished - 1983


Dive into the research topics of 'An Assessment of Locally Least-Cost Error Recovery'. Together they form a unique fingerprint.

Cite this