Eberhard Bertsch
Abstract
A previous article presented a technique to compute the least-cost error repair by incrementally generating configurations that result from inserting and deleting tokens a syntactically incorrect input. An additional mechanism to improve the run-time efficiency of this algorithm by pruning some of the configurations 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.
- AHO, A., SETHI, R., AND ULLMAN, J. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, Mass. Google Scholar
Digital Library
- EARLEY, J. 1970. An efficient context-free parsing algorithm. Commun. ACM 13, 2 (Feb.), 94-102. Google ScholarDigital Library
- GOSLING, J., JOY, B., AND STEELE, G. 1996. The Java Language Specification. Addison-Wesley, Reading, Mass. Google ScholarDigital Library
- MCKENZIE, B., YEATMAN, C., AND DE VERE, L. 1995. Error repair in shift-reduce parsers. ACM Trans. Program. Lang. Syst. 17, 4 (July), 672-689. Google ScholarDigital Library
Index Terms
- On failure of the pruning technique in “Error repair in shift-reduce parsers”
Recommendations
Error repair in shift-reduce parsers
Local error repair of strings during CFG parsing requires the insertion and deletion of symbols in the region of a syntax error to produce a string that is error free. Rather than precalculating tables at parser generation time to assist in finding such ...
Repairing syntax errors in LR-based parsers
When a compiler encounters a syntax error, it usually attempts to restart parsing to check the remainder of the input for any further errors. One common method of recovering from syntax errors is to repair the incorrect input string, allowing parsing to ...
Error-repair parsing schemata
Robustness, the ability to analyze any input regardless of its grammaticality, is a desirable property for any system dealing with unrestricted natural language text. Error-repair parsing approaches achieve robustness by considering ungrammatical ...
Reviews
Frank George Pagan
This short and narrowly focused paper is essentially a piece of technical correspondence concerning an earlier paper [1] by McKenzie et al. in the same journal. The McKenzie paper presented a general method by which automatically generated LR parsers, by inserting and deleting tokens, can repair syntax errors in source programs, and a “pruning” heuristic by which the size of a search space associated with the repair method can be reduced, thereby improving the method's efficiency. In the paper under review, Bertsch and Nederhof show that the pruning heuristic is theoretically defective, in that it can lead to unnecessarily costly repairs and can even fail to find any repairs when feasible repairs exist. They do this by considering several very small grammars (between two and five rules each) and erroneous source strings, and exhibiting the details of the corresponding parsers and search spaces. In the conclusion, they briefly discuss some possibilities for improving the heuristic. Significantly, however, they also state that, for realistic grammars, complete failure of the original heuristic should be very rare and that less-than-optimal repairs are “by no means frequent.” They end by recommending the McKenzie technique “with only minor reservations.” The paper assumes that readers have a good knowledge of LR parsing. Given that, it comes close to being understandable independently of the McKenzie paper, although most interested readers will already have digested the latter. Only four references are cited; more can be found in the McKenzie paper. This paper is recommended to specialists in the technology of compiler generation.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments