A Practical Method for Lr and Ll Syntactic Error Diagnosis and Recovery

Candidate: Burke,Michael George

Abstract

A powerful, practical, and language-independent method for diagnosing and recovering from syntactic errors within the LR and LL parsing frameworks is described. The method proceeds in three phases. The simple recovery phase attempts a single token modification of the source text, scope recovery attempts a multiple token insertion to close one or more open scopes, and secondary recovery involves a multiple deletion of tokens surrounding the error point. When the token at which the error is detected is not the token that is in error, points on the parse stack must be considered if the error is to be corrected. Condensation that has occurred on the parse stack, however, is sometimes harmful in this context. Also, in some of the parsing frameworks under consideration, unwanted condensation may occur even if the error is detected at the point at which it occurs. This problem motivates the existence of four versions of the method involving tradeoffs between the quality of error recovery and efficiency with respect to space and time. Techniques are described that make the method efficient in practice. Other implementation issues, such as language specific tuning and the issuing of diagnostic messages, are discussed. Empirical results are presented that demonstrate that the versions of the method offer choices ranging from very high quality recovery with reasonable efficiency to high quality recovery with excellent efficiency.