Skip to main content Skip to main navigation


On Failure of the Pruning Technique in "Error Repair in Shift-Reduce Parsers"

Eberhard Bertsch; Mark-Jan Nederhof
In: ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 21, No. 1, Pages 1-10, 1999.


A previous article presented a technique to compute the least-cost error repair by incrementally generating congurations that result from inserting and deleting tokens in a syntactically incorrect input. An additional mechanism to improve the run-time efficiency of this algorithm by pruning some of the congurations was discussed as well. In this communication we show that the pruning mechanism may lead to suboptimal repairs or may block all repairs. Certain grammatical errors in a common construct of the Java programming language also lead to the above kind of failure.

Weitere Links