49
Mark Minas Universität der Bundeswehr München [email protected] Tripel-Graphgrammatik-basierte Diagrammanalyse

Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

  • Upload
    others

  • View
    7

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Mark Minas

Universität der Bundeswehr München

[email protected]

Tripel-Graphgrammatik-basierte Diagrammanalyse

Page 2: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Überblick •  Editiermodi bei Diagrammeditoren •  Editorgenerator DiaGen •  Diagrammanalyse bei DiaGen-Editoren •  Tripel-Graph-Grammatiken zur Diagrammanalyse

  Tripel-Graph-Grammatiken allgemein   Bidirektionale Diagrammanalyse mit Tripel-Graph-Grammatiken   Spezielle TGG-Probleme bei der Diagrammanalyse

 Negative Anwendbarkeitsbedingungen  Unifikation von Knoten

•  Zusammenfassung

2

Page 3: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 3

Diagrammeditoren •  Strukturiertes Editieren

+ Relativ einfach zu realisieren + Stellt dem Nutzer eine Menge von Operationen zur Verfügung -  Schränkt den Benutzer ein

•  Freihändiges Editieren

− Erfordert aufwändige Diagrammanalyse +  Lässt dem Nutzer größtmögliche Freiheit − Gibt dem Nutzer keine „Anleitung“

Semantik Diagramm

Abstrakte Repräsentation

Diagramm

Semantik

Page 4: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 4

Diagrammeditoren •  Kombination von strukturiertem und freihändigem Editieren

+ Stellt dem Nutzer eine Menge von Operationen zur Verfügung +  Lässt dem Nutzer größtmögliche Freiheit -  Erfordert aufwändige Diagrammanalyse

Abstrakte Repräsentation

Diagramm

Semantik Semantik Diagramm +

Abstrakte Repräsentation Diagramm Semantik

Page 5: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Überblick •  Editiermodi bei Diagrammeditoren •  Editorgenerator DiaGen •  Diagrammanalyse bei DiaGen-Editoren •  Tripel-Graph-Grammatiken zur Diagrammanalyse

  Tripel-Graph-Grammatiken allgemein   Bidirektionale Diagrammanalyse mit Tripel-Graph-Grammatiken   Spezielle TGG-Probleme bei der Diagrammanalyse

 Negative Anwendbarkeitsbedingungen  Unifikation von Knoten

•  Zusammenfassung

5

Page 6: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 6

DiaGen •  Rapid Prototyping-Werkzeug zur Erstellung von Diagrammeditoren

aus einer Spezifikation •  Freihändiges Editieren:

  Zeichenprogramm   Lexikalische, syntaktische und semantische Analyse

•  Strukturiertes Editieren (optional) •  Automatisches Layout (optional)

auch bei freihändigem Editieren •  Unterstützung hierarchischer Diagramme (optional) •  Unparsing von Diagrammen, d.h. Semantik → Diagramm (optional) •  Unterstützung großer Diagramme:

Semantisches Zoomen (optional) •  Java

Page 7: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 7

Generating diagram editors with DiaGen

Editor developer

Diagram editor

DiaGen editor

framework

DiaGen Designer DiaGen

Generated program

code

Specifi- cation

operates

Page 8: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 8

Example: Message Sequence Charts (MSC)

Page 9: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 9

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

Editor user

selects operation

selects operation

Hypergraph transformer

reads

reads

modifies reads

Layout information Layouter

Semant. represen-

tation

Attribute evaluation

Highlights syntactically correct sub-diagrams

Abstract Representation Diagram Semantics

Page 10: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 10

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

Editor user

selects operation

selects operation

Hypergraph transformer

reads

reads

modifies reads

Layout information Layouter

Semant. represen-

tation

Attribute evaluation

Highlights syntactically correct sub-diagrams

Set of diagram components

Diagram components & Relations

Reducer rules Hypergraph grammar

Attribute hypergraph grammar

Programmed (hyper-) graph- transformations

Constraints

Page 11: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 11

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

Editor user

selects operation

selects operation

Hypergraph transformer

reads

reads

modifies reads

Layout information Layouter

Semant. represen-

tation

Attribute evaluation

Highlights syntactically correct sub-diagrams

