E EWS-3.1 E2. Symbole und Syntax Überblick Grundbegriffe zur formalen Definition von Sprachen: * Alphabet: Menge von Zeichen * Wort: Folge von Zeichen aus Alphabet - gebildet nach bestimmten Regeln (Ebene 1) Satz: Folge von Symbolen aus Vokabular - gebildet nach bestimmten Regeln (Ebene 2) (Wort, Satz), (Zeichen, Symbol) und (Alphabet, Vokabular) paarweise synonym * Sprache: Menge von Worten bzw. Sätzen Kalküle zur Bildung von Worten und Sätzen: * reguläre Ausdrücke zur Definition der Notation von Grundsymbolen (Ebene 1 der Spracheigenschaften) zur Definition von Textmustern angewandt zum Suchen und Ersetzen von Zeichenfolgen programmiert in PHP, Perl, Unix-sh * kontextfreie Grammatik zur Definition der Menge der syntaktisch korrekten Sätze einer Sprache (Ebene 2 der Spracheigenschaften) Struktur der syntaktisch korrekten Sätze einer Sprache (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 301 Ziele: Zusammenhang der Begriffe erkennen in der Vorlesung: * Die Begriffe werden kurz erklärt und * der Zusammenhang gezeigt. * Auf der lexikalischen Ebene werden meist die Bezeichnungen Wort, Zeichen, Alphabet benutzt; aus der syntaktischen Ebene spricht man stattdessen von Satz, Symbol, Vokabular - bei gleicher Bedeutung. * Die Anwendungen der Kalküle werden erklärt. -------------------------------------------------------------------------------- E EWS-3.2 Alphabete und Zeichenfolgen Ein Alphabet ist eine nicht-leere Menge von Zeichen zur Bildung von Zeichenfolgen. Wir betrachten hier nur Alphabete mit endlich vielen Zeichen. Alphabete werden in Formeln häufig mit Sigma bezeichnet; sonst gibt man ihnen individuelle Namen oder benutzt sie unbenannt. Beispiele: Sigma = {T, F} Dualziffern = {0, 1} Dezimalziffern = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Kleinbuchstaben = {a, b, ..., z} Nukleotide = {A, C, G, U} ASCII = standardisierter Zeichensatz mit 128 Zeichen Ein Wort über einem Alphabet A ist eine Folge von Zeichen aus A. formal: eine Folge a1 a2 ... an, mit ai element A, für i = 1,..,n. n ist die Länge der Folge bzw. die Länge des Wortes. Beispiele: Wort der Länge 7 über dem Alphabet Dualziffern: 1001101 Die leere Folge bzw. das leere Wort wird mit epsilon (epsilon) bezeichnet. (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 302 Ziele: Wörter über Alphabeten in der Vorlesung: Erläuterungen und Beispiele dazu -------------------------------------------------------------------------------- E EWS-3.3 Reguläre Ausdrücke Ein regulärer Ausdruck R definiert eine Mengen von Worten über einem Alphabet A, die Sprache L (R). Ein regulärer Ausdruck kann aus folgenden 8 Formen rekursiv zusammengesetzt sein. F und G seien reguläre Ausdrücke. regulärer Sprache L (R) Erklärung Ausdruck R a { a } Zeichen a als Wort F G { f g | f element L(F), g element L(G) } Zusammenfügen von 2 Worten F | G { f | f element L(F) } union { g | g element L(G) } Alternativen epsilon { epsilon } das leere Wort ( F ) L(F) Klammerung F + { f1 f2 ... fn | fi element L(F), für ngreaterequal 1, i=1,..n} nicht-leere Folgen von Worten aus L(F) F * { epsilon } union L(F +) Folgen von Worten aus L(F) F n { f1 f2 ... fn | fi element L(F), für i = 1,..n} Folgen von genau n Worten aus L(F) (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 303 Ziele: Definition von regulären Ausdrücken verstehen in der Vorlesung: Erläuterungen zu * rekursiver Definition, * Hintereinanderschreibung von Zeichen und Teilworten, * Alternativen, * leer und Klammern, * Folgen von Worten Verständnisfragen: Unterscheiden Sie: * das leere Wort, * die leere Menge, * die Menge, die nur das leere Wort enthält. -------------------------------------------------------------------------------- E EWS-3.4 Struktur eines regulären Ausdruckes 1 1 (0 | 1)* 0 0 Zusammenfügen, 5-fach * Folge ( ) Klammern | Alternative 1 1 0 1 0 0 Zeichen verbal: Jedes Wort aus der Sprache dieses regulären Ausdruckes besteht aus zwei 1, gefolgt von beliebig vielen 0 oder 1, gefolgt von zwei 0. (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 304 Ziele: Aufbau von regulären Ausdrücken verstehen in der Vorlesung: Erläuterungen: * rekursive Konstruktion, * Struktur erkennen. * Bedeutung folgt der Struktur. * Verbale Beschreibung folgt der Struktur. * Das Alphabet ergibt sich aus den Zeichen, die in dem regulären Ausdruck vorkommen. -------------------------------------------------------------------------------- E EWS-3.5 Beispiele für reguläre Ausdrücke Name regulärer Ausdruck A Worte aus seiner Sprache L(A) Abc = (a | b) (c | d | epsilon ) ac bc ad bd a b Anrede = Sehr geehrte(r | epsilon ) (Frau | Herr) Sehr geehrte Frau Dig = 0 | 1 | ... | 9 7 sLet = a | b | ... | z x cLet = A | B ... | Z B Let = sLet | cLet m N Bezeichner = Let ( Let | Dig )* Maximum min3 a GeldBetrag = Dig +,Dig 2 23,95 0,50 KFZ = (cLet | cLet 2 | cLet 3)-(cLet | cLet 2)-(Dig | Dig 2 | Dig 3 | Dig 4) PB-AX-123 Dual = 13 ( 1 | 0 )* 03 1111000 111000 1111101010000 Wenn Namen von regulären Ausdrücken in regulären Ausdrücken verwendet werden, müssen sie von den Zeichen unterschieden werden können; hier Namen kursiv. (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 305 Ziele: Reguläre Ausdrücke anwenden lernen in der Vorlesung: Einen regulären Ausdruck verstehen: * Struktur erkennen, * Bedeutung erkennen, verbal beschreiben, * Sprache herleiten, * Beispiele für Worte aus der Sprache geben. Einen regulären Ausdruck entwerfen: * Beispiele für Worte aus der Sprache geben. * Sprache herleiten, verbal beschreiben, * Struktur entwerfen, * regulären Ausdruck aufschreiben. -------------------------------------------------------------------------------- E EWS-3.6 Beispiele für Definitionen von Grundsymbolen Pascal_Identifier = Let (Let | Dig)* C_Identifier = ( Let | _) (Let | _ | Dig)* ADA_Identifier = Let ( (_ | epsilon ) (Let | Dig) )* PHP_Var_Identifier = $ ( Let | _) (Let | _ | Dig)* Pascal_Real = ((Dig +. Dig +) ( (e | E) (+ |- | epsilon ) Dig +) | epsilon ) | (Dig + (e | E) (+ | - | epsilon ) Dig +) HexDig = Dig | a | b | c | d | e | f | A | B | C | D | E | F HTML_CharRef = & ( Let+ | # Dig+ | #x HexDig+) ; (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 306 Ziele: Definitionen verstehen in der Vorlesung: * Reguläre Ausdrücke untersuchen, * Beispiele für Worte seiner Sprache angeben -------------------------------------------------------------------------------- E EWS-3.7 Reguläre Ausdrücke als Textmuster In Sprachen, die zur Textverarbeitung eingesetzt werden, benutzt man reguläre Ausdrücke, um Textmuster zu definieren. Beispiele: suche alle Dateinamen der Form ews(0|1|2|3|4|5|6|7|8|9)3.html in der Schreibweise von Unix-sh ls ews[0-9][0-9][0-9].html Aufruf einer PHP-Funktion preg_match ("/[dD]aß/", $absatz) sucht ein Textmuster in einer Zeichenreihe Muster Zeichenreihe $d = "[0-9]"; preg_match ("/ews$d$d$d\.html/", $files) Reguläre Ausdrücke als Textmuster sind umfassend in der Skriptsprache Perl definiert und so in PHP übernommen. Auf den vorigen Folien haben wir die grundlegenden Begriffe für reguläre Ausdrücke mit der dafür üblichen Notation eingeführt. In PHP, Perl, Unix-sh werden die gleichen Begriffe aber in anderer Notation verwendet. (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 307 Ziele: Anwendung von regulären Ausdrücke als Textmuster in der Vorlesung: * Beispiele erläutern. * Neue Notation begründen. -------------------------------------------------------------------------------- E EWS-3.8 Notation von regulären Ausdrücken in PHP a das Zeichen a F G Zusammenfügen von 2 Worten F | G Alternativen (F) Klammerung F? Option; wie F | epsilon F+ nicht-leere Folge von Worten aus L(F) F* beliebig lange Folge von Worten aus L(F) F{m,n} Folge mit mindestens m und höchstens n von Worten aus L(F) F{m} Folge mit genau m Worten aus L(F) [abc] alternativ ein Zeichen aus der Klammer [^abc] alternativ ein anderes Zeichen als die in der Klammer [a-zA-Z] alternativ ein Zeichen aus Zeichenbereichen . beliebiges Zeichen ^ Anfang der Zeichenfolge (nichts darf vorangehen) $ Ende der Zeichenfolge (nichts darf darauf folgen) (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 308 Ziele: Notation lernen in der Vorlesung: * Notationen vergleichen, * bisher definierte reguläre Ausdrücke umschreiben, * weitere Beispiele angeben. -------------------------------------------------------------------------------- E EWS-3.9 Beispiele für reguläre Ausdrücke in PHP-Notation Reguläre Ausdrücke kommen in PHP-Programmen immer als Zeichenreihenliterale (Strings) vor. Diese werden in " eingeschlossen, z. B. "1|0". Statt Namen für reguläre Ausdrücke zu definieren, weisen wir die Zeichenreihe einer Variablen zu, z. B. $binDig = "(1|0)"; Variable = regulärer Ausdruck als PHP-String $Abc = "(a|b)(c|d)?"; $Anrede = "Sehr geehrte(r)? (Frau|Herr)"; $Dig = "[0-9]"; $sLet = "[a-z]"; $cLet = "[A-Z]"; $Let = "[a-zA-Z]"; $Bezeichner = "[a-zA-Z][a-zA-Z0-9]*"; $GeldBetrag = "$Dig+,$Dig{2}"; $KFZ = "$cLet{1,3}-$cLet{1,2}-$Dig{1,4}"; $Dual = "1{3}[10]*0{3}"; (c) 2004 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 309 Ziele: Notationen üben in der Vorlesung: * Notationen vergleichen, * bisher definierte reguläre Ausdrücke umschreiben. -------------------------------------------------------------------------------- E EWS-3.10 Beispiele für Definitionen von Grundsymbolen in PHP-Notation $Pascal_Identifier = "[a-zA-Z][a-zA-Z0-9]*"; $C_Identifier = "[a-zA-Z_][a-zA-Z_0-9]*"; $ADA_Identifier = "[a-zA-Z](_?[a-zA-Z0-9])*"; $PHP_Var_Identifier = "\$[a-zA-Z_][a-zA-Z_0-9]*"; $Pascal_Exponent = "((e|E)(\+|-)?[0-9]+)"; $Pascal_Real = "(([0-9]+\.[0-9]+)$Exponent?)|([0-9]+$Exponent)"; $HexDig = "[0-9a-fA-F]"; $HTML_CharRef = "&(([a-zA-Z]+)|(#[0-9]+)|(#x$HexDig+));"; (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 310 Ziele: Notationen üben in der Vorlesung: * Notationen vergleichen, * bisher definierte reguläre Ausdrücke umschreiben. -------------------------------------------------------------------------------- E EWS-3.11 E2.2 Kontextfreie Grammatiken Kontextfreie Grammatik (KFG): formaler Kalkül zur Definition einer * 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 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 Beispiel: Tabellen in HTML: Table Row Row Data Data Data Data Data Data Mo 11-13 AM Fr 9-11 AM
Mo 11-13AM
Fr 9-11 AM
(c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 311 Ziele: Einsatz von KFGn kennenlernen in der Vorlesung: Erläuterungen zu den Anwendungen: * Struktur von HTML-Sätzen, * Struktur von Tabellen. * Bäume werden noch definiert. -------------------------------------------------------------------------------- E EWS-3.12 Definition: 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 disjunkt) S Startsymbol; S ist ein Nichtterminal: S element N P Menge der Produktionen jede Produktion hat die Form A ::= x A ist ein Nichtterminal, d. h. A element N und x ist eine (evtl. leere) Folge von Terminalen und Nichtterminalen, d. h. x element (T union N)* = V* 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 (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 312 Ziele: KFG Definition lernen in der Vorlesung: * Erläuterung der Begriffe am Beispiel der nächsten Folie EWS-3.13, * Erläuterung der Notation von Produktionen * Wir benutzen jetzt die Bezeichnungen Satz, Symbol und Vokabular statt Wort, Zeichen und Alphabet. * Die Angabe V* ist als regulärer Ausdruck zu verstehen, also "eine (evtl. auch leere) Folge beliebiger Symbole aus V. -------------------------------------------------------------------------------- E EWS-3.13 Beispiel zur Definition einer KFG Terminale T = { (, ) } Vokabular V = T union N = Nichtterminale N = { Klammern, Liste } { (, ), Klammern, Liste } Startsymbol S = Klammern Produktionen P = { Unbenannte Terminale p1: Klammern ::= quotesingle (quotesingle Liste quotesingle )quotesingle werden in quotesingle einge- p2: Liste ::= Klammern Liste schlossen, um Verwechselungen mit p3: Liste ::= KFG-Zeichen zu vermeiden: quotesingle (quotesingle } Namen N V* element element Diese Grammatik definiert eine Sprache, deren Sätze Folgen von geschachtelten Klammerpaaren sind, z. B. (()()) (()(())(()())) element (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 313 Ziele: Kleines Beispiel zum Verstehen der Definition in der Vorlesung: Die Begriffe der Definition von KFGn werd an diesem Beispiel erklärt: * Im Rahmen stehen die formal notwendigen Angaben T, N, S, P. * Vokabular und Namen von Produktionen sind zusätzliche Angaben. * Die Menge N wird aus den Symbolen auf den linken Seiten der Produktionen gebildet. * Symbole, die in Produktionen vorkommen, aber nicht in N sind, sind Terminale in T. * Die Anwendungder Produktionen als Regeln zur Definitionder Sprache derGrammatik folgt aufdennächsten Folien. -------------------------------------------------------------------------------- E EWS-3.14 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 dargestellt als gewurzelter Baum mit geordneten Kanten und mit Symbolen als Knotenmarken (zum Begriff "Baum" siehe nächste Folie): Zuweisung Variable Variable := Ausdruck Variable [ Ausdruck ] (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 314 Ziele: Produktionen verstehen in der Vorlesung: Erläuterungen der beiden Rollen von Produktionen: * Definition von Struktur: "besteht aus" * Definition von Ersetzungen * Siehe auch spätere Folie zur graphischen Darstellung von Produktionen. -------------------------------------------------------------------------------- E EWS-3.15 Bäume als Abstraktion Bäume bezeichnen in der Informatik abstrakte Datenstrukturen mit speziellen Eigenschaften. Sie werden zur abstrakten Beschreibung bestimmter Zusammenhänge eingesetzt. Ein besonders wichtiger ist die "besteht-aus"-Beziehung zwischen einem Objekt und seinen Teilen. Z. B. ein regulärer Ausdruck besteht aus Teilausdrücken: * ( ) | 1 1 0 1 0 0 (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 315 Ziele: Bäume als Abstraktion verstehen in der Vorlesung: Am Beispiel wird gezeigt, wie die besteht-aus Relation durch einen Baum dargestellt wird. -------------------------------------------------------------------------------- E EWS-3.16 Begriffe zu Bäumen Definition: Ein (gewurzelter, gerichteter) Baum besteht aus * einem Knoten k und * einer (evtl. leeren) Folge von Bäumen und Kanten von k zu jedem Element der Folge. * In einen Knoten mündet keine Kante, in alle anderen genau eine. Begriffe und Eigenschaften: * Wurzel: Knoten in den keine Kante mündet. * Blätter: Knoten, von denen keine Kante ausgeht Höhe 4 * innere Knoten: es mündet eine Kante und es gehen welche aus * Es gibt genau eine Wurzel. Tiefe 3 * Wenn ein Baum n Knoten hat, dann hat er n-1 Kanten. Tiefe 4 * Tiefe eines Blattes: Anzahl der Kanten auf dem Weg von der Wurzel zu dem Blatt. * Höhe des Baumes: größte Tiefe aller seiner Blätter. Knoten und/oder Kanten können beschriftet werden. Man kann die Pfeilspitzen weglassen, wenn die Wurzel bekannt ist. (c) 2006 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 316 Ziele: Definition und Begriffe zu Bäumen verstehen in der Vorlesung: Die Definition und die Begriffe werden an Beispielen erklärt. -------------------------------------------------------------------------------- E EWS-3.17 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: Klammern ::= ( Liste ) 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 EWS-3.13 definiert geschachtelte Folgen paariger Klammern als Sprachmenge: { (), (()), (()()()),((()())(())), ... } reflexsubset L(G) Ableitung des Satzes (()()): S = Klammern p1 => ( Liste ) p2 => ( Klammern Liste ) p2 => ( Klammern Klammern Liste ) p1 => ( KLammern ( Liste ) Liste ) p1 => ( ( Liste ) ( Liste ) Liste ) p3 => ( ( ) ( Liste ) Liste ) p3 => ( ( ) ( ) Liste ) p3 => ( ( ) ( ) ) -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 317 Ziele: Ableitungsbegriff verstehen in der Vorlesung: Erläuterungen dazu * Beispiele für Ableitungen * Beispiele für Sprachen -------------------------------------------------------------------------------- E EWS-3.18 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. Ein Ableitungsbaum entsteht durch "Zusammensetzten von Kopien der Produktionsbäume". Produktionen: ein Ableitungsbaum: Klammern Klammern p1 p1 ( Liste ) ( Liste ) p2 Klammern Liste Liste p1 p2 p2 ( Liste ) Klammern Liste Klammern Liste p3 p1 p2 ( Liste ) Klammern Liste p3 p1 p3 Liste ( Liste ) p3 p3 der Satz dazu: (()()()) (c) 2004 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 318 Ziele: Ableitungsbaum verstehen in der Vorlesung: * Konstruktion des Baumes durch Zusammensetzen von Produktionsanwendungen, -------------------------------------------------------------------------------- E EWS-3.19 Satz zum Ableitungsbaum Man erhält den Satz aus einem ein Ableitungsbaum: Ableitungsbaum, wenn man seine Terminale in der Klammern Reihenfolge eines links-abwärts p1 Durchlaufes aufschreibt. ( Liste ) p2 Klammern Liste Ein links-abwärts Durchlauf p1 p2 * beginnt mit einem Besuch der ( Liste ) Klammern Liste Wurzel, p1 p2 * bei dem Besuch eines Knotens ( Liste ) Klammern Liste werden nacheinander für jeden p1 p3 seiner Unterbäume von links ( Liste ) nach rechts jeweils ein links- abwärts Durchlauf durchgeführt. der Satz dazu: (()()()) (c) 2006 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 319 Ziele: Satz aus Ableitungsbaum herleiten in der Vorlesung: An Beispielen wird erklärt: * rekursiv definierter Baumdurchlauf, * Zusammenhang zum Satz der Sprache -------------------------------------------------------------------------------- E EWS-3.20 Grammatik für arithmetische Ausdrücke Grammatik für arithmetische Ausdrücke Produktionen: Beispiele: p1: Expr ::= Expr AddOpr Fact b + c p2: Expr ::= Fact p3: Fact ::= Fact MulOpr Opd a * (b + c) p4: Fact ::= Opd p5: Opd ::= quotesingle (quotesingle Expr quotesingle )quotesingle a * b + c p6: Opd ::= Ident a + b * c p7: AddOpr ::= quotesingle +quotesingle p8: AddOpr ::= quotesingle -quotesingle p9: MulOpr ::= quotesingle *quotesingle p10: MulOpr ::= quotesingle /quotesingle T = { (, ), +, -, *, /, Ident } N = { Expr, Fact, Opd, AddOpr, MulOpr} S = Expr (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 320 Ziele: Kleine, realistische Grammatik verstehen in der Vorlesung: An Beispielen wird erklärt: * Ableitungen und Bäume dazu bilden (mit EWS-3.21), * Rollen der Produktionen verstehen. -------------------------------------------------------------------------------- E EWS-3.21 Beispiel für eine Ableitung zur Ausdrucksgrammatik Satz der Ausdrucksgrammatik b + c Ableitungsbaum: Ableitung: Expr Expr p1 => Expr Addopr Fact Expr Addopr Fact p2 => Fact Addopr Fact Fact p4 => Opd Addopr Fact Opd p6 => Ident Addopr Fact Ident p7 => Ident + Fact + p4 => Ident + Opd Opd p6 => Ident + Ident Ident b + c b + c (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 321 Ziele: Zusammenhang zw. Ableitung und Ableitungsbaum in der Vorlesung: An dem Beispiel wird erklärt: * Baum stellt Ableitungsschritte dar. * Ableitungsschritte können in unterschiedlicher Reihenfolge ausgeführt werden, * die Bäume dazu sind identisch. -------------------------------------------------------------------------------- E EWS-3.22 Präzedenz und Assoziativität in Ausdrucksgrammatiken Die Struktur eines Satzes wird durch seinen Ableitungsbaum bestimmt. Ausdrucksgrammatiken legen dadurch die Präzedenz und Assoziativität von Operatoren fest. Im Beispiel hat AddOpr geringere Präzedenz als MulOpr, weil er höher in der Hierarchie der Kettenproduktionen Expr ::= Fact, Fact ::= Opd steht. Name Produktion p1: Expr ::= Expr AddOpr Fact Expr p2: Expr ::= Fact p1 p3: Fact ::= Fact MulOpr Opd Expr AddOpr Fact p4: Fact ::= Opd p2 p7 p3 p5: Opd ::= quotesingle (quotesingle Expr quotesingle )quotesingle Fact + Fact MulOpr Opd p6: Opd ::= Ident p4 p7: AddOpr ::= quotesingle +quotesingle p4 p9 p6 p8: AddOpr ::= quotesingle -quotesingle Opd Opd * Ident p9: MulOpr ::= quotesingle *quotesingle p6 p6 c p10: MulOpr ::= quotesingle /quotesingle Ident Ident a b Im Beispiel sind AddOpr und MulOpr links-assoziativ, weil ihre Produktionen links-rekursiv sind, d. h. a + b - c entspricht (a + b) - c. (c) 2006 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 322 Ziele: Struktur von Ausdrucksgrammatiken verstehen in der Vorlesung: Erläuterungen dazu am Beispiel: * Präzedenz (Bindungsstärke) von Operatoren, * Assoziativität von Operatoren, * Kettenproduktion: genau ein Nichtterminal auf der rechten Seite. * Zusammenhang zu Produktionen zeigen, * Variation des Beispiels Verständnisfragen: * Wie ändert sich die Sprache, wenn Produktion p1 durch Expr ::= Fact '+' Fact ersetzt wird? Für welche Art von Operatoren wäre das sinnvoll? -------------------------------------------------------------------------------- E EWS-3.23 Schemata für Ausdrucksgrammatiken Ausdrucksgrammatiken konstruiert man schematisch, sodass strukturelle Eigenschaften der Ausdrücke definiert werden: eine Präzedenzstufe, binärer eine Präzedenzstufe, binärer Operator, linksassoziativ: Operator, rechtsassoziativ: A ::= A Opr B A ::= B Opr A A ::= B A ::= B eine Präzedenzstufe, eine Präzedenzstufe, unärer Operator, präfix: unärer Operator, postfix: A ::= Opr A A ::= A Opr A ::= B A ::= B Elementare Operanden: nur aus Geklammerte Ausdrücke: nur aus dem Nichtterminal der höchsten dem Nichtterminal der höchsten Präzedenzstufe (sei hier H) Präzedenzstufe (sei hier H) abgeleitet; abgeleitet: enthalten das Nichtterminal der niedrigsten Präzedenzstufe (sei hier A) H ::= Ident H ::= quotesingle (quotesingle A quotesingle )quotesingle (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 323 Ziele: Schemata erkennen können in der Vorlesung: Erläuterungen dazu Übungsaufgaben: Anwenden der Schemata zum Verstehen von Ausdrucksgrammatiken -------------------------------------------------------------------------------- E EWS-3.24 Nützliche Grammatik-Konstrukte beliebig lange Folgen von Stmt z. B. in: Abkürzung für beliebig lange Folgen: Block ::= quotesingle {quotesingle Stmts quotesingle }quotesingle Block ::= quotesingle {quotesingle Stmt* quotesingle }quotesingle Stmts ::= Stmts Stmt Die 2 Produktionen für Stmts entfallen. Stmts ::= nicht leere Folgen von Stmt: Entsprechend für nicht-leere Folgen: Stmts ::= Stmts Stmt Block ::= quotesingle {quotesingle Stmt+ quotesingle }quotesingle Stmts ::= Stmt nicht-leere Folgen von Stmt Alternative Produktionen für dasselbe getrennt durch ;: Nichtterminal mit | zusammenfassen, z. B. Stmts ::= Stmts quotesingle ;quotesingle Stmt Stmts ::= Stmts quotesingle ;quotesingle Stmt | Stmts ::= Stmt Stmt Optionale Parameter z. B. in: Optionales mit [ ] klammern, z. B. Call ::= Name quotesingle (quotesingle ParamOpt quotesingle )quotesingle Call ::= Name quotesingle (quotesingle [ Parameter ] quotesingle )quotesingle ParamOpt ::= Parameter Die 2 Produktionen für ParamOpt entfallen. ParamOpt ::= (c) 2006 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 324 Ziele: Produktionen für Folgen und Optionen verstehen in der Vorlesung: Die Konstrukte und Abkürzungen werden an Beispielen erklärt: * Beispiele für Sätze aus Block und Call ableiten. * * und + mit regulären Ausdrücken vergleichen. -------------------------------------------------------------------------------- E EWS-3.25 Ausschnitte aus einer HTML-Grammatik Die Syntax von HTML ist im Kalkül der "Document Type Definition (DTD)" formal definiert. Man kann Ausschnitte zu einigen Aspekten von HTML in KFGn übertragen. Es folgen Beispiele dafür. Grundstruktur (ohne Attribute innerhalb von Tags): HTMLDoc ::= quotesingle quotesingle quotesingle quotesingle HeadContent quotesingle quotesingle quotesingle quotesingle Block quotesingle quotesingle quotesingle quotesingle Block ::= Paragraph | Table | List | Heading | ... Paragraph ::= quotesingle

quotesingle Inline [quotesingle

quotesingle ] Inline ::= ... Fließtext mit Auszeichnungen ohne Blockstrukturen ... Flow ::= Block | Inline Tabellen: Table ::= quotesingle quotesingle Row* quotesingle
quotesingle Row ::= quotesingle quotesingle Cell* quotesingle quotesingle Cell ::= quotesingle quotesingle Flow quotesingle quotesingle (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 325 Ziele: Produktionen aus einer größeren Grammatik verstehen in der Vorlesung: An bekannten Beispielen aus HTML wird erklärt: * Bedeutung der Produktionen, * Verwendung von Grammatikkonstrukten, * Klassifikation in Block und Inline und Zusammenfassung zu Flow, * Tabellenstruktur, * Hinweis auf DTD für HTML beim W3C. -------------------------------------------------------------------------------- E EWS-3.26 HTML-Grammatik: Listen und Attribute Listen: List ::= quotesingle
    quotesingle ListElement+ quotesingle
quotesingle | quotesingle quotesingle ListElement ::= quotesingle
  • quotesingle Flow quotesingle
    • quotesingle Attribute in Anfangs-Tags. In dieser Grammatik werden Tags weiter zerlegt: AnfangsTag ::= quotesingle quotesingle Attribute ::= AttributeName quotesingle =quotesingle AttributeValue AttributeName ::= Identifier AttributeValue ::= StringLiteral | Identifier | Number | ... (c) 2003 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Einführung in Web-bezogene Sprachen WS 2006 / Folie 326 Ziele: HTML-Konstrukte an Grammatikregeln verstehen in der Vorlesung: An bekannten Beispielen aus HTML wird erklärt: * Bedeutung der Produktionen, * Verwendung von Grammatikkonstrukten, * Struktur von Listen in HTML, * Notation der Attribute in HTML. --------------------------------------------------------------------------------