Locally Least-Cost Error Recovery in Early's Algorithm.

Stuart Anderson, Roland Carl Backhouse

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Whilst least-cost error correction is fundamentally important to context-free language processing, it is inefficient when done globally. A locally least-cost repair method has been devised to model error recovery in conventional compilers. The principles of this recovery technique have inspired a practical LL(1) method and should be of value in implementing error repair in other parsing algorithms. At each point in the syntax analysis, a locally optimal repair of the next symbol is defined to be a string w such that w can be parsed without error and such that editing the symbol following w can be achieved at least cost, costs being defined by the Wagner-Fischer model of string-to-string correction. In this paper we describe how error recovery can be achieved in Earley's algorithm by simulating locally optimal repairs. The main result is to show that the complexity of Earley's algorithm is not affected by this process; that is, for any input string of length n, the work involved is O(n) if the given grammar is deterministic, O(n2) if the grammar is unambiguous, and O(n3) in the worst case.
Original languageEnglish
Pages (from-to)318-347
Number of pages30
JournalACM Letters on Programming Languages and Systems
Issue number3
Publication statusPublished - 1981


Dive into the research topics of 'Locally Least-Cost Error Recovery in Early's Algorithm.'. Together they form a unique fingerprint.

Cite this