Eignung von Grammatik-basiertem Layout für grafische Programmiersprachen

Seminar Layout-Algorithmen für GraphenInstitut für Informatik

Christian-Albrechts Universität zu Kiel

Kevin Hesse

2

Struktur

• Einführende Worte• Graph-Grammatik• Layout-Graph-Grammatik• Gruppierung von Teilgraphen und Parser-Graphen• Reversed Graph Grammar• VisPro• RGG mit Layout-Regeln in VisPro• Anwendung im Beispielfall• Auswertung

3

Einführende Worte

• Grammatik-basiertes Layout• Grafische Programmiersprachen• Kombination

4

Graph-Grammatik

• Definition Graph– Ein Graph G ist ein Tupel (V, E), wobei V die

Menge der Knoten, sowie E die Menge der gerichteten Kanten und somit Teilmenge von ist.

– Gibt es ferner eine Menge B von Beschriftungen, heißt eine Abbildung , die jedem Knoten eine Beschriftung zuordnet Knotenmarkierung.

– Eine Abbildung , die jeder Kante eine Beschriftung zuordnet, heißt entsprechend Kantenmarkierung.

5

Graph-Grammatik

• Definition Graph-Grammatik– Eine Graph-Grammatik S ist ein Tupel (N, T, A, R). N ist die

Menge der Nichtterminale, T die Menge der Terminale, das Anfangs-Nichtterminal und R die Menge der Regeln.– Eine Regel ist dabei das Tupel (L, R, C) mit L als linke Seite der

Regel in Form eines Nichtterminals. R ist die rechte Seite und stellt einen markierten gerichteten Graphen dar. C ist eine Menge von Einbettungsregeln mit und mit und die Kantenmarkierung, die Richtung der Kante und der betroffene Knoten. Zu interpretieren ist es wie folgt: Eine f-markierte Kante, die den nichtterminalen Knoten L durch eine d-gerichteten Kante mit dem Graphen verbindet, wird stattdessen an den Knoten g gelegt.

6

Graph-Grammatik

• Aufbau der Grammatik wie bei Wörtern• Graph muss markiert sein• Regeln müssen angepasst werden– Einbettungsinformationen– Graph als Rechte Seite der Regel

• Gleichheit bedeutet Isomorphie

7

Layout Graph-Grammatik

• Definition– Eine Layout Graph-Grammatik L ist ein Tupel (S, K) mit der

Graph-Grammatik S und der Layout-Komponente K(S) passend zu der Grammatik

– Für jede Regel existiert in K(S) eine Menge von Positionsbedingungen P(r)

– kann dabei entweder eine Positions- oder eine Kantenregel sein

– Eine Positionsregel beschreibt die Position von zwei Knoten über ihre Kante zueinander, eine Kantenregel beschreibt, selbiges für die Kanten die über die Einbettungsregel in r spezifiziert ist

8

Layout Graph-Grammatik

• Trotz Layout-Komponente wieder eine Graph-Grammatik

• Positionsbedingung müssen konsistent sein• Nach Brandenburg werden nur allgemein die

Horizontale und die Vertikale bedacht. Keine konkreteren Angaben

F. Brandenburg: Layout graph grammars: The placement approach

9

Gruppierung von Teilgraphen und Parser-Graphen nach McCreary et al.

• Bildung von Gruppen von Teilgraphen• Parser-Graph, gebildet aus Gruppen als

Knoten und Nichtterminalen als Blätter• Ein Algorithmus bildet aus dem Parser-Graph

mit Hilfe von Relationsinformationen einen neuen Graphen

C. McCreary, R. Chapman, and F.-S. Shieh. Using graph parsing for automatic graph drawing

10

Reversed Graph Grammar

• Nicht kontextfrei• Keine Kanten im herkömmlichen Sinne• Knoten enthalten Verbindungsinformationen

K. Z. D-Q. Zhang. Reserved Graph Grammar: A Specication Tool for Diagrammatic VPLs

11

Struktur

• Einführende Worte• Graph-Grammatik• Layout-Graph-Grammatik• Gruppierung von Teilgraphen und Parser-Graphen• Reversed Graph Grammar• VisPro• RGG mit Layout-Regeln in VisPro• Anwendung im Beispielfall• Auswertung

12

VisPro

• Programm zum erstellen von visuellen Programmiersprachen

• Grammatik der Sprache über Graph-Grammatik

• Parser zur Auswertung kann generiert werden• Layout-Generierung kann auf den Regeln der

Auswertung der Sprache beruhen

K. Z. D-Q. Zhang. VisPro: A Visual Language Generation Toolset

13

RGG mit Layout-Regeln in VisPro

• Der Parser kann beim Prüfen der Syntax direkt das neue Layout berechnen

• Beim Auswerten des Graphen kann dann das neue Layout gezeichnet werden

• Layout ist an Korrektheit gebunden

14

K.-B. Zhang, K. Zhang, and M. Orgun. Grammar-based layout for a visual programming language generation system

15

Anwendung im Beispielfall

K.-B. Zhang, K. Zhang, and M. Orgun. Grammar-based layout for a visual programming language generation system

16

Anwendung im Beispielfall

1. Prüfen der Syntax2. Parser-Graph mit Gruppen erstellen3. Größen-Bestimmung der Teilbäume in den

Gruppen4. Optimierung der Kantenverläufe5. Bestimmung der Positionen der einzelnen

Knoten anhand der Layout-Regeln

17

Auswertung

• Anwendbarkeit– Programmabhängig, unwahrscheinlich, dass viele

Programme solch Tiefe Layout-Bestimmungen anbieten

– Mit VisPro jedoch, einfach und nebenbei umsetzbar

– Kann an jede visuelle Programmiersprache angepasst werden

18

Auswertung

• Endnutzerfreundlichkeit– Visuelle Programmiersprachen Entwickler (VisPro):• Kann mit den syntaktischen Regeln zusammen erstellt

werden• Ergibt sich mit der Sprache

– Nutzer von solchen Programmiersprachen:• Layout ist intuitiv, da an Syntax gekoppelt• Kein zusätzlicher Aufwand, Layout wird, bei korrekter

Syntax, angepasst

19

Auswertung

• Flexibilität– Wenig, da es sich um ein Regelsystem handelt– Ausnahmen sind schwer einzurichten, grade

wegen der Verknüpfung zur Syntax– Jede Regel kann jedoch individuell das Layout

beeinflussen und die Einteilung in Gruppen tut dies ebenso, daher nicht ganz unflexibel

20

Auswertung

• Fazit+ Passt sehr gut zu visuellen Programmiersprachen+ Benötigt keine weiteren Programmierkenntnisse und es müssen keine Algorithmen angepasst werden- Wenig Flexibel- Entwicklungsprogramm muss diese Art von Layout unterstützen

21

Ende

• Fragen?