Locally least-cost error repair in LR parsers
Carl Cerecke · UC Research Repository (University of Canterbury) · 2003
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.