Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message...

Mark Minas

Universität der Bundeswehr München

Mark.Minas@unibw.de

Tripel-Graphgrammatik-basierte Diagrammanalyse

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

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

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

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

Generating diagram editors with DiaGen

Editor developer

Diagram editor

DiaGen editor

framework

DiaGen Designer DiaGen

Generated program

Specifi- cation

operates

Example: Message Sequence Charts (MSC)

Hypergraph model Modeler

Reduced hypergraph

model Reducer Parser Derivation

structure Diagram

Drawing tool

Editor user

selects operation

Hypergraph transformer

modifies reads

Layout information Layouter

Semant. represen-

tation

Attribute evaluation

Highlights syntactically correct sub-diagrams

Abstract Representation Diagram Semantics

Reduced hypergraph

structure Diagram

Drawing tool

Editor user

selects operation

modifies reads

Semant. represen-

tation

Set of diagram components

Diagram components & Relations

Reducer rules Hypergraph grammar

Attribute hypergraph grammar

Programmed (hyper-) graph- transformations

Constraints

Reduced hypergraph

structure Diagram

Drawing tool

Editor user

selects operation

modifies reads

Semant. represen-

tation

Example: Message Sequence Charts (MSC)

Diagram components:

Action

Lifeline of an entity

Message

Reduced hypergraph

structure Diagram

Drawing tool

Editor user

selects operation

modifies reads

Semant. represen-

tation

Hypergraph Model

lifeline lifeline

Component hyperedge

Hypergraph Model

lifeline lifeline

Component hyperedge

Attachment area of the

diagram component

Nodes represent attachment areas

Hypergraph Model with Relationship Edges

lies on

lies on lies on

lifeline lifeline

Relationship edges connect nodes whose attachment areas are

related in a specific way

Reduced hypergraph

structure Diagram

Drawing tool

Editor user

selects operation

modifies reads

Highlights syntactically correct sub-diagrams Semant. represen-

tation

Hypergraph Model with Relationship Edges

lies on

lies on lies on

lifeline lifeline

Reduced Hypergraph Model

message next

action

nextLife

action

message

“Reducing“ the Hypergraph Model

lies on lies on lies on

lifeline lifeline line

message next

action

nextLife

action

message

“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

message next

action

nextLife

action

message

“Reducing“ the Hypergraph Model lifeline lifeline

nextLife line1 line2

Condition: line1.x < line2.x

lifeline

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)

message next

action

nextLife

action

message

lies on

lifeline

l l = e

with e2.y < e.y

Textual representation:

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

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

f1,1 f

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-

Reduced hypergraph

structure Diagram

Drawing tool

Editor user

selects operation

modifies reads

Semant. represen-

tation

Hypergraph Grammar

send recv

message

send recv ::=

a b b a

Lifelines Lifeline

nextLife

Lifeline Lifelines ::=

Lifeline line line

EventSeq

::= a a

a Event action send recv ::=

a a a a

EventSeq Event

EventSeq

::= a a

context-free productions

embedding production

•  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

Reduced hypergraph

structure Diagram

Drawing tool

selects operation

modifies reads

Semant. represen-

tation

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

pL pC pR

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

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

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’

G G’

Diagram a) Diagram b)

Remark:

The sign “!” labels any arrow which

represents an inclusion.

[Schürr94]

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

L1 C1 R1 ← → →

L2 C2 R2 ← →

L3 C3 R3 ← →

Ln Cn Rn ← →

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.

L1 C1 R1 ← →

L2 →

L3 →

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

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

lifeline lifeline

nextLife line1 line2

Condition: line1.x < line2.x

lifeline

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

line1 line2

Negative Anwendbarkeitsbedingungen •  Produktionstripel (mit Kanten statt Attributbedingungen)

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

⇐ ⇐ ⇐

Unifikation von Knoten •  Beispiel Flussdiagramme

Unifikation von Knoten

start o

stmt o

Flussdiagramme

o start

stmt i

start o

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:

stmt o

start o

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

Flussdiagramme

stmt o

start o

stmt o

start o

Flussdiagramme

stmt o

start o

stmt o

start o

•! Lösung durch Kombination von Produktionstripeln:

Flussdiagramme

stmt o

start o

stmt o

start o

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

Tripel-Graphgrammatik-basierte Diagrammanalysehof/gratra081114/GTD08-Minas.pdf · Example: Message...

Documents

00880115 Techniker-Handbuch für Lifeline Vi und Vi+€¦ · 1. Zu diesem Handbuch 4 Lifeline Vi und Lifeline Vi+ – Techniker-Handbuch, 05/13 (Rev. 2.0), 00 8801 15 1.2.1 Lifeline

Musik + Message 1_2016

i.s.h.med MCI Message Communication Infrastructurege 4 mit der Message Communication Infrastructure (MCI) eine Komponente in i.s.h.med, die dem seit Jahren stetig steigenden Bedarf

Strukturen in Sätzen und Wörtern - fb10.uni-bremen.de · schwarz Polarfuchs weiß Oboe Material . Holz Tuba Metall . Abbildung 2: Objekt-Attribut-Wert Tripel 2 . 1 »Tripel« bedeutet

6350 Bedienungsanleitung DeTeWe Message 800 - direct.de message 800... · Message 800 Message 800 Willkommen bei DeTeWe Vielen Dank, dass Sie sich für ein Produkt von DeTeWe entschieden

DEFIBRILLATOREN DEF:DCE-110G Lifeline AED defibtech … · 2017. 3. 9. · DEF:DCF-210 Ultra-Langzeit-Batterie für Lifeline AED 259,00 7 Jahre Standby, bis zu 300 Defibrillationen

Nachrichtenorientierte Middleware &Nachrichtenorientierte ... · Message Oriented Middleware (MOM) • MOM ist die Middleware-Technologie zum Message-Passing-Kommunika-tionsmodell

Message in a bottle:

Semantische Netze. Deklarative Formen der Wissensrepräsentation 1.Semantische Netze 2.Objekt-Attribut-Wert-Tripel 3.Frames (Schemata, Scripts) 4.Prädikatenlogik

Message Oriented Middleware (MOM)

Message Monitoring Online-Handbuch - Clearstream · Message-Monitoring Online-Handbuch 9 2. Transaktion MAMJ 2.1. MAMJ-Einstieg Für den Aufruf der Transaktion MAMJ sind entweder

Message from Chapter ChairmanMessage from Chapter Chairman

e-Desk Status Report - c-point.be · e-Desk Status Report – Message Implementation Guide Page 6 of 32 2.2 Message Header (UNH) The message header is a service segment starting and

Message Passing Interface (MPI)

Lifeline Nela Orahovac Quanten-Kinesiologie-llÍecoach ... · Quanten-Kinesiologie-llÍecoach Terminanfrage unter lifeline-coaching@web de 0163 - 3424984 Reiki & begleitende ... traditionellen

Kapitelplanung Netzplantechnik - rybin · Web viewLösungsalgorithmen für MPM sind z.B. das Verfahren von FORD oder der Tripel-Algorithmus von Floyd/Warshall, Lösungsalgorithmen

Web Services and Service Flows - dbs.uni-leipzig.de · Message-Format z.B. MIME-Encoded, ASCII, SOAP Interaction Style RPC style / message style SMPT (Simple Mail Transfer Protocol),

Defibtech Lifeline AED Semi-Automatischer Externer Defibrillator

Lifeline – Ernährung mit system

Musik + Message 2_2015