A scheme for LR(k) parsing with error recovery part II: error recovery

Abstract

The paper is the second in a series of three papers devoted to a detailed study of LR(k) parsing with error recovery and correction. Error recovery in LR(k) parsing of a context-free grammar is formalized by extending an LR(k) parser of the grammar such that it accepts all strings over the terminal vocabulary. The parse produced by this extension for a terminal string is a right parse if the string is in the language. In the case of a string not in the language the parse produced by the extension contains so-called error productions which represent the error recovery actions performed by the extension. The treatment is based on the formalization of LR(k) parsing presented in the first paper in the series and it covers practically all error recovery methods designed for LR(k) parsing.

Keywords:

• Formal systems
• context-free grammars
• canonical LR(k)
• LALR(k) and SLR(k) grammars and parsers
• error detection and recovery

C.R. Categories:

• 4.12
• 5.23

†The work of this author was supported by the Emil Aaltonen Foundation.

‡Department of Mathematics, University of California, Santa Barbara, California 93106.

†The work of this author was supported by the Emil Aaltonen Foundation.

‡Department of Mathematics, University of California, Santa Barbara, California 93106.

Notes

†The work of this author was supported by the Emil Aaltonen Foundation.

‡Department of Mathematics, University of California, Santa Barbara, California 93106.