Practical LR error recovery

ABSTRACT

We present a practical, language independent mechanism for error recovery in LR parsers. The method is easy to implement in existing parser generators. It uses only the normal parse tables and a small amount of symbol cost information. It is possible to use compressed parse tables with the method, as well as other LR augmentations such as precedence and associativity declarations. The method is efficient enough to be used in environments where space and time are at a premium. Our method utilizes a number of previous error recovery ideas: forward moves in the input after detection of errors to incorporate right context, recovery choice based on weighted costs, and the use of special productions to indicate major productions in the grammar for error recovery. The method also makes use of semantic information in choosing between possible recovery actions. We have implemented the method in a production Pascal translator which has been in use for instruction at a number of universities for two years. We report here on measurements of our system on a standard data base of Pascal programs with errors.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: Frederick C. Druseikis , G. David Ripley, Error recovery for Simple LR(k) parsers, Proceedings of the annual conference, p.396-400, October 20-22, 1976, Houston, Texas, United States [doi>10.1145/800191.805624]
• 3: 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]
• 4: James, L. R. A Syntax Directed Error Recovery Method. M. S. Thesis, Tech. Report CSRG-13. Computer Systems Research Group, University of Toronto, May 1972.
• 5: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• 6: Johnson, S.C. YACC — Yet Another Compiler Compiler. Bell Laboratories, Murray Hill, 1977.
• 7: Joy, W.N., Graham, S.L., and Haley, C.B. Berkeley Pascal User's Manual Version 1.1. Computer Science Division, University of California at Berkeley, April 1979.
• 8: 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]
• 9: Modry, J.A. Syntactic Error Recovery for LR Parsers. M.S. Thesis, Univ. Illinois, 1976.
• 10: 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]
• 11: Ajit B. Pai , Richard B. Kieburtz, Global context recovery: A new strategy for parser recovery from syntax errors, Proceedings of the 1979 SIGPLAN symposium on Compiler construction, p.158-167, August 06-10, 1979, Denver, Colorado, United States
• 12: Rhodes, S. P. Practical Syntactic Error Recovery for Programming Languages. Ph. D. Dissertation. Tech. Report #15. Computer Science Division, University of California, Berkeley. June, 1973.
• 13: Ripley, G. David and Druseikis, Frederick C. A Statistical Analysis of Syntax Errors. Journal of Computer Languages, 3, 1978.
• 14: Niklaus Wirth, Algorithms + Data Structures = Programs, Prentice Hall PTR, Upper Saddle River, NJ, 1978

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Error handling and recovery

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

General Terms:
Verification