DEPARTMENT OF COMPUTER SCIENCE
DOCTORAL DISSERTATION DEFENSE


Candidate: William Kirk Snyder
Advisor: Jacob T. Schwartz
Non-Correcting Error Recovery For LR Parsers

Abstract

In recent years much effort has been devoted to the automatic generation of parsers, with considerable success. The error-handling mechanisms of these parsers are still not completely satisfactory, however. Currently available techniques are either too slow for practical production compilers, or they leave open the possibility of many spurious diagnostic messages. This thesis presents a parsing technique designed to minimize the frequency of spurious or misleading diagnostic messages emitted by the compiler, without the efficiency cost of similarly robust parsers. The technique parses program text following a syntax error as a `suffix' in the programming language, reporting errors in invalid suffixes. The system achieves its high efficiency by accepting a superset of the suffixes of the language being parsed, but a sufficiently small superset that very few errors are undetected. The technique described has been fully implemented, and a number of experiments on typical syntax errors in various programming languages are presented. We describe our parsing system in detail and assess its strengths and weaknesses relative to other parsing systems.