Page 12: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Überblick •  Editiermodi bei Diagrammeditoren •  Editorgenerator DiaGen •  Diagrammanalyse bei DiaGen-Editoren •  Tripel-Graph-Grammatiken zur Diagrammanalyse

  Tripel-Graph-Grammatiken allgemein   Bidirektionale Diagrammanalyse mit Tripel-Graph-Grammatiken   Spezielle TGG-Probleme bei der Diagrammanalyse

 Negative Anwendbarkeitsbedingungen  Unifikation von Knoten

•  Zusammenfassung

12

Page 13: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 13

Example: Message Sequence Charts (MSC)

Diagram components:

Action

Lifeline of an entity

Message

Page 14: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 14

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

Editor user

selects operation

selects operation

Hypergraph transformer

reads

reads

modifies reads

Layout information Layouter

Semant. represen-

tation

Attribute evaluation

Highlights syntactically correct sub-diagrams

Page 15: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 15

Hypergraph Model

act

act

act

lifeline lifeline

arrow

arrow

Component hyperedge

Page 16: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 16

Hypergraph Model

act

act

act

lifeline lifeline

arrow

arrow

Component hyperedge

Attachment area of the

diagram component

Nodes represent attachment areas

Page 17: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 17

Hypergraph Model with Relationship Edges

lies on

lies on lies on

act

act

arrow

arrow

act

lifeline lifeline

Relationship edges connect nodes whose attachment areas are

related in a specific way

Page 18: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 18

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

Editor user

selects operation

selects operation

Hypergraph transformer

reads

reads

modifies reads

Layout information Layouter

Highlights syntactically correct sub-diagrams Semant. represen-

tation

Attribute evaluation

Page 19: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 19

Hypergraph Model with Relationship Edges

lies on

lies on lies on

act

act

arrow

arrow

act

lifeline lifeline

Page 20: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 20

Reduced Hypergraph Model

line

message next

action

send

recv

nextLife

next

next

action

next

next

recv

action

send

line

message

Page 21: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 21

“Reducing“ the Hypergraph Model

lies on lies on lies on

act

act

arrow

arrow

act

lifeline lifeline line

message next

action

send

recv

nextLife

next

next

action

next

next

recv

action

send

line

message

Page 22: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 22

“Reducing“ the Hypergraph Model •  Reducer rule

  For each lifeline edge and its visited node, create a line edge together with its visited node in the RHGM

  Actually (for each reducer rule!!):  Don’t create a new node in the RHGM if the HGM node has a

corresponding RHGM node already. Use this RHGM node instead!   Textual representation: lifeline(s) ==> line(s)

lifeline line

s s

Page 23: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 23

“Reducing“ the Hypergraph Model

lies on lies on lies on

act

act

arrow

arrow

act

lifeline lifeline line

message next

action

send

recv

nextLife

next

next

action

next

next

recv

action

send

line

message

Page 24: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 24

“Reducing“ the Hypergraph Model lifeline lifeline

nextLife line1 line2

Condition: line1.x < line2.x

lifeline

line3

with line1.x < line3.x < line2.x

line1 line2

Textual representation:

lifeline(line1) lifeline(line2) -{ lifeline(line3) where line1.x < line3.x && line3.x < line2.x } ==> nextLife(line1,line2)

Page 25: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 25

“Reducing“ the Hypergraph Model

lies on lies on lies on

act

act

arrow

arrow

act

lifeline lifeline line

message next

action

send

recv

nextLife

next

next

action

next

next

recv

action

send

line

message

Page 26: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 26

“Reducing“ the Hypergraph Model

lies on

lifeline

e

l l = e

e2

with e2.y < e.y

Textual representation:

lifeline(l) liesOn(e,l) -{ liesOn(e2,l) where e2.y < e.y } ==> e = l

Page 27: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Semantik von Reduktionsregeln •  Eine Reduktionsregel ist ein Graphmorphismus L → R

mit Anwendbarkeitsbedingungen •  Eine Reduktionsregel beschreibt, wie das reduzierte

Hypergraphmodell im Hypergraphmodell aufgebaut wird •  Reduktion =

  parallele Anwendung aller Reduktions- regeln

  und anschließend Entfernen des ursprünglichen Hypergraphmodells

27

1L

L1

R1

R1

m1

m1

L2

L2

R2

R2

m2

m2

f1,1 f

1,2

f2,1

f2,2

1,1g

1,2g

2,1g

2,2g

H

H’

h

Abbildung 11.1: Anwendung der Reduktionsregeln auf das Hypergraphmodell

Die lexikalische Analyse ist durch eine endliche Menge von

