A practical method for syntactic error diagnosis and recovery

ABSTRACT

Our goal is to develop a practical syntactic error recovery method applicable within the general framework of viable prefix parsing. Our method represents an attempt to accurately diagnose and report all syntax errors without reporting errors that are not actually present. Successful recovery depends upon accurate diagnosis of errors together with sensible “correction” or alteration of the text to put the parse back on track. The issuing of accurate and helpful diagnostics is achieved by indicating the nature of the recovery made for each error encountered. The error recovery is prior to and independent of any semantic analysis of the program. However, the method does not exclude the invocation of semantic actions while parsing or preclude the use of semantic information for error recovery. The method assumes a framework in which an LR or LL parser, driven by the tables produced by a parser generator, maintains an input symbol buffer, state or prediction stack, and parse stack. The input symbol buffer contains part or all of the sequence of remaining input tokens, including the current token. The LR state stack is analogous to the LL prediction stack; except when restricting our attention to the LL case, prediction stack shall serve as a generic term indicating the LR state or LL prediction stack. The parse stack contains the symbols of the right hand sides that have not yet been reduced.

REFERENCES

• 1: Feyock, S., Lazurus, P., "Syntax-directed Correction of Syntax Errors", Software Practice and Experience, Vol. 6, 1976.
• 2: Susan L. Graham , Charles B. Haley , William N. Joy, Practical LR error recovery, ACM SIGPLAN Notices, v.14 n.8, p.168-175, August 1979
• 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: Johnson, S.C., YACC - Yet Another Compiler Compiler. Bell Laboratories, Murray Hill, 1977.
• 5: Poonen, G., "Error Recovery For LR(k) Parsers", Information Processing, August 1977.
• 6: 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]
• 7: Ripley, G.D., Druseikis, F.C., "A Statistical Analysis of Syntax Errors", Journal of Computer Languages, Vol. 3, 1978.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Diagnostics
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Parsing

General Terms:
Verification