Locally Least-Cost Error Recovery in Early's Algorithm

Abstract

~While-least-cost~ error correction is fundamentally important to context-free language processing, it is inefficient w'Qhemdone globally.A locally least-cost repair method has been devised to model error recovery in conventional-~o-mpile]ts.The principles of this recovery technique have inspired a practical LL(1) method and should be of value m ~ntmg-error~rJel~a~lr m other parsing algorithms.-At each point in the syntax analysis, a locally optimal repair of't~e-next-sy-mBffl 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(n 2) if the grammar is unambiguous, and O(n 3) in the worst case.Key Words and Phrases: error repair,