An Abstract Machine for the Execution of
Graph Grammars
Heiko Dörr
Institut für Informatik
Freie Universität Berlin
email: doerr@inf.fu-berlin.de
Report B-94-07
7/13/94
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.
Get the report by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-07.ps.gz