Dain, Julia Anne (1989) Automatic error recovery for LR parsers in theory and practice. PhD thesis, University of Warwick.

Preview

PDF WRAP_THESIS_Dain_1989.pdf - Requires a PDF viewer. Download (9Mb)

Request Changes to record.

Abstract

This thesis argues the need for good syntax error handling schemes in language
translation systems such as compilers, and for the automatic incorporation of such schemes
into parser-generators. Syntax errors are studied in a theoretical framework and practical
methods for handling syntax errors are presented.
The theoretical framework consists of a model for syntax errors based on the concept of
a minimum prefix-defined error correction,a sentence obtainable from an erroneous string by
performing edit operations at prefix-defined (parser defined) errors. It is shown that for an
arbitrary context-free language, it is undecidable whether a better than arbitrary choice of edit
operations can be made at a prefix-defined error. For common programming languages,it is
shown that minimum-distance errors and prefix-defined errors do not necessarily coincide,
and that there exists an infinite number of programs that differ in a single symbol only; sets
of equivalent insertions are exhibited.
Two methods for syntax error recovery are, presented. The methods are language
independent and suitable for automatic generation. The first method consists of two stages,
local repair followed if necessary by phrase-level repair. The second method consists of a
single stage in which a locally minimum-distance repair is computed. Both methods are
developed for use in the practical LR parser-generator yacc, requiring no additional
specifications from the user. A scheme for the automatic generation of diagnostic messages
in terms of the source input is presented. Performance of the methods in practice is evaluated
using a formal method based on minimum-distance and prefix-defined error correction. The
methods compare favourably with existing methods for error recovery.

Item Type:	Thesis (PhD)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Library of Congress Subject Headings (LCSH):	Programming languages (Electronic computers) -- Syntax, Debugging in computer science -- Computer programs, Compilers (Computer programs), Parsing (Computer grammar)
Official Date:	September 1989
Dates:	Date Event September 1989 Submitted
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Thesis Type:	PhD
Publication Status:	Unpublished
Supervisor(s)/Advisor:	Beynon, Meurig
Extent:	176 leaves
Language:	eng

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads