The Graph Parser in 

 

 

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.  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.    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. 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 : 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.   Moreover, it is possible to choose layered parsing by the checkbox  Layered. 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 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 (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: