Formal specification of operations on a class of syntactically-specified data structures.

Abstract

To illustrate the theory, a transform statement syntax is developed, and an interpreter is used to demonstrate operations on several types of structures. The work documented herein is a potential basis for an advanced data structure manipulation language or program generator. A method of formally specifying operations on a class of linked data structures is developed. Data structures are syntactically specified using K-formula grammars. The class of linked data structures whose K-formulas are recognizable by pushdown automata is shown to include those structures with an Eulerian traversal. A method for specifying all allowable operations on a given structure is given, using the structure grammar as a basis.