Introduction to Graph Grammar


This tutorial is about creating, editing and applying Graph Grammars in AToM3. A Graph Grammar consists of several rules/productions that specify a formalism for a given language. Graph Grammars are specified in AToM3 as model transformations. Indeed, each of their rules is defined by a left-hand-side (LHS) that is rewrited into a right-hand-side (RHS). Model transformation such as code generation, simulators and graph reduction can be created in AToM3. For example, we will explain in detail in this tutorial a simulator for finite state automata that was meta-modeled in AToM3:

As you can see on figure 1, when the event "A" is triggered, the FSA envolves to a new state on figure 2. This is modeled in a Graph Grammar by a rule having figure 1 on the LHS and figure 2 on the RHS.

Figure 1

Figure 2


But how exaclty the graph grammar tool perform those transformations? Two key words: pattern matching. As a user, you define one or more rules that specify patterns to be rewrited. Then, AToM3's graph grammar tool locates those patterns in an instance of a host graph and transforms them.

To achieve the learning of Graph Grammar, I consider that the reader is completely new to AToM3. We will first Load and Setup AToM3, then we will see how the FSA formalism works by creating a simple model with it. After that, we will go step by step in the execution of the Graph Grammar and, finally, we will analyse how the graph grammar was built.