A case grammar approach to error correction in computer programs
Judy Mallino Popelas · 1983
This dissertation describes a programming language grammar and a corresponding analysis method based on the use of attribute and significant keyword information. The grammar is referred to as a case grammar, and the analysis method as case analysis. Their use results in a significant ability to correct syntactic errors in computer programs. A case grammar defines a programming language in terms of its objects, and its objects in terms of their attributes. It consists of two parts. The first part, the access form dictionary, defines ways of accessing objects in the language in terms of other objects in the language. For example, a Pascal set literal can be accessed by specifying the zero or more set elements that compose it. The second part of a case grammar, the verb dictionary, specifies the objects required by each verb of the language, and the functional or case relationship of each object to its verb. The Pascal assignment verb, for example, requires two objects, the first a recipient and the second a donor. The donor case relationship is explicitly indicated by the terminal symbol ':=' that precedes the donor object. Entries in the verb and access form dictionaries are referred to as case and form frames, respectively. Case grammars are capable of a complete syntactic definition of any context-free programming language. The case analysis algorithm retrieves appropriate case or form frames, puts them on a stack, and matches the next object in the program text to an object requirement in the topmost frame. Frames are often established absolutely, on the basis of significant programming language tokens (keywords) in the program text. In matching an object to a particular object requirement in a frame, the analysis algorithm considers the object's attributes, as well as its position, punctuation context, and preceding keyword, if any. The case analysis algorithm is shown to work correctly for correct program text. The error correction performance of the case analysis algorithm compares favorably with the performance of other recently proposed error correction schemes.