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 * Sprachen als Schnittstellen zwischen Software-Werkzeugen, Datenaustauschformate, z. B. HTML, XML * Bäume zur Repräsentation strukturierter Daten, z. B. in HTML * Struktur von Protokollen beim Austausch von Nachrichten zwischen Geräten oder Prozessen
Mo11-13AM
Fr9-11AM
(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 Rows ::= Row * Row ::= quotesingle quotesingle Cells quotesingle quotesingle Cells ::= Cell * Cell ::= quotesingle quotesingle Cell ::= quotesingle quotesingle
TagZeit
Raum
Mo11:00-12.30 AM
quotesingle Text quotesingle
Frquotesingle Table 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. --------------------------------------------------------------------------------