[home] [info] [docu] [examples] [download] [contact] [applications] [bugs]

`Parsing a simple Class Diagram`

Let us consider a simple class diagram "ClassHost" as an example for parsing based on critical pair analysis, as shown in Figure 1.
The "C"-nodes represent classes and "A"-nodes stand for associations.

Figure 1. A simple class diagram

Graph "ClassHost" is stored in grammar "classHost.ggx" . The class diagram is drawn free-handed and we will test if this diagram is correct or not, respectively, if this diagram belongs to graph language for class diagrams or not.

At first, we create a parsing grammar "Class" in AGG.
The grammar contains only three parsing rules (Fig.2 - Fig.4) and a graph (Fig.5), the so-called "stop graph".

Figure 2. Parsing rule: DelClass

Figure 3. Parsing rule: DelAss

Figure 4. Parsing rule: DelAss1

Figure 5. The "stop graph" of the parsing grammar

The "stop graph" is a goal for the parsing process.
If our class diagram "Class Host" is correct, these rules reduce it to the "stop graph" in Figure 5. If it is not correct, the parsing process will generate a graph non-isomorphic to the "stop graph",to which no more rule can be applied.
The grammar "Class" is stored in file "class.ggx".

After critical pair analysis by AGG ( menu item Parser / Critical Pair / Generate ) we have got all critical pairs of the parsing rules which we can consider in the graphical user interface for critical pairs.
Figure 6 presents the output for the rule pair [DelClass, DelAss]. We can see the left-hand sides of both rules and all critical overlapping graphs of their left-hand sides. For one graph also the match is shown (by numbers).

Figure 6. Sample critical pairs

The generated critical pairs are stored in file "class.cpx".

Now we want to start the parsing process of our class diagram ( menu item Parser / Open ).
The user dialog in Figure 7 is used to initialize the parser.

Figure 7. User dialog of parser

Choice item "Select Host Graph" waits for selecting or loading a grammar which contains a class diagram. In our example it is the grammar "ClassHost" or the file "classHost.ggx".
Choice item "Select Stop Graph" waits for selecting or loading a parsing grammar which contains the parsing rules and a stop graph. In our example it is grammar "Class" or the file "class.ggx".
Choice item "Select Critical Pairs" has a special meaning. The critical pairs represent a unit with their parsing rules. Therefor the parsing grammar "Class" has to be selected to generate critical pairs. If critical pairs are already generated and stored, they can be loaded. In our example we choose file "class.cpx".
The Next-button moves the selector to the next item. If the initialization is completed, the Finish-button appears.
The Finish-button closes the user dialog and opens the parser GUI.
The Cancel-button cancels the user dialog.

Figure 8 shows the parser GUI.

Figure 8. Parser GUI

Using menu item Parser / Start we can start parsing of our class diagram.
During the parsing process the class diagram is reduced. An intermediate result is shown in Figure 9.

Figure 9. Reduced class diagram in the parser GUI

The final result in Figure 10 shows a graph that is isomorphic to the "stop graph".
The parser result is true, i.e. our class diagram is correct.

Figure 10. Result of parsing

Graph parsing in the context of visual language parsing is described in:

Application of Graph Transformation to Visual Languages by R. Bardohl, M. Minas, A. Schürr and G. Taentzer
Efficient Parsing of Visual Languages based on Critical Pair Analysis and contextual Layered Graph Transformation by P. Bottoni, A. Schürr and G. Taentzer

More about the facilities of the parser and the critical pair analysis in AGG can be read in the diploma thesis of Thorsten Schultzke (in German):
"Entwicklung und Implementierung eines Parsers für visuelle Sprachen basierend auf kritischer Paaranalyse" Revision: September 6, 2001