Reduktionsregeln spezifiziert und wird unter

Vorgabe eines Hypergraphmodells in vier Schritten durch-

geführt:

1. Suche alle Muster in , die durch die Reduktionsregeln vorgegeben sind, d. h.

bestimme alle Hypergraphmonomorphismen von „linken Seiten“ der Regeln

nach , die die Anwendbarkeitsbedingungen erfüllen. Das Ergebnis ist eine

Familie von Morphismenmengen, wobei

ist Monomorphismus

Im folgenden sei . Abb. 11.1 zeigt die Hypergraphmor-

phismen zusammen mit den Einbettungen als durchgezogene

Pfeile. Man beachte, daß jeder Knoten und jede Hyperkante von Bestand-

teil mehrerer Muster sein kann, d. h. jede Hyperkante und jeder Knoten kann

mehrfach Bild eingebetteter linker Regelseiten sein.

2. Wende alle Reduktionsregeln gleichzeitig für alle Einbettungen ihrer „linken

Seiten“ auf an. Dazu muß der allgemeinste Hypergraph gesucht wer-

Page 28: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 28

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

Editor user

selects operation

selects operation

Hypergraph transformer

reads

reads

modifies reads

Layout information Layouter

Semant. represen-

tation

Attribute evaluation

Highlights syntactically correct sub-diagrams

Page 29: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München 29

Hypergraph Grammar

send recv

message

send recv ::=

a b b a

Lifelines Lifeline

nextLife

Lifeline Lifelines ::=

a a a

Lifeline line line

EventSeq

::= a a

a Event action send recv ::=

a a a a

EventSeq Event

Event

next

EventSeq

::= a a

a

context-free productions

embedding production

Page 30: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

•  Reduktion ist uni-direktional ⇒  Strukturierte Editieroperationen können nur auf dem Hypergraph-

modell ausgeführt werden ⇒  Zur Integration mit anderen Werkzeugen müssen externe

Datenstrukturen in Hypergraphmodelle transformiert werden 30

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

selects operation

selects operation

Hypergraph transformer

reads

reads

modifies reads

Layout information Layouter

Semant. represen-

tation

Attribute evaluation

Highlights syntactically correct sub-diagrams

Page 31: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Überblick •  Editiermodi bei Diagrammeditoren •  Editorgenerator DiaGen •  Diagrammanalyse bei DiaGen-Editoren •  Tripel-Graph-Grammatiken zur Diagrammanalyse

  Tripel-Graph-Grammatiken allgemein   Bidirektionale Diagrammanalyse mit Tripel-Graph-Grammatiken   Spezielle TGG-Probleme bei der Diagrammanalyse

 Negative Anwendbarkeitsbedingungen  Unifikation von Knoten

•  Zusammenfassung

31

Page 32: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Lösung: Tripel-Graph-Grammatiken •  Tripel-Graph-Grammatiken operieren auf Graph-Tripeln:

  L ← C → R   Linker Graph L, Korrespondenzgraph C, rechter Graph R   Morphismen zwischen C, L und R

•  Ein Produktions-Tripel pL, pC, pR besteht aus den drei Produktionen sowie Morphismen zwischen den linken und rechten Seiten:

•  Voraussetzung:   Produktionen sind monoton, also Morphismen   „Quadrate“ kommutieren

32

LL

LR

CL

CR

RL

RR

pL pC pR

Page 33: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Tripel-Graph-Grammatiken •  Produktions-Tripel pL, pC, pR , angewandt auf ein

Graph-Tripel LG ← CG → CR, ergibt ein neues Graph-Tripel LG‘ ← CG‘ → RG‘

33

-8-

Definition 3.2 Monotonic Productions and Graph Rewriting.

Any tuple of graphs p := (L, R) with L ! R is a monotonic production and p applied to a

given graph G produces another graph G’ " G, denoted by: G ~p~> G’, with respect to

redex3 selecting morphisms g: L # G and g’: R # G’, iff:

(1) g’ | L = g , i.e. g and g’ are identical mappings w.r.t. the left-hand side graph L.

(2) g’ maps new vertices and edges of R \ L onto unique new vertices and edges of G’ \ G .

Using the categorical framework [3], conditions (1) and (2) may be replaced by requiring

the existence of the pushout diagram a) of figure 3. !

Based on this fundamental terminology we are now able to define graph triples as well as pro-

duction triples and their application to graph triples:

Definition 3.3 Graph Triples.

