An efficient insertion-only error-corrector for LL(1) parsers

ABSTRACT

An LL(1)-based error-corrector which operates by "insertion-only" is studied. The corrector is able to correct and parse any input string. It is efficient (linear in space and time requirements) and chooses least-cost insertions (as defined by the user) in correcting syntax errors. Moreover, the error-corrector can be generated automatically from the grammar and a table of terminal symbol insertion costs. The class of LL(1) grammars correctable by this method contains (with minor modifications) grammars used to specify most common programming languages. Preliminary results suggest that this method can be used to advantage in LL(1)-driven compilers.

REFERENCES

• 1: Aho, A. V. and Peterson, T. G., A Minimum Distance Error-correcting Parser for Context-free Languages. SIAM Journal of Computing 1, 4, 305-312, 1972.
• 2: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 3: Richard W. Conway , Thomas R. Wilcox, Design and implementation of a diagnostic compiler for PL/I, Communications of the ACM, v.16 n.3, p.169-179, March 1973 [doi>10.1145/361972.361992]
• 4: DeRemer, F. L., Practical Translators for LR(k) Languages. Ph.D. Thesis, M.I.T., 1969.
• 5: Ghezzi, C., LL(1) Grammars Supporting an Efficient Error Handling. Information Processing Letters 3, 6, 174-176, 1975.
• 6: Susan L. Graham , Steven P. Rhodes, Practical syntactic error recovery, Communications of the ACM, v.18 n.11, p.639-650, Nov. 1975 [doi>10.1145/361219.361223]
• 7: David Gries, Use of transition matrices in compiling, Communications of the ACM, v.11 n.1, p.26-34, Jan. 1968 [doi>10.1145/362851.362872]
• 8: David Gries, Compiler Construction for Digital Computers, John Wiley & Sons, Inc., New York, NY, 1971
• 9: E. T. Irons, An error-correcting parse algorithm, Communications of the ACM, v.6 n.11, p.669-673, Nov. 1963 [doi>10.1145/368310.368385]
• 10: James, L. R., A Syntax Directed Error Recovery Method. M.S. Thesis, Univ. of Toronto, Computer Systems Research Group Tech. Rep. CSRG-13, May 1972.
• 11: Jacques Emmett Lafrance, Syntax-directed error recovery for compilers, 1971
• 12: Ronald Paul Leinius, Error detection and recovery for syntax directed compiler systems, 1970
• 13: Jean-Pierre Levy, Automatic correction of syntax errors in programming languages, 1971
• 14: Philip M. Lewis, 2nd , Daniel J. Rosenkrantz , Richard E. Stearns, Compiler Design Theory, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1976
• 15: Gordon Lyon, Syntax-directed least-errors analysis for context-free languages: a practical approach, Communications of the ACM, v.17 n.1, p.3-14, Jan. 1974 [doi>10.1145/360767.360771]
• 16: Thomas G. Peterson, Syntax error detection, correction and recovery in parsers, 1972
• 17: Rhodes, S. P., Practical Syntactic Error Recovery for Programming Languages. Ph.D. Thesis, Univ. of California, Berke Dept. of Comp. Sci. Tech. Rep. 15, 1973.
• 18: Ray Teitelbaum, Context-free error analysis by evaluation of algebraic power series, Proceedings of the fifth annual ACM symposium on Theory of computing, p.196-199, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804050]