Computer Sciences Dept.

A Simple, Fast, and Effective LL(1) Error Repair Algorithm

Charles N Fischer and Jon Mauney

Validation and locally least-cost repair are two simple and effective techniques for dealing with syntax errors. We show how the two can be combined into an efficient and effective error-handler for use with LL(1) parsers. Repairs are computed using an extension of the FMQ algorithm. Tables are created as necessary, rather than precomputed, and possible repairs are kept in a priority queue. Empirical results show that the repairs chosen with this strategy are of very high quality and that speed is quite acceptable.

Download this report (PDF)

Return to tech report index

Computer Science | UW Home