Computer Science and
     Software Engineering

Computer Science and Software Engineering

PHD 03/03

Locally least-cost error repair in LR parsers

Carl Cerecke
Department of Computer Science
University of Canterbury

Abstract

This thesis presents some methods for improving the efficiency and effectiveness of locally least-cost error repair algorithms for an LR-based parser. Three different algorithms for reducing the search space are described and compared using a collection of 59,643 incorrect Java programs collected from novice programmers. Two of the algorithms prove particularly effective at reducing the search space. Also presented is a more efficient priority queue implementation for storing transformations of the input string. The effect on repairs of different grammars describing the same language is investigated, and a comparison of different methods of assigning costs to edit operations is performed.