Graph Types and Graph Rewriting

. GRAPH TYPES AND GRAPH REWRITING  

A typical compiler uses many types of graphs to represent internal program information. For instance, control flow graphs, data dependence graphs, call graphs, def/use chains are some of the most common examples. In order to automate the process of implementing and manipulating these graph structures, Prop provides a generic formalism- graph types- for specifying multisorted, attributed, hierarchical directed graphs in very high level manner. The data structure mapping process of translating high level graph specifications into concrete C++ classes is completely automated. Thus the user can concentrate on specifying the semantic relationships between the elements of the domain, instead of the implementation details.

The graph structure mapping process uses real-time set machine simulation[Pai89] and subtype analysis[CFH91] to convert associative accesses involving sets, maps, and multimaps into hash free, worst-case constant time pointer manipulations. This optimization is performed transparently by the translator.

Manipulation of graphs structures are done in three ways:

object-oriented

Using a standard interface generated from Prop the user can manipulate a graph in the usual procedural/object-oriented manner.

set formalism

Using an embedded SETL[SDDS86]-like sublanguage, the user can manipulate the graphs using high level set operations such as set comprehension.

graph rewriting

At the highest level, analysis and transformation can be carried out using the graph rewriting formalism.

In this section we'll describe each of these topics in detail.

 
• Graph Types
• The Graph Interface
• Set Formalisms
• Graph Rewriting