Automatic error recovery for LR parsers

ABSTRACT

In this paper we present a scheme for detecting and recovering from syntax errors in programs. The scheme, which is based on LR parsing, is driven by information which is directly and automatically obtainable from the information that is already present in an LR parser. The approach, which is patterned after that of Levy and Graham and Rhodes, appears to provide error recovery which is both simple and powerful.

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, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
• 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: Susan L. Graham , Steven P. Rhodes, Practical syntactic error recovery in compilers, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.52-58, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512932]
• 5: 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]
• 6: E. T. Irons, An error-correcting parse algorithm, Communications of the ACM, v.6 n.11, p.669-673, Nov. 1963 [doi>10.1145/368310.368385]
• 7: James, L.R. A syntax directed error recovery method. Master's Th., Tech. Rep. CSRG-13, Comptr. Syst. Res. Group, U. of Toronto, Toronto, Ont., Canada, May 1972.
• 8: Marc Louis Joliat, On the reduced matrix representation of lr(k) parser tables., 1973
• 9: Knuth, D.E. On the translation of languages from left to right. Inform. and Control 8 (1965), 607-639.
• 10: Jacques Emmett Lafrance, Syntax-directed error recovery for compilers, 1971
• 11: Ronald Paul Leinius, Error detection and recovery for syntax directed compiler systems, 1970
• 12: Jean Levy, Automatic Correction of Syntax Errors in Programming Languages, Cornell University, Ithaca, NY, 1971
• 13: Modry, ,I.A. Syntactic error recovery for LR parsers. Master's Th. UIUCDCS-R-76-388, Dept. Comptr. Sci., U. of Illinois, Urbana, I11., 1976.
• 14: Partridge, D. Heuristic methods in the analysis of program statements. Ph.D. Th., Dept. of Comptng. and Control, U. of London, London, England, Aug. 1972.
• 15: Rhodes S.P. Practical syntactic error recovery for programming languages. Ph.D. Th., Tech. Rep. No. 15, Comptr. Sci. Dept., U. of California, Berkeley, Calif., June 1973.
• 16: Szymanski, T.G., and Williams, J.H. Non-canonical parsing. Proc. 14th Annual Symp. on Switching and Automata Theory, Oct. 1973, pp. 122-129.
• 17: Michael Harry Tindall, An interactive compile-time diagnostic system., 1975
• 18: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Design, Languages, Performance, Reliability, Theory

Keywords:
LR, automatic correction, compilers, error correction, parsing, programming languages, syntax errors