Error recovery for Simple LR(k) parsers

ABSTRACT

A procedure is described for augmenting a Simple LR(k) parser with new states which enable the extended parser to continue parsing the input after an error is detected. Examples of the error recovery technique are given.

REFERENCES

• 1: 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]
• 2: 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]
• 3: F. C. Druseikis, Techniques for error recovery and error correction in simple LR(k) parsers, technical report, Department of Computer Science, The University of Arizona, April, 1976.
• 4: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 5: T. Anderson, T. Eve, and J. J. Horning, Efficient LR(k) parsers, Acta Informatica, vol. 2, 1973, 12-39.
• 6: F. C. Druseikis, SLR(1) parser generator user's manual, technical report, Department of Computer Science, The University of Arizona, December, 1975.

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:
Design, Languages, Performance, Verification