Global context recovery

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Global context recovery: A new strategy for parser recovery from syntax errors

Full text

Pdf (592 KB)

Source

Symposium on Compiler Construction archive
Proceedings of the 1979 SIGPLAN symposium on Compiler construction table of contents

Denver, Colorado, United States

Pages: 158 - 167

Year of Publication: 1979

ISBN:0-89791-002-8

Also published in ...

Authors

Ajit B. Pai	Programs in Mathematical Sciences, The University of Texas at Dallas
Richard B. Kieburtz	Department of Computer Science, State University of New York at Stony Brook

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 10, Citation Count: 2

Additional Information:

abstract references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/800229.806966 What is a DOI?

ABSTRACT

Methods for error recovery in parsing a deterministic, context-free language need not be derived by ad hoc means. When fixed, table-driven parsing algorithms are used the error recovery procedures can also make use of knowledge about the grammar for the language, derived from the parsing tables. However, at the point of detection of certain kinds of syntax errors, the knowledge of a sentential prefix already parsed, as reflected in the current state of the parsing stack, will be incorrect. Effective error recovery under such circumstances has proven to be difficult. We suggest the use of fiducial, or trustworthy symbols of a language as a key to recovery in these difficult cases. In this paper we give a characterization of such symbols in terms of properties of a grammar and give an algorithm that is capable of global context recovery under all circumstances. It has been implemented in conjunction with an LL(1) parser. We have compared it experimentally with the LR-parser recovery algorithm of Pennello and DeRemer on a test set of 126 small Pascal programs.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	Thomas J. Pennello , Frank DeRemer, A forward move algorithm for LR error recovery, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.241-254, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512786]
	3	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	4	Ripley, D.C. and Druseikis, F.C., A statistical analysis of syntax errors, Technical Report, Department of Computer Science, University of Arizona, Tucson, (1978).
	5	Ajit Babani Pai, Syntax driven error recovery in top-down parsing., 1978

CITED BY 2

	Susan L. Graham , Charles B. Haley , William N. Joy, Practical LR error recovery, ACM SIGPLAN Notices, v.14 n.8, p.168-175, August 1979
	Peter N. van den Bosch, A bibliography on syntax error handling in context free languages, ACM SIGPLAN Notices, v.27 n.4, p.77-86, April 1992