A forward move algorithm for LR error recovery

ABSTRACT

A "forward move algorithm", and some of its formal properties, is presented for use in a practical syntactic error recovery scheme for LR parsers. The algorithm finds "valid fragment" (comparable to a valid prefix) just to the right of a point of error detection. For expositional purposes the algorithm is presented as parsing arbitrarily far beyond the point of error detection in a "parallel" mode, as long as all parses agree on the read or reduce action to be taken at each parse step. In practice the forward move is achieved serially by adding "recovery states" to the LR machine. Based on the formal properties of the forward move we propose an error recovery algorithm that uses the accumulated right context. The performance of the recovery algorithm is illustrated in a specific case and discussed in general.

REFERENCES

• 1: A. V. Aho , S. C. Johnson, LR Parsing, ACM Computing Surveys (CSUR), v.6 n.2, p.99-124, June 1974 [doi>10.1145/356628.356629]
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971 [doi>10.1145/362619.362625]
• 4: {DeR 77} DeRemer, Frank, "Tree-affix Dendrogrammars", research proposal to NSF, Information Sciences, University of California, Santa Cruz, CA. 95064, 1977.
• 5: {D&R 76} Druseikis, Frederick C. and G. David Ripley, "Error Recovery for Simple LR (k) Parsers", Dept. of Computer Science, Univ. of Arizona, Tucson, Az. 85721, 1976.
• 6: {D&R 77} Druseikis, Frederick C. and G. David Ripley, "Extended SLR (k) Parsers for Error Recovery and Repair", Dept. of Computer Science, Univ. of Arizona, Tucson, Az. 85721, Feb. 1977.
• 7: Susan L. Graham , Steven P. Rhodes, Practical syntactic error recovery, Communications of the ACM, v.18 n.11, p.639-650, Nov. 1975 [doi>10.1145/361219.361223]
• 8: {H&U 69} Hopcroft, John E. and Jeffrey D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Mass., 1969.
• 9: {Kos 71} Koster, C. H. A., "Affix Grammars", in Algol 68 Implementation, J. E. L. Peck (ed.), Amsterdam, North Holland, 1971.
• 10: {MHW 70} McKeeman, W. M., J. J. Horning, and D. B. Wortman, A Compiler Generator, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1970.
• 11: {O'H 76} O 'Hare, Michael F., "Modification of the LR (k) Parsing Technique to Include Automatic Syntactic Error Recovery", senior thesis, Univ. of Calif. at Santa Cruz, Santa Cruz, CA. 95064, June 1976.
• 12: {Pen 77} Pennello, Thomas J., "Error Recovery for LR Parsers", M.Sc. Thesis, Information Sciences, University of California at Santa Cruz, Santa Cruz, CA. 95064, June 1977.
• 13: {Wat 75} Watt, David, "The Parsing Problem for Affix Grammar", Department of Computer Science, University of Glasgow, Glasgow, Scotland, 1975.
• 14: Niklaus Wirth, Systematic Programming: An Introduction, Prentice Hall PTR, Upper Saddle River, NJ, 1973

INDEX TERMS

Keywords:
LALR (k), LR (k), SLR (k), error recovery, parsing, syntax errors