Graph Parser
The AGG graph parser is able to check if a given graph belongs to a certain graph language determined by a graph grammar. In formal language theory, this problem is known as the membership problem. Here, the membership problem is lifted to graphs. This problem is undecidable for graph grammars in general, but for restricted classes of graph grammars it is more or less efficiently solvable.Usually, a graph grammar is given to generate all graphs of a graph language. For parsing, all rules of the graph grammar have to be inverted. Applying the inverted rules in a right way, all graphs of the corresponding graph language can be reduced to the start graph of the grammar.
In AGG not all kinds of rules can be automatically inverted. That's why the graph parser expects already a so-called parse grammar containing reducing parsing rules and a stop graph. Given an arbitrary host graph, AGG tries to apply the parsing rules in a way that the host graph is reduced to the stop graph. If this is possible, the host graph belongs to the determined graph language and there is a derivation sequence from the host graph to the stop graph, otherwise not.
Three different parsing algorithms are offered by AGG all based on back tracking, i.e. the parser is building up a derivation tree of possible reduction of the host graph with dead ends, i.e. leave graphs where no rule can be applied anymore but the leave graph is not isomorphic to the stop graph. Since simple back tracking has exponential time complexity, the simple back tracking parser is accompanied by two further parser variants exploiting critical pair analysis for rules.
Critical pair analysis can be used to make parsing by graphs more efficient: decisions between conflicting rule applications are delayed as far as possible. This means to apply non conflicting rules first and to reduce the graph as much as possible. Afterwards, the conflicting rules are applied, first in uncritical situations and when this is not possible, in critical ones. In general, this optimization reduces the derivation tree constructed, but does not change the worst case complexity.
More concretely, the overall rule set is structured into conflict free and conflicting rules. For optimized parsing the rules are applied in the following order:
- If there is a match of a conflict free rule in the host graph, it is applied.
- Otherwise, if there is a match of a conflicting rule in a non conflicting situation, i.e. the match is non conflicting, this rule is applied at this match.
- Otherwise only a conflicting rule can be applied at a conflicting match. In this case, the algorithm might have to backtrack later on, thus, all important data has to be stored such that this situation can be recovered. Afterwards the rule is applied at the given match.
The parsing process might not terminate, therefore so-called layering conditions are introduced.
In the follow we shortly explain when two rule applications are in conflict and how all critical situations can be found. Critical Pair Analysis Critical pair analysis can be advantageously used to make parsing by graph transformation more efficient in the sense that decisions between conflicting rule applications are delayed as far as possible. This means to apply non conflicting rules first and reduce the graph as much as possible before starting with rule applications which are in conflict with others. At each conflict, a decision point is created which can cause backtracking in the parsing algorithm. There are three reasons why rule applications can be conflicting: The first two are related to the graph structure while the last one concerns the graph attributes.
Two rules are in conflict if at least one of the conditions above is fulfilled. To find all conflicting rule applications minimal critical graphs are computed to which rules can be applied in a conflicting way. Basically we consider all overlapping graphs of the left-hand sides of two rules with the obvious matches and analyze these rule applications. All conflicting rule applications we found are called critical pairs.
- One rule application deletes a graph object which is in the match of another rule.
- One rule generates graph objects in a way that a graph structure would occur which is prohibited by a negative application condition (NAC) of another rule application.
- One rule changes attributes being in the match of another rule.
Parsing of non-layered or layered graph grammar can optionally be based on critical pair analysis.
Graphical user interface
The graph parser has a graphical user interface, where the way the parser works can be considered. Figures 6 and 8 in section "Sample Parsing in AGG" below show the GUI for the parser. In the following, we consider the options and menu items of the parser. There are a number of options to set the strategies for the parsersing process. Parser Options:
Figure 1 shows the possible settings:
Figure 1. Parser Options
The Parser Display Option are used to configure the visualization of the parsing process. Choosing Invisible the host graph and the stop graph are not shown. Choosing host graph, the user can also select the stop graph to be displayed.
Furthermore, parsing may be layered. In this case, first all rules of one layer are applied as long as possible before the rules of the next layer are applied.
A further setting concerns the parsing algorithm to be used. (Figure 2) Dependent on the use of critical pairs for parsing, the user may choose:
- Backtracking without optimization : no usage of critical pairs
- Semi-optimized backtracking : Applies non-conflicting rules first.
- Critical Pair Analysis: As semi-optimized backtracking, but uses critical pair analysis to check if potentially conflicting rules really exclude rule applications in the actual host graph.
Figure 2. Selection of Parsing Algorithms
Critical Pair Analysis :Moreover, it is possible to choose layered parsing by the checkbox Layered.After the crticial pair analysis, there are two rule sets: conflict-free rules and conflicting rules. A critical pair shows the essential part of critical matches. The algorithms runs as follows:
1. A conflict-free rule is applied.
2. There is no match of a conflict-free rule. Choose a non-critical match of a conflicting rule and apply the rule.
3. There are only critical matches of conflicting rules. Apply a rule and store the application on the stack, since it might cause backtracking.Semi optimized backtracking :
After the crticial pair analysis, there are two rule sets: conflict-free rules and conflicting rules. A critical pair shows the essential part of critical matches. The algorithms goes as follows:
1. A conflict-free rule is applied.
2. There is no match of a conflict-free rule. Choose the first match of a conflicting rule and apply it. Store the application on the stack, since it might cause backtracking.Backtracking without optimization :
The critical pair analysis is completely ignored here. The rules are applied in any order which might cause backtracking.
Parsing starts at the lowest layer. Rules are chosen layerwise and according to the actual parsing algorithm described above. Parsing stays in one layer as long as a rule is applicable, thereafter rules of the next layer are chosen. Since layered parsing with non-layered critical pairs is meaningless, both checkboxes are coupled (Figure 2).
Menu Parser
- Open
Opens a user dialog to initialize the parser and set parser GUI.- Start
Starts the parsing process.- Stop
Stops the parsing process.- back
Returns to main GUI.
Sample Parsing in AGG
Let us consider a simple class diagram "ClassHost" as an example for parsing based on critical pair analysis, Its abstract syntax 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.
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 the 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.
Grammar "Class" is stored in file "class.ggx".After critical pair analysis by AGG ( menu item Analyzer / Critical Pair Analysis / 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
Figure 8 shows the parser GUI.
- 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. 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 (full paper) 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: