Declarative Term Graph Attribution for Program Generation

Wolfram Kahl, Frank Derichsweiler

Journal of Universal Computer Science 7 (2001), No. 1, pp. 54-70



We show how the declarative spirit of attribute grammars can be employed to define an attribution mechanism for term graphs, where the non-uniqueness of inherited attributes demands an appropriately generalised treatment.

Since term graphs are a useful data structure for symbolic computation systems such as theorem provers or program transformation systems, this mechanism provides a powerful means to generate concrete programs (and other relevant text or data structures) from their abstract term graph representations.

We have implemented this declarative term graph attribution mechanism in the graphically interactive term graph program transformation system HOPS and show a few simple examples of its use.

Keywords: Program generation, term graph attribution, declarative attribute grammars, graph traversals

Wolfram Kahl