## Abstract

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(n*if the grammar is unambiguous, and^{2})*O(n*in the worst case.^{3})Original language | English |
---|---|

Pages (from-to) | 318-347 |

Number of pages | 30 |

Journal | ACM Letters on Programming Languages and Systems |

Volume | 3 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1981 |