Summary
Methods for the automatic construction of error handling parsers are presented. The resulting parsers are capable of correcting all syntax errors by insertion and/or deletion of terminal symbols to the right of the error location. Thus, the output of the parser always corresponds to a syntactically valid program. This contributes significantly to the reliability and robustness of a compiler. The speed of parsing correct parts of a program is not affected by the presence of the error handling capability. The correction algorithm is easy to implement. Apart from the parsing tables only one character per parser state is required to control the correction process. The method is applicable to a wide class of stack automata including LL(k), LR(k), SLR(k), and LALR(k) parsers. It is shown that for LL(k) grammars error correction can be obtained as a byproduct of the canonical LL(k) parser generation. A similar result can be obtained for LR(k) grammars if the parser generator is slightly modified. The method has been successfully added to an LALR(1) parser generator.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho A.V., Ullman, J.D.: The Theory of Parsing, Translation, and Compiling. Volume I. Englewood Cliffs, N.J.: Prentice Hall 1972
Amman, U.: Die Entwicklung eines PASCAL-Compilers nach der Methode des strukturierten Programmierens. Dissertation 54/56. ETH Zürich 1975
Büchi, J.R.: Regular canonical systems. Archiv für Mathematische Logik und Grundlagenforschung 6, 91–111 (1964)
Dencker, P.: Ein neues LALR System. Diplomarbeit. Institut für Informatik II, Universität Karlsruhe 1977
DeRemer, F.L.: Simple LR(k) grammars. CACM 14, 453–460 (1971)
Graham, S.L., Rhodes, S.P.: Practical syntactic error recovery. CACM 18, 639–650 (1975)
Gries, D.: Compiler Construction for Digital Computers. New York, London: Wiley 1971
Horning, J.J.: What the Compiler Should Tell the User. In: Compiler Construction. An Advanced Course (G. Goos, J. Hartmanis, eds.), Lecture Notes in Computer Science 21, pp. 526–548. Berlin, Heidelberg, New York: Springer 1974
Irons, E.T.: An Error-Correcting Parse Algorithm. CACM 6, 669–680 (1963)
James, L.R.: A Syntax-Directed Error Recovery Method. CSRG 13. University of Toronto 1972
Leinius, R.P.: Error Detection and Recovery for Syntax Directed Compiler Systems. PhD Thesis. University of Wisconsin 1970
Levy, J.P.: Automatic Correction of Syntax Errors in Programming Languages. PhD Thesis, TR71-116. Cornell University 1971
Peterson, T.G.: Syntax Error Detection, Correction and Recovery in Parsers. PhD Thesis. Stevens Institute of Technology, Hoboken (N.J.) 1972
Röhrich, J.: Automatic Construction of Error Correcting Parsers. Dissertation, Interner Bericht Nr. 8. Fakultät für Informatik, Universität Karlsruhe 1978
Salomaa, A.: Formal Languages. London: Academic Press 1973
Wynn, P.: Error recovery in SLR parsers. PhD Thesis. University of Newcastle upon Typne 1973
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Röhrich, J. Methods for the automatic construction of error correcting parsers. Acta Informatica 13, 115–139 (1980). https://doi.org/10.1007/BF00263989
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF00263989