Mod-6.1
6 Modellierung von Strukturen
6.1 Kontextfreie Grammatiken
Kontextfreie Grammatik (KFG): formaler Kalkül, Ersetzungssystem; definiert
* Sprache als Menge von Sätzen; jeder Satz ist eine Folge von Symbolen
* Menge von Bäumen; jeder Baum repräsentiert die Struktur eines Satzes der Sprache
Beispiel zu HTML:
Anwendungen:
* Programme einer Programmiersprache und deren Struktur,
z. B. Java, Pascal, C
Mo |
* Sprachen als Schnittstellen zwischen Software-Werkzeugen, 11-13 |
Datenaustauschformate, z. B. HTML, XML AM |
* Bäume zur Repräsentation strukturierter Daten,
z. B. in HTML Fr |
* Struktur von Protokollen beim Austausch von Nachrichten 9-11 |
zwischen Geräten oder Prozessen AM |
(c) 2008 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 601
Ziele:
Einsatz von KFGn kennenlernen
in der Vorlesung:
Erläuterungen zu den Anwendungen
nachlesen:
Kastens, Kleine Büning: Modellierung, Abschnitt 6.1
--------------------------------------------------------------------------------
Mod-6.2
Kontextfreie Grammatik
Eine kontextfreie Grammatik G = (T, N, P, S) besteht aus:
T Menge der Terminalsymbole (kurz: Terminale)
N Menge der Nichtterminalsymbole (kurz: Nichtterminale)
T und N sind disjunkte Mengen
S element N Startsymbol (auch Zielsymbol)
P reflexsubset N multiply V* Menge der Produktionen; (A, x) element P, mit A element N und x element V*;
statt (A, x) schreibt man A ::= x
V = T union N heißt auch Vokabular, seine Elemente heißen Symbole
Man sagt "In der Produktion A ::= x steht A auf der linken Seite und x auf der rechten Seite."
Man gibt Produktionen häufig Namen: p1: A ::= x
In Symbolfolgen aus V* werden die Elemente nur durch Zwischenraum getrennt: A ::= B C D
Beispiel: Produktionsmenge P =
Name N V*
Terminale T = { (, ) } {
p1: Klammern::='(' Liste ')'
Nichtterminale N = { Klammern, Liste } p2: Liste ::= Klammern Liste
p3: Liste ::=
Startsymbol S = Klammern }
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 602
Ziele:
KFG Definition lernen
in der Vorlesung:
* Erläuterung der Bergriffe an dem Beispiel
* Erläuterung der Notation von Produktionen
* Unbenannte Terminale werden gekennzeichnet, um Verwechselungen mit KFG-Zeichen zu vermeiden: '('
nachlesen:
Kastens, Kleine Büning: Modellierung, Abschnitt 6.1
--------------------------------------------------------------------------------
Mod-6.3
Bedeutung der Produktionen
Eine Produktion A ::= x ist eine Strukturregel: A besteht aus x
Beispiele:
DeutscherSatz ::= Subjekt Prädikat Objekt
Ein DeutscherSatz besteht aus (der Folge) Subjekt Prädikat Objekt
Klammern ::= '(' Liste ')'
Zuweisung ::= Variable ':=' Ausdruck
Variable ::= Variable '[' Ausdruck ']'
Produktion graphisch als gewurzelter Baum
mit geordneten Kanten und mit Symbolen als Knotenmarken:
Zuweisung Variable
Variable := Ausdruck Variable [ Ausdruck ]
(c) 2008 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 603
Ziele:
Produktionen verstehen
in der Vorlesung:
Erläuterungen der beiden Rollen von Produktionen:
* Definition von Struktur: "besteht aus"
* Definition von Ersetzungen
* Siehe auch Mod-6.5 zur graphischen Darstellung von Produktionen.
nachlesen:
Kastens, Kleine Büning: Modellierung, Abschnitt 6.1
--------------------------------------------------------------------------------
Mod-6.4
Ableitungen
Produktionen sind Ersetzungsregeln: Ein Nichtterminal A in einer Symbolfolge u A v kann
durch die rechte Seite x einer Produktion A ::= x ersetzt werden.
Das ist ein Ableitungsschritt; er wird notiert als u A v => u x v
z. B. Klammern Klammern Liste => Klammern ( Liste ) Liste
mit Produktion p1
Beliebig viele Ableitungsschritte nacheinander angewandt heißen Ableitung;
notiert als u =>* v
Eine kontextfreie Grammatik definiert eine Sprache; das ist eine Menge von Sätzen.
Jeder Satz ist eine Folge von Terminalsymbolen, die aus dem Startsymbol ableitbar ist:
L(G) = { w | w element T* und S =>* w }
Grammatik auf Mod-6.2 definiert geschachtelte Folgen paariger Klammern als Sprache:
{ (), (()), (()()()),((()())(())), ... } reflexsubset L(G)
Ableitung des Satzes (()()): S = Klammern
=> ( Liste )
=> ( Klammern Liste )
=> ( Klammern Klammern Liste )
=> ( Klammern ( Liste ) Liste )
=> ( ( Liste ) ( Liste ) Liste )
=> ( ( ) ( Liste ) Liste )
=> ( ( ) ( ) Liste )
=> ( ( ) ( ) )
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 604
Ziele:
Ableitungsbegriff verstehen
in der Vorlesung:
Erläuterungen dazu
* Beispiele für Ableitungen
* Beispiele für Sprachen
nachlesen:
Kastens, Kleine Büning: Modellierung, Abschnitt 6.1
--------------------------------------------------------------------------------
Mod-6.5
Ableitungsbäume
Jede Ableitung kann man als gewurzelten Baum darstellen:
Die Knoten mit ihren Marken repräsentieren Vorkommen von Symbolen.
Ein Knoten mit seinen direkten Nachbarn repräsentiert die Anwendung einer Produktion.
Die Wurzel ist mit dem Startsymbol markiert.
Terminale kommen nur an Blättern vor.
Produktionen: ein Ableitungsbaum:
Klammern
Klammern p1
p1 ( )
( Liste ) Liste
p2
Klammern Liste
Liste p1 p2
p2 ( Liste ) Klammern Liste
Klammern Liste p1 p2
( Liste ) Klammern Liste
p1 p3
Liste ( Liste )
p3
der Satz dazu: (()()())
Satz zum Baum: Terminale im links-abwärts Durchgang
(c) 2008 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 605
Ziele:
Ableitungsbaum verstehen
in der Vorlesung:
* Konstruktion des Baumes durch Zusammensetzen von Produktionsanwendungen am "Bastelbogen" zeigen,
* Zusammenhang zum Satz der Sprache
nachlesen:
Kastens, Kleine Büning: Modellierung, Abschnitt 6.1
--------------------------------------------------------------------------------
Mod-6.6
Beispiel: Ausdrucksgrammatik
p1: Ausdruck ::= Ausdruck BinOpr Ausdruck
p2: Ausdruck ::= Zahl
Ableitungsbaum zum Ausdruck
p3: Ausdruck ::= Bezeichner a / (b - 1)
p4: Ausdruck ::= '(' Ausdruck ')' Ausdruck
p5: BinOpr ::= '+'
p6: BinOpr ::= '-' Ausdruck BinOpr Ausdruck
p7: BinOpr ::= '*' / ( Ausdruck )
Bezeichner
p8: BinOpr ::= '/' a
Ausdruck BinOpr Ausdruck
Startsymbol: Ausdruck
Terminale: -
Bezeichner Zahl
T = { Zahl, Bezeichner, (, ), +, -, *, / } b 1
Schreibweise der Terminale
Zahl und Bezeichner wird nicht in der KFG definiert.
Grammatik ist mehrdeutig: Es gibt Sätze, die mehrere Ableitungsbäume haben.
(c) 2008 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 606
Ziele:
Vollständiges Beispiel sehen
in der Vorlesung:
* Erläuterungen dazu.
* Vergleich mit Kantorowitsch-Bäumen.
* Diese Grammatik ist mehrdeutig: z. B. hat der Satz a+b+c mehrere Ableitungsbäume.
nachlesen:
Kastens, Kleine Büning: Modellierung, Abschnitt 6.1
--------------------------------------------------------------------------------
Mod-6.7
Beispiel: Tabellen in HTML
HTML: Hypertext Markup Language zur Darstellung von verzeigerten Dokumenten,
insbesondere im WWW verwendet.
typisch: geklammerte Strukturen mit Klammern der Form ....
hier: vereinfachter Ausschnitt aus der Sprache zur Darstellung von Tabellen.
Produktionen der kontextfreien Grammatik: Beispieltext in HTML:
Table ::= quotesingle quotesingle Rows quotesingle
quotesingle
Tag |
Rows ::= Row * Zeit |
Row ::= quotesingle
quotesingle Cells quotesingle
quotesingle Raum |
Mo |
Cells ::= Cell * 11:00-12.30 |
AM |
Cell ::= quotesingle quotesingle Text quotesingle | quotesingle Fr |
Cell ::= quotesingle quotesingle Table quotesingle | quotesingle 9:15-10:45 |
AM |
Erweiterung der Notation von KFGn: Darstellung der Tabelle:
X * auf der rechten Seite einer Produktion Tag Zeit Raum
steht für eine beliebig lange Folge von X Mo 11:00-12.30 AM
(gleiche Bedeutung wie bei Wertebereichen) Fr 9:15-10:45 AM
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607
Ziele:
HTML-Ausschnitt verstehen
in der Vorlesung:
Erläuterungen
* zum *-Operator (siehe Mod-2.8b),
* zur Struktur von HTML,
* zum Beispiel,
* zur Baumdarstellung
Übungsaufgaben:
Beschreiben Sie die Operationsfolgen zur Bedienung des Getränkeautomaten durch eine KFG.
--------------------------------------------------------------------------------
Mod-6.7a
6.2 Baumstrukturen in XML
Übersicht
XML (Extensible Markup Language, dt.: Erweiterbare Auszeichnungssprache)
* seit 1996 vom W3C definiert, in Anlehnung an SGML
* Zweck: Beschreibungen allgemeiner Strukturen (nicht nur Web-Dokumente)
* Meta-Sprache ("erweiterbarquotedblright ):
Die Notation ist festgelegt (Tags und Attribute, wie in HTML),
Für beliebige Zwecke kann jeweils eine spezielle syntaktische Struktur definiert
werden (DTD)
Außerdem gibt es Regeln (XML-Namensräume), um XML-Sprachen in andere
XML-Sprachen zu importieren
* XHTML ist so als XML-Sprache definiert
* Viele Sprachen sind aus XML abgeleitet, z.B. SVG, MathML, SMIL, RDF, WML
* individuelle XML-Sprachen werden definiert, um strukturierte Daten zu
speichern, die von Software-Werkzeugen geschrieben und gelesen werden
* XML-Darstellung von strukturierten Daten kann mit verschiedenen Techniken in
HTML transformiert werden, um sie formatiert anzuzeigen:
XML+CSS, XML+XSL, SAX-Parser, DOM-Parser
Dieser Abschnitt orientiert sich eng an SELFHTML (Stefan Münz), http://de.selfhtml.org
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607a
Ziele:
Rolle von XML verstehen
in der Vorlesung:
Die Aspekte werden einführend erklärt.
--------------------------------------------------------------------------------
Mod-6.7b
3 elementare Prinzipien
Die XML-Notation basiert auf 3 elementaren
Prinzipien:
A: Vollständige Klammerung durch Tags Hello
World
a
B:Klammerstruktur ist äquivalent zu
gewurzeltem Baum b c
Hello World
a ::= b c
C:Kontextfreie Grammatik definiert Bäume; b ::= PCDATA
eine DTD ist eine KFG c ::= PCDATA
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607b
Ziele:
Prinzipien der XML-Notation
in der Vorlesung:
Kurze Erklärung der Prinzipien.
--------------------------------------------------------------------------------
Mod-6.7c
Notation und erste Beispiele
Ein Satz in einer XML-Sprache ist ein Text, der durch Tags strukturiert wird.
Tags werden immer in Paaren von Anfangs- und End-Tag verwendet:
Paderborn
Anfangs-Tags können Attribut-Wert-Paare enthalten:
05251606686
Die Namen von Tags und Attributen können für die XML-Sprache frei gewählt werden.
Mit Tags gekennzeichnete Texte können geschachtelt werden.
2
(a+b) in MathML:
Mustermann
Max
a
+
Hauptstr 42 b
Paderborn
33098
2
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607c
Ziele:
Notation von XML verstehen
in der Vorlesung:
An den Beispielen wird erklärt:
* Tags und Attribute werden für den speziellen Zweck frei erfunden,
* ein Tag-Paar begrenzt ein Element und benennt seine Rolle,
* geschachtelte Strukturen.
* Wir entwerfen eigene Sprachen!!
--------------------------------------------------------------------------------
Mod-6.7d
Ein vollständiges Beispiel
Datei mit der Definition der
Kennzeichnung des Syntaktischen Struktur dieser Datei mit Angaben zur
Dokumentes als XML-Datei XML-Sprache (DTD) Transformation in HTML
Mustermann
Max
Hauptstr 42
Paderborn
33098
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607d
Ziele:
Technische Angaben sehen
in der Vorlesung:
Am Beispiel wird erklärt:
* die 3 technischen Angaben,
* XML-Text.
--------------------------------------------------------------------------------
Mod-6.7e
Baumdarstellung von XML-Texten
Jeder XML-Text ist durch Tag-Paare vollständig geklammert (wenn er wohlgeformt ist).
Deshalb kann er eindeutig als Baum dargestellt werden. (Attribute betrachten wir hier nicht)
Wir markieren die inneren Knoten mit den Tag-Namen; die Blätter sind die elementaren Texte:
adressBuch
adresse
Mustermann
name
Max
nachname
Mustermann anschrift
Hauptstr 42 vorname
Paderborn Max
33098 strasse
Hauptstr 42 ort plz
Paderborn
33098
XML-Werkzeuge können die Baumstruktur eines XML-Textes
ohne weiteres ermitteln und ggf. anzeigen.
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607e
Ziele:
XML-Text als Baum verstehen
in der Vorlesung:
Am Beispiel wird erklärt:
* vollständige Klammerung durch Tags,
* definiert einen Baum,
* aus dem Baum kann man den Text wiederherstellen
--------------------------------------------------------------------------------
Mod-6.7f
Wohlgeformte XML-Texte
XML-Texte sind wohlgeformt (well-formed), wenn sie folgende Regeln erfüllen:
1. Ein Element beginnt mit einem Anfangs-Tag und endet mit einem gleichnamigen End-Tag.
Dazwischen steht eine evtl. leere Folge von Elementen und elementaren Texten.
2. Elementare Texte können beliebige Zeichen, aber keine Tags enthalten.
3. ein XML-Text ist ein Element.
wohlgeformt wohlgeformt nicht wohlgeformt
1
1 1
2 2
3
3 4
5
6
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607f
Ziele:
Regeln für wohlgeformte XML-Texte kennenlernen
in der Vorlesung:
Regeln und Beispiele werden erklärt.
--------------------------------------------------------------------------------
Mod-6.7g
Grammatik definiert die Struktur der XML-Bäume
Mit kontextfreien Grammatiken (KFG) kann man Bäume definieren.
Folgende KFG definiert korrekt strukturierte Bäume für das Beispiel Adressbuch:
adressBuch ::= adresse* adressBuch
adresse ::= name anschrift
name ::= nachname vorname adresse
Anschrift ::= strasse ort plz name
nachname ::= PCDATA nachname
vorname ::= PCDATA Mustermann
strasse ::= PCDATA vorname anschrift
ort ::= PCDATA Max
plz ::= PCDATA
strasse
Hauptstr 42 ort plz
Paderborn
33098
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607g
Ziele:
Definition durch KFG verstehen
in der Vorlesung:
Am Beispiel wird erklärt:
* Tag-Namen werden Nichtterminale,
* PCDATA ist das Terminal für die elementaren Texte,
* weiteren Baum skizzieren.
--------------------------------------------------------------------------------
Mod-6.7.h
Document Type Definition (DTD) statt KFG
Die Struktur von XML-Bäumen und -Texten wird in der DTD-Notation definiert. Ihre Konzepte
entsprechen denen von KFGn:
KFG DTD
adressBuch ::= adresse*
adresse ::= name anschrift
name ::= nachname vorname
Anschrift ::= strasse ort plz
nachname ::= PCDATA
vorname ::= PCDATA
strasse ::= PCDATA
ort ::= PCDATA
plz ::= PCDATA
weitere Formen von DTD-Produktionen:
(Y)+ nicht-leere Folge
(A | B) Alternative
(A)? Option
EMPTY leeres Element
(c) 2011 bei Prof. Dr. Uwe Kastens
--------------------------------------------------------------------------------
Vorlesung Modellierung WS 2011/12 / Folie 607h
Ziele:
DTD-Notation als KFG verstehen
in der Vorlesung:
Am Beispiel wird erklärt:
* Zuordnung der KFG- zu DTD-Konstrukten,
* Erklärung der weiteren Formen an Beispielen.
* Hinweis: Die DTD-Notation zur Definition von Attributlisten in Anfangs-Tags wird hier nicht beschrieben.
--------------------------------------------------------------------------------