Let LG, RG, and CG be three graphs, and lr: CG# LG, rr: CG # RG are those morphis-

ms which represent m-to-n relationships between the left-hand side graph LG and the

right-hand side graph RG via the correspondence graph CG in the following way:

x $ LG is related to y $ RG :% & z $ CG: x = lr(z) ' rr(z) = y .

The resulting graph triple is denoted as follows:

GT := ( LG ( lr ) CG ) rr # RG ) . !

Definition 3.4 Production Triples and Graph Triple Rewriting.

Let lp := (LL, LR), rp := (RL, RR), and cp := (CL, CR) be monotonic productions. Fur-

thermore, lh: CR# LR and rh: CR# RR are graph morphisms such that their restrictions

lh|CL: CL # LL and rh|CL: CL # RL are morphisms, too, which relate the left- and right-

hand sides of productions lp and rp via cp to each other. The resulting production triple is

denoted as follows:

p := ( lp ( lh ) cp ) rh # rp ) .

3) A redex is a subgraph within a host graph matching a given production’s left-hand side.

Fig. 4: Application of Simple Productions and Production Triples.

LL CL RL

LR CR RR

LG CG RG

LG’ CG’ RG’

lh|CL rh|CL

lg cg rg

lg’ cg’ rg’

lr rr

lr’ rr’

!!!

!!!

lh rh

L R

G G’

!

g’

!

g PO

Diagram a) Diagram b)

Remark:

The sign “!” labels any arrow which

represents an inclusion.

[Schürr94]

Page 34: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Tripel-Graph-Grammatiken •  Damit definieren Tripel-Graph-Grammatiken jeweils drei

korrespondierende Ableitungsketten: •  Auf diese Weise definieren Tripel-

Graph-Grammatiken die Menge aller gültigen Graph-Tripel:   Abbildung der „linken“ Graphsprache

in die „rechte“ und umgekehrt   Die Korrespondenzgraphen

beschreiben mit ihren Morphismen die m:n-Beziehungen zwischen linken und rechten Graphen

34

L1 C1 R1 ← → →

L2 C2 R2 ← →

L3 C3 R3 ← →

Ln Cn Rn ← →

...

...

...

Page 35: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

L1 C1 R1 ← → →

L2 C2 R2 ← →

L3 C3 R3 ← →

Ln Cn Rn ← →

...

...

...

Tripel-Graph-Grammatiken •  Tripel-Graph-Grammatiken erlauben eine effektiv durchführbare

Übersetzung eines linken Graphen in einen entsprechenden rechten (u.u.), wenn man die Ableitung des linken Graphen kennt:

•  Ableitung von „Vorwärts-“ und „Rückwärtsregeln“ etc.

35

Ln

L1 C1 R1 ← →

L2 →

L3 →

...

Page 36: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Überblick •  Editiermodi bei Diagrammeditoren •  Editorgenerator DiaGen •  Diagrammanalyse bei DiaGen-Editoren •  Tripel-Graph-Grammatiken zur Diagrammanalyse

  Tripel-Graph-Grammatiken allgemein   Bidirektionale Diagrammanalyse mit Tripel-Graph-Grammatiken   Spezielle TGG-Probleme bei der Diagrammanalyse

 Negative Anwendbarkeitsbedingungen  Unifikation von Knoten

•  Zusammenfassung

36

Page 37: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

TGGen zur Definition des Reduzierers •  Vorteile:

  Transformation des Hypergraphmodells ins reduzierte Hypergraph-modell und umgekehrt möglich (setzt Repräsentation der Hypergraphen durch bipartite Graphen voraus)

  Korrespondenz zwischen HGM und rHGM wird durch den Korrespondenzgraphen repräsentiert

•  Nachteile:   Ableitung des zu transformierenden Graphen muss bestimmt

werden   Es werden negative Anwendbarkeitsbedingungen benötigt

 diese zerstören aber im Allgemeinen die operationale Übersetzbarkeit mit TGGen

  Nicht-injektive Produktionen („Unifikation“ von Knoten) werden benötigt

37

Page 38: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Negative Anwendbarkeitsbedingungen •  Werden z.B. benötigt, um transitive Beziehungen zu reduzieren •  Beispiel MSC:

38

lifeline lifeline

nextLife line1 line2

Condition: line1.x < line2.x

lifeline

line3

with line1.x < line3.x < line2.x

line1 line2

