An abstract machine for the execution of graph grammars

Abstract

An abstract machine for graph rewriting is the central part of the middle layer of the implementation of a grammar based graph rewriting system. It specifies the interface between a compiler for graph grammars and a system performing actual graph transformations. By the introduction of a middle layer, the analysis of the given graph grammar can be used to optimize its execution. The costs of expensive analysis are thus shifted from run to compile time. Each implementation of the abstract machine can optimize the utilization of available hardware. We give the specification of the state and the instruction set of the abstract machine. For an example grammar we show how compile time analysis can reduce execution time, and we present code generation rules to implement a grammar on the abstract machine. In comparison to abstract machines, well-known from the implementation of functional languages, our machine can execute rewriting specified by graph grammars which is far more general than graph reduction. The abstract machine for graph rewriting is part of a project which addresses the efficient implementation of the execution of graph grammars.