Locally Least-Cost Error Recovery in Earley'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.