Abstract

This research is concerned with the automatic generation of syntax-directed editors for graphical programming languages. A specification technique that is used to uniformly define graphical languages along with their syntax-directed editors is developed. The novel aspect of this specification technique, called a general graph transformation system, is that the graphical languages are described by specifying a family of editing operations. In this manner, a language is defined as a dynamic object which, by applying different editing operations, changes from one form to another, each form representing a sentence of the language. In order to demonstrate this process, the language of Petri nets is specified by a general graph transformation system.

Unfortunately, general graph transformation systems allow ambiguous language specification. Moreover, the problem of deciding whether or not an editing operation is applicable to a graphical program is shown to be NP-Complete. Consequently, general graph transformation systems are restricted to obtain a subclass called the deterministic graph transformation systems. The deterministic graph transformation systems enjoy two major properties: first, they define only deterministic languages and second, a polynomial time algorithm is presented that, given a program and an editing operation, decides if the editing operation is applicable to the program. The language of D-charts and an appropriate syntax-directed editor is then specified by a deterministic graph transformation system.

While many of the properties of deterministic graph transformation systems can be efficiently determined, their inherent power comes with some liabilities. Specifically, the problem of deciding whether or not an editing operation specified by a deterministic graph transformation system terminates is shown to be unsolvable.

Finally, the overall object-oriented architecture of a graphical syntax-directed editing system is presented. Moreover, it is shown how such editing systems for different languages may be generated automatically and efficiently from specifications in the forms of deterministic graph transformation systems.

Graduation Date

1988

Semester

Summer

Advisor

Workman, David A.

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Language

English

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0022049

Subjects

Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences

Share

COinS