A practical method for LR and LL syntactic error diagnosis and recovery

ABSTRACT

This paper presents a powerful, practical, and essentially language-independent syntactic error diagnosis and recovery method that is applicable within the frameworks of LR and LL parsing. The method generally issues accurate diagnoses even where multiple errors occur within close proximity, yet seldom issues spurious error messages. It employs a new technique, parse action deferral, that allows the most appropriate recovery in cases where this would ordinarily be precluded by late detection of the error. The method is practical in that it does not impose substantial space or time overhead on the parsing of correct programs, and in that its time efficiency in processing an error allows for its incorporation in a production compiler. The method is language independent, but it does allow for tuning with respect to particular languages and implementations through the setting of language-specific parameters.

REFERENCES

• 1: AHO, A. V., AND PETERSON, T.J. A minimum-distance error-correcting parser for context-free languages. SIAM J. Comput. 1, 4 (Dec. 1972), 305-312.
• 2: AMERICAN NATIONAL STANDARDS INSTITUTE. Ada programming language military standard. ANSI/MIL-STD-1815A, American National Standards Institute, Washington, D.C., Jan. 1983.
• 3: Michael George Burke, A practical method for lr and ll syntactic error diagnosis and recovery, 1983
• 4: Michael Burke , Gerald A. Fisher, Jr., A practical method for syntactic error diagnosis and recovery, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.67-78, June 23-25, 1982, Boston, Massachusetts, United States
• 5: BURKE, M. G. AND FISHER, G.A. A practical method for LR and LL syntactic error diagnosis and recovery. Res. Rep. RC 11111, IBM T. J. Watson Research, Yorktown Heights, N.Y., Mar. 1985.
• 6: CHARLES, P. Implementation of a LALR parser generator. Master's thesis, Dept. of Computer Science, New York Univ., 1982.
• 7: FEYOCK, S., AND LAZURUS, P. Syntax-directed correction of syntax errors. Softw. Pract. Exper. 6, 2 (Apr.-June 1976), 207-219.
• 8: 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]
• 9: Susan L. Graham , Charles B. Haley , William N. Joy, Practical LR error recovery, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.168-175, August 06-10, 1979, Denver, Colorado, United States
• 10: JOHNSON, S.C. YACC--Yet another compiler compiler. Bell Laboratories, Murray Hill, N.J., 1977.
• 11: Jon Mauney , Charles N. Fischer, A forward move algorithm for LL and LR parsers, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.79-87, June 23-25, 1982, Boston, Massachusetts, United States
• 12: M. Dennis Mickunas , John A. Modry, Automatic error recovery for LR parsers, Communications of the ACM, v.21 n.6, p.459-465, June 1978 [doi>10.1145/359511.359519]
• 13: Thomas J. Pennello , Frank DeRemer, A forward move algorithm for LR error recovery, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.241-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512786]
• 14: PENNELLO, T. J., AND DEREMER, F.L. Practical error recovery for LR parsers. Unpublished Rep.
• 15: POONEN, G. Error recovery for LR(k) parsers. Inf. Process. 77 (Aug. 1977), 529-533.
• 16: RIPLEY, D.J. Pascal Syntax Errors Data Base. RCA Laboratories, Princeton, N. J., Apr. 1979.
• 17: RIPLEY, G. D., AND DRUSEIKIS, F.C. A statistical analysis of syntax errors. J. Comput. Lang. 3, 4 (1978), 227-240.

INDEX TERMS

Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing; Compilers

General Terms:
Algorithms, Languages