Page 39: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Negative Anwendbarkeitsbedingungen •  Produktionstripel (mit Kanten statt Attributbedingungen)

39

Page 40: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Negative Anwendbarkeitsbedingungen •  Ziel:

•  obwohl dies eine gültige Ableitung des linken Graphen ist:

•  Beobachtungen:   NACs dienen dazu, bestimmte Graphanteile nicht zu übersetzen,

und nicht (ausschließlich) der Determinierung, welche Regeln angewendet werden dürfen

  NACs müssen sich auf den Graphen am Ende der Ableitung, d.h. den zu übersetzenden Graphen beziehen

40

⇐ ⇐ ⇐

Page 41: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten •  Beispiel Flussdiagramme

41

B

S

I

O

F

T

A

O

at

at

f

t

i

o

o

HGM

start

o

stmt

i

o

rHGM

Page 42: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten

42

B

O o

start o

S

I

O

i

o

stmt o

i

I

O 1

2

I

O

F

T

A

at

at

f

t 1=2

Page 43: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Flussdiagramme

39

B

O

o

start

o

!

S

I

O

i

o

stmt

o

i

!

I

O 1

2

I

O

F

T

A

at

at

f

t 1=2

!

Unifikation von Knoten

43

B

S

I

O

F

T

A

O

at

at

f

t

i

o

o start

o

stmt

i

o

S

I

O

i

o

stmt i

o

B

O o

start o

B

O o

start o

Page 44: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten •  „Vorwärtsanwendung“ HGM→rHGM ist

unproblematisch •  „Rückwärtsanwendung“ rHGM→HGM:

  Es muss tatsächlich eine komplette Ableitungsfolge für den rHGM gefunden werden, um dann die Ableitung der Graphtripel zu vervollständigen

  Aber wann muss man einen Knoten aufspalten? Bei der Bestimmung der rHGM-Ableitungsfolge werden vorhandene Abhängig- keiten vom HGM und dem Korrespondenzgraphen nicht berücksichtigt:

44

I

O 1

2

I

O

F

T

A

at

at

f

t 1=2

stmt o

i

start o

Page 45: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten •  Lösung durch Kombination von Produktionstripeln:

45

B o

start

o

I

O

F

T

A

at

at

f

t

I

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Flussdiagramme

39

B

O

o

start

o

!

S

I

O

i

o

stmt

o

i

!

I

O 1

2

I

O

F

T

A

at

at

f

t 1=2

!

Page 46: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten

S

I

O

i

o

stmt o

i

start o

stmt o

i

start o

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Flussdiagramme

39

B

O

o

start

o

!

S

I

O

i

o

stmt

o

i

!

I

O 1

2

I

O

F

T

A

at

at

f

t 1=2

!

Page 47: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten

S

I

O

i

o

stmt o

i

start o

stmt o

i

start o

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten

•! Lösung durch Kombination von Produktionstripeln:

42

B o

start

o

I

O

F

T

A

at

at

f

t

I

!

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Flussdiagramme

39

B

O

o

start

o

!

S

I

O

i

o

stmt

o

i

!

I

O 1

2

I

O

F

T

A

at

at

f

t 1=2

!

Page 48: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Unifikation von Knoten

S

I

O

i

o

stmt o

i

B o

start

o

I

O

F

T

A

at

at

f

t

S

O

i

o

stmt o

i

start o

stmt o

i

start o

Page 49: Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message Sequence Charts (MSC) Diagram components: Action Lifeline of an entity Message

Tripel-Graphgrammatik-basierte Diagrammanalyse Mark Minas, Universität der Bundeswehr München

Zusammenfassung •  TGGen unterstützen die bidirektionale Diagrammanalyse

  Diagramm abstrakte Syntax Semantik ohnehin   Nun auch abstrakte Syntax Diagramm   Dadurch erleichtert:

 Strukturierte Editieroperationen   Integration mit anderen Werkzeugen  Diagrammvervollständigung

  Aber: Es wird ein automatischer Layouter benötigt, da die umgekehrte Diagrammanalyse lediglich ein (Hyper-) Graphmodell erstellt

•  Man kann TGGen für die grammatikbasierte (DiaGen) und die metamodellbasierte (DiaMeta) Diagrammanalyse einsetzen

•  Prototypische Implementierung in einer Diplomarbeit:   Nur Vorwärtsübersetzung (Diagramm abstrakte Syntax)   Keine Knotenunifikation

49