GPS-2-1 2. Syntax Themen dieses Kapitels: * 2.1 Grundsymbole * 2.2 Kontext-freie Grammatiken * Schema für Ausdrucksgrammatiken * Erweiterte Notationen für kontext-freie Grammatiken * Entwurf einfacher Grammatiken * abstrakte Syntax * 2.3 XML (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 201 Ziele: Übersicht zu diesem Kapitel in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- GPS-2-2 2.1 Grundsymbole Grundsymbole: Programme bestehen aus einer Folge von Grundsymbolen. (Ebene (a) auf GPS-1-16) Jedes Grundsymbol ist eine Folge von Zeichen. Ihre Schreibweise wird z.B. durch reguläre Ausdrücke festgelegt. Grundsymbole sind die Terminalsymbole der konkreten Syntax. (Ebene (b) GPS-1-16) Folgende 4 Symbolklassen sind typisch für Grundsymbole von Programmiersprachen: Bezeichner, Wortsymbole, Literale, Spezialsymbole 1. Bezeichner (engl. identifier): zur Angabe von Namen, z. B. maximum findValue res_val _MIN2 Definition einer Schreibweise durch reg. Ausdruck: Buchstabe (Buchstabe | Ziffer)* 2. Wortsymbole (engl. keywords): kennzeichnen Sprachkonstrukte Schreibweise fest vorgegeben; meist wie Bezeichner, z. B.class static if for Dann müssen Bezeichner verschieden von Wortsymbolen sein. Nicht in PL/1; dort unterscheidet der Kontext zwischen Bezeichener und Wortsymbol: IF THEN THEN THEN = ELSE ELSE ELSE = THEN; Es gibt auch gekennzeichnete Wortsymbole, z.B. $begin (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 202 Ziele: Klassen und Schreibweisen von Grundsymbolen kennenlernen in der Vorlesung: * Grundsymbolklassen erläutern * Typische Schreibweisen erläutern * Beispiele aus Java, C, Pascal, FORTRAN Verständnisfragen: * Wie sind Bezeichner in Java definiert? -------------------------------------------------------------------------------- GPS-2-2a Literale und Spezialsymbole 2. Literale (engl. literals): Notation von Werten, z. B. ganze Zahlen: 7 077 0xFF Gleitpunktzahlen: 3.7e-5 0.3 Zeichen: quotesingle xquotesingle quotesingle \nquotesingle Zeichenreihen: "Hallo" Unterscheide Literal und sein Wert: "Sage \"Hallo\""und Sage "Hallo" verschiedene Literale - gleicher Wert: 63 077 0x3F Schreibweisen werden durch reguläre Ausdrücke festgelegt 4. Spezialsymbole (engl. separator, operator): Operatoren, Trenner von Sprachkonstrukten, z. B. ; , = * <= Schreibweise festgelegt, meist Folge von Sonderzeichen Bezeichner und Literale tragen außer der Klassenzugehörigkeit weitere Information: Identität des Bezeichners und Wert des Literals. Wortsymbole und Spezialsymbole stehen nur für sich selbst, tragen keine weitere Information. (c) 2009 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 202a Ziele: Klassen und Schreibweisen von Grundsymbolen kennenlernen in der Vorlesung: * Grundsymbolklassen erläutern * Typische Schreibweisen erläutern * Beispiele aus Java, C, Pascal, FORTRAN Verständnisfragen: * Erläutern Sie den Unterschied zwischen dem Literal für eine ganze Zahl und ihrem Wert. * Wie wird in Java das Berandungszeichen in Zeichen- oder Zeichenreihenliteralen dargestellt? * Welche Regeln gelten dafür in Pascal? -------------------------------------------------------------------------------- GPS-2-3 Trennung von Grundsymbolen In den meisten Sprachen haben die Zeichen Zwischenraum, Zeilenwechsel, Tabulator und Kommentare keine Bedeutung außer zur Trennung von Grundsymbolen; auch white space genannt. z. B. int pegel; statt intpegel; Ausnahme Fortran: Zwischenräume haben auch innerhalb von Grundsymbolen keine Bedeutung z. B. Zuweisung DO 5 I = 1.5 gleichbedeutend wie DO5I=1.5 aber Schleifenkopf DO 5 I = 1,5 In Fortran, Python, Occam können Anweisungen if (x < y) durch Zeilenwechsel getrennt werden. a = x In Occam und Python werden Anweisungen durch b = y gleiche Einrücktiefe zusammengefasst print (x) Häufigste Schreibweisen von Kommentaren: geklammert , z. B. int pegel; /* geklammerter Kommentar */ oder Zeilenkommentar bis zum Zeilenende, z. B. int pegel; // Zeilenkommentar Geschachtelte Kommentare z.B. in Modula-2: /* aeusserer /* innerer */ Kommentar */ (c) 2009 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 203 Ziele: Zeichen zwischen Grundsymbolen in der Vorlesung: Verständnisfragen: * Warum ist die Regel für Zwischenräume in Fortran problematisch? * Welche Schreibweisen für Kommentare gibt es in Modula-2? -------------------------------------------------------------------------------- GPS-2-4 2.2 Kontext-freie Grammatiken; Definition Kontext-freie Grammatik (KFG, engl. CFG): formaler Kalkül zur Definition von Sprachen und von Bäumen Die konkrete Syntax einer Programmiersprache oder anderen formalen Sprache wird durch eine KFG definiert. (Ebene b, GPS 1-16) Die Strukturbäume zur Repräsentation von Programmen in Übersetzern werden als abstrakte Syntax durch eine KFG definiert. Eine kontext-freie Grammatik G = (T, N, P, S) besteht aus: T Menge der Terminalsymbole Daraus bestehen Sätze der Sprache; Grundsymbole N Menge der Nichtterminalsymbole Daraus werden Sprachkonstrukte abgeleitet. S element N Startsymbol (auch Zielsymbol) Daraus werden Sätze abgeleitet. P reflexsubset N multiply V* Menge der Produktionen Regeln der Grammatik. außerdem wird V = T union Nals Vokabular definiert; T und N sind disjunkt Produktionen haben also die Form A ::= x, mit A element N und x element V* d.h. x ist eine evtl. leere Folge von Symbolen des Vokabulars. (c) 2009 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 204 Ziele: Kalkül kontext-freie Grammatik wiederholen in der Vorlesung: * Erläuterungen dazu am Beispiel der Ausdrucksgrammatik; * Grundsymbole sind die Terminalsymbole der konkreten Syntax; * KFG wird benutzt, um Programme zu schreiben und um existierende Programme zu strukturieren, prüfen, verstehen. nachlesen: Skript zu Modellierung, Kap. 5.1 Verständnisfragen: * Wie kann man aus der Menge der Produktionen die Mengen der Terminale, Nichtterminale und das Startsymbol bestimmen? -------------------------------------------------------------------------------- GPS-2-4a KFG Beispiel: Grammatik für arithmetische Ausdrücke GaA = (T, N, P, S) besteht aus: T Terminalsymbole { quotesingle (quotesingle , quotesingle )quotesingle , quotesingle +quotesingle , quotesingle -quotesingle , quotesingle *quotesingle , quotesingle /quotesingle , Ident } N Nichtterminalsymbole { Expr, Fact, Opd, AddOpr, MulOpr} S element N Startsymbol Expr P reflexsubset N multiply V* Produktionen P Menge der Produktionen: Häufig gibt man Produktionen Namen: p1: Expr ::= Expr AddOpr Fact p2: Expr ::= Fact p3: Fact ::= Fact MulOpr Opd p4: Fact ::= Opd Unbenannte Terminalsymbole p5: Opd ::= quotesingle (quotesingle Expr quotesingle )quotesingle kennzeichnen wir in Produktionen, p6: Opd ::= Ident z.B. quotesingle +quotesingle p7: AddOpr ::= quotesingle +quotesingle p8: AddOpr ::= quotesingle -quotesingle p9: MulOpr ::= quotesingle *quotesingle p10: MulOpr ::= quotesingle /quotesingle Es werden meist nur die Produktionen (und das Startsymbol) einer kontext-freien Grammatik angegeben, wenn sich die übrigen Eigenschaften daraus ergeben. (c) 2009 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 204a Ziele: Kalkül kontext-freie Grammatik wiederholen in der Vorlesung: * Erläuterungen dazu am Beispiel der Ausdrucksgrammatik; * Grundsymbole sind die Terminalsymbole der konkreten Syntax; * KFG wird benutzt, um Programme zu schreiben und um existierende Programme zu strukturieren, prüfen, verstehen. nachlesen: Skript zu Modellierung, Kap. 5.1 Verständnisfragen: * Wie kann man aus der Menge der Produktionen die Mengen der Terminale, Nichtterminale und das Startsymbol bestimmen? -------------------------------------------------------------------------------- GPS-2-5 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 u A v arrowdblright u x v z. B. Expr AddOpr Fact arrowdblright Expr AddOpr Fact MulOpr Opd mit Produktion p3 Beliebig viele Ableitungsschritte nacheinander angewandt heißen Ableitung: u arrowdblright * v Eine kontext-freie Grammatik definiert eine Sprache, d. h. die Menge von Terminalsymbolfolgen, die aus dem Startsymbol S ableitbar sind: L(G) = { w | w element T* und S arrowdblright * w } Die Grammatik aus GPS-2-4a definiert z. B. Ausdrücke als Sprachmenge: L(G) = { w | w element T* und Expr arrowdblright * w } { Ident, Ident + Ident, Ident + Ident * Ident } propersubset L(G) oder mit verschiedenen Bezeichnern für die Vorkommen des Grundsymbols Ident: { a, b + c, a + b * c } propersubset L(G) (c) 2009 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 205 Ziele: Das Prinzip der Ableitung verstehen in der Vorlesung: Erläuterungen am Beispiel der Ausdrucksgrammatik Übungsaufgaben: Verständnisfragen: * Geben Sie eine Ableitung zu a*b/c an. * Gibt es weitere zum selben Satz? Wie unterscheiden sie sich? * Geben Sie Folgen von Terminalsymbolen an, die nicht zur Sprache der Grammatik gehören. -------------------------------------------------------------------------------- GPS-2-6 Beispiel für eine Ableitung 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) 2006 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 206 Ziele: Ableitung wiederholen in der Vorlesung: Zusammenhang zum Ableitungsbaum zeigen nachlesen: Text -------------------------------------------------------------------------------- GPS-2-7 Ableitungsbäume Jede Ableitung kann man als Baum darstellen. Er definiert die Struktur des Satzes. Die Knoten repräsentieren Vorkommen von Terminalen und Nichtterminalen. Ein Ableitungsschritt mit einer Produktion wird dargestellt durch Kanten zwischen dem Knoten für das Symbol der linken und denen für die Symbole der rechten Seite der Produktion: Anwendung der Produktion p3: Expr Ableitungsbaum für p2 a * ( b + c ) Fact Fact p3 p3 Fact MulOpr Opd Fact MulOpr Opd p4 p9 p5 Opd * ( Expr ) p6 p1 Ident Expr AddOpr Fact a p2 p7 p4 Fact + Opd p4 p6 Opd Ident c p6 Ident b (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 207 Ziele: Ableitungsbäume verstehen in der Vorlesung: * Erläuterungen dazu * Beispiele für mehrdeutige Grammatiken Übungsaufgaben: Verständnisfragen: * Zeigen Sie an dem Satz a*b+c, dass der Ableitungsbaum wichtige Aussagen zur Struktur des Satzes enthält. -------------------------------------------------------------------------------- GPS-2-8 Mehrdeutige kontext-freie Grammatik Eine kontext-freie Grammatik ist genau dann mehrdeutig, wenn es einen Satz aus ihrer Sprache gibt, zu dem es zwei verschiedene Ableitungsbäume gibt. Beispiel für eine mehrdeutige KFG: Expr ::= Expr quotesingle -quotesingle Expr ein Satz, der 2 verschiedene Ableitungsbäume Expr ::= Number hat: Expr Expr Expr - Expr Expr - Expr Number Number Expr Expr - - Expr - - Expr Number Number Number Number a - b - c a - b - c (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 208 Ziele: Mehrdeutigkeit verstehen in der Vorlesung: * Definition wiederholen; * Beispiel erläutern; * ein Satz mit verschiedenen Ableitungsbäumen ist mehrdeutig; * zeigen, dass verschiedene Strukturen unterschiedliche Bedeutung haben können. Verständnisfragen: * Geben Sie andere mehrdeutige Sätze zu der Grammatik an. * Geben Sie Sätze zu der Grammatik an, die nicht mehrdeutig sind. * Geben Sie andere mehrdeutige Grammatiken an. -------------------------------------------------------------------------------- GPS-2-9 Ausdrucksgrammatik 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. Expr Name Produktion p1 p1: Expr ::= Expr AddOpr Fact Expr AddOpr p2: Expr ::= Fact Fact p2 p7 p3 p3: Fact ::= Fact MulOpr Opd Fact p4: Fact ::= Opd + Fact MulOpr Opd p5: Opd ::= quotesingle (quotesingle Expr quotesingle )quotesingle p4 p4 p9 p6 p6: Opd ::= Ident Opd Ident p7: AddOpr ::= quotesingle +quotesingle Opd * p6 p8: AddOpr ::= quotesingle -quotesingle p6 c Ident p9: MulOpr ::= quotesingle *quotesingle Ident a p10: MulOpr ::= quotesingle /quotesingle 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) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 209 Ziele: Systematische Struktur von Ausdrucksgrammatiken verstehen in der Vorlesung: * Erläuterungen dazu am Beispiel * Variation des Beispiels Übungsaufgaben: Geben Sie eine Ausdrucksgrammatik für die Java-Operatoren auf SWE-30 an. Verständnisfragen: * Wie sind die Operatoren in der Java-Grammatik definiert? * Wie ändert sich die Sprache, wenn Produktion p1 durch Expr ::= Fact '+' Fact ersetzt wird? Für welche Art von Operatoren wäre das sinnvoll? -------------------------------------------------------------------------------- GPS-2-10 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) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 210 Ziele: Schemata anwenden können in der Vorlesung: Erläuterungen dazu Übungsaufgaben: Anwenden der Schemata zur Konstruktion und zum Verstehen von Ausdrucksgrammatiken -------------------------------------------------------------------------------- GPS-2-11 Notationen für kontext-freie Grammatiken Eine kontext-freie Grammatik wurde 1959 erstmals zur Definition einer Programmiersprache (Algol 60) verwendet. Name für die Notation - noch heute: Backus Naur Form (BNF). Entweder werden Symbolnamen gekennzeichnet, z. B. durch Klammerung oder durch den Schrifttyp Expr. oder unbenannte Terminale, die für sich stehen, werden gekennzeichnet, z. B. quotesingle (quotesingle Zusammenfassung von Produktionen mit gleicher linker Seite: oder im Java -Manual: Opd ::= quotesingle (quotesingle Expr quotesingle )quotesingle Opd: | Ident ( Expr ) Ident (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 211 Ziele: Gebräuchliche Notationen kennenlernen in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- GPS-2-12 Erweiterte Notation EBNF Backus Naur Form (BNF) erweitert um Konstrukte regulärer Ausdrücke zu Extended BNF EBNF gleichbedeutende BNF-Produktionen X ::= u (v) w Klammerung X ::= u Y w Y ::= v X ::= u [v] w optional X ::= u Y w Y ::= v Y ::= epsilon X ::= u s* w optionale X ::= u Y w Y ::= s Y Y ::= epsilon X ::= u { s } w Wiederholung X ::= u s ... w Wiederholung X ::= u Y w Y ::= s Y Y ::= s X ::= u s+ w X ::= u (v || s) w Wdh. mit Trenner X ::= u Y w Y ::= v s Y Y ::= v X ::= u (v1 | v2) w Alternativen X ::= u Y w Y ::= v1 Y ::= v2 Dabei sind u, v, v1, v2, w element V* s element V X, Y element N Y ist ein Nichtterminal, das sonst nicht in der Grammatik vorkommt. Beispiele: Block ::= quotesingle {quotesingle Statement* quotesingle }quotesingle Block ::= quotesingle {quotesingle Y quotesingle }quotesingle Y ::= Statement Y Y ::= epsilon Decl ::= Type (Ident || quotesingle ,quotesingle ) quotesingle ;quotesingle Decl ::= Type Y quotesingle ;quotesingle Y ::= Ident quotesingle ,quotesingle Y Y ::= Ident (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 212 Ziele: EBNF kennenlernen in der Vorlesung: * Erläuterungen der EBNF Konstrukte * Transformation von EBNF in BNF nachlesen: ..., Abschnitt Verständnisfragen: * Welche EBNF-Notationen werden in der Java-Sprachspezifikation verwendet? -------------------------------------------------------------------------------- GPS-2-13 Syntaxdiagramme Expr: Ein Syntaxdiagramm repräsentiert eine EBNF-Produktion: + Expr Fact Expr ::= [ Expr ( quotesingle +quotesingle | quotesingle -quotesingle )] Fact Option und Alternative - Expr: Expr ::= (Fact || ( quotesingle +quotesingle | quotesingle -quotesingle )) Fact Wiederholung mit alternativem Trenner + Terminal: + - Nichtterminal: Fact (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 213 Ziele: Grafische Notation verstehen in der Vorlesung: * Erläuterungen dazu * Vergleich mit textuellen Produktionen nachlesen: siehe z. B. Pascal-Report Verständnisfragen: * Zeigen Sie die Zuordnung zwischen EBNF-Formen und Syntaxdiagrammen. -------------------------------------------------------------------------------- GPS-2-14 Produktionen-Schemata für Folgen Beschreibung Produktionen Sprachmenge nicht-leere Folge von b A ::= A b | b {b, bb, bbb, ...} nicht-leere Folge von b A ::= b A | b {b, bb, bbb, ...} evtl. leere Folge von b A ::= A b | {epsilon , b, bb, bbb, ...} evtl. leere Folge von b A ::= b A | {epsilon , b, bb, bbb, ...} nicht-leere Folge von b A ::= A t b | b {b, btb, btbtb, ...} getrennt durch t nicht-leere Folge von b A ::= b t A | b {b, btb, btbtb, ...} getrennt durch t (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 214 Ziele: Folgen konstruieren können in der Vorlesung: * Erläuterungen und Beispiele dazu nachlesen: ..., Abschnitt nachlesen: Übungsaufgaben: -------------------------------------------------------------------------------- GPS-2-14a Grammatik-Entwurf: Folgen Produktionen für Folgen von Sprachkonstrukten systematisch konstruieren. Schemata hier am Beispiel von Anweisungsfolgen (Stmts) Folgen mit Trenner: a. Stmts ::= Stmts quotesingle ;quotesingle Stmt | Stmt linksrekursiv b. Stmts ::= Stmt quotesingle ;quotesingle Stmts | Stmt rechtsrekursiv c. Stmts ::= ( Stmt || quotesingle ;quotesingle ) EBNF d. StmtsOpt::= Stmts | mit leerer Folge Folgen mit Terminator: a. Stmts ::= Stmt quotesingle ;quotesingle Stmts | Stmt quotesingle ;quotesingle rechtsrekursiv b. Stmts ::= Stmt Stmts | Stmt Terminator an den Elementen Stmt ::= Assign quotesingle ;quotesingle | ... c. Stmts ::= Stmts Stmt| Stmt linksrekursiv Stmt ::= Assign quotesingle ;quotesingle | ... d. Stmts ::= ( Stmt quotesingle ;quotesingle )+ EBNF (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 214a Ziele: Folgen konstruieren können in der Vorlesung: * Erläuterungen und Beispiele dazu nachlesen: ..., Abschnitt nachlesen: Übungsaufgaben: Geben Sie eine kontext-freie Grammatik für bedingte Anweisungen und für while-Schleifen an. -------------------------------------------------------------------------------- GPS-2-15 Grammatik-Entwurf: Klammern Klammern: Paar von Terminalen, das eine Unterstruktur einschließt: Operand ::= quotesingle (quotesingle Expression quotesingle )quotesingle Stmt ::= quotesingle whilequotesingle Expr quotesingle doquotesingle Stmts quotesingle endquotesingle Stmt ::= quotesingle whilequotesingle Expr quotesingle doquotesingle Stmts quotesingle endquotesingle MethodenDef ::= ErgebnisTyp MethodenName quotesingle (quotesingle FormaleParameter quotesingle )quotesingle Rumpf Stilregel: Öffnende und schließende Klammer immer in derselben Produktion gut : Stmt ::= quotesingle whilequotesingle Expr quotesingle doquotesingle Stmts quotesingle endquotesingle schlecht: Stmt ::= WhileKopf Stmts quotesingle endquotesingle WhileKopf ::= quotesingle whilequotesingle Expr quotesingle doquotesingle Nicht-geklammerte (offene) Konstrukte können Mehrdeutigkeiten verursachen: Stmt ::= quotesingle ifquotesingle Expr quotesingle thenquotesingle Stmt | quotesingle ifquotesingle Expr quotesingle thenquotesingle Stmts quotesingle elsequotesingle Stmt Offener, optionaler else-Teil verursacht Mehrdeutigkeit in C, C++, Pascal, sog. "dangling else"-Problem: if c then if d then S1 else S2 In diesen Sprachen gehört else S2 zur inneren if-Anweisung. Java enthält das gleiche if-Konstrukt. Die Grammatik vermeidet die Mehrdeutigkeit durch Produktionen, die die Bindung des else explizit machen. (c) 2014 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 215 Ziele: Mit Klammern umgehen können in der Vorlesung: * Erläuterungen und Beispiele dazu * Erläuterung des "dangling else" Verständnisfragen: * Zeigen Sie die Mehrdeutigkeit des "dangling else" an Ableitungsbäumen. -------------------------------------------------------------------------------- GPS-2-16 Abstrakte Syntax konkrete Syntax abstrakte Syntax KFG definiert KFG definiert Symbolfolgen (Programmtexte) und abstrakte Programmstruktur durch deren Ableitungsbäume Strukturbäume konkrete Syntax bestimmt die Struktur statische und dynamische Semantik von Programmkonstrukten, z. B. werden auf der abstrakten Syntax definiert Präzedenz und Assozitivität von Operatoren in Ausdrücken Präzedenzschemata benötigen Kettenproduktionen, d.h. Produktionen solche Kettenproduktionen sind hier mit genau einem Nichtterminal auf der überflüssig rechtenSeite: Expr ::= Fact Fact ::= Opd Opd ::= quotesingle (quotesingle Expr quotesingle )quotesingle Mehrdeutigkeit ist akzeptabel Mehrdeutigkeit ist problematisch Terminale, die nur für sich selbst stehen Alle Terminale sind nötig. und keine Information tragen, sind hier überflüssig (Wortsymbole, Spezial- symbole), z.B. class ( ) + - * / (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 216 Ziele: Prinzip der abstrakten Syntax verstehen in der Vorlesung: * KFG ausschließlich zur Definition von Bäumen. * Zusammenhang zur konkreten Syntax zeigen. * Beispiel auf der nächsten Folie erläutern. Verständnisfragen: * Geben Sie eine abstrakte Syntax zu den Anweisungsformen auf SWE-31 an. -------------------------------------------------------------------------------- GPS-2-17 Abstrakte Ausdrucksgrammatik konkrete Ausdrucksgrammatik abstrakte Ausdrucksgrammatik p1: Expr ::= Expr AddOpr Fact Name Produktion p2: Expr ::= Fact BinEx: Exp ::= Exp BinOpr Exp p3: Fact ::= Fact MulOpr Opd IdEx: Exp ::= Ident p4: Fact ::= Opd PlusOpr: BinOpr ::= p5: Opd ::= quotesingle (quotesingle Expr quotesingle )quotesingle MinusOpr: BinOpr ::= p6: Opd ::= Ident TimesOpr: BinOpr ::= p7: AddOpr ::= quotesingle +quotesingle DivOpr: BinOpr ::= p8: AddOpr ::= quotesingle -quotesingle p9: MulOpr ::= quotesingle *quotesingle p10: MulOpr ::= quotesingle /quotesingle Strukturbaum für a * (b + c) Abbildung Exp BinEx konkret -> abstrakt Exp BinOpr Exp Expr,Fact,Opd -> Exp IdEx AddOpr,MulOpr -> BinOpr TimesOpr BinEx p1,p3 -> BinEx Ident Exp BinOpr Exp p2,p4,p5 -> IdEx PlusOpr IdEx p6 -> IdEx Ident Ident p7 -> PlusOpr a * b + c ... (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 217 Ziele: Beispiel zur vorigen Folie in der Vorlesung: * Bezüge zwischen konkreten und abstrakten Produktionen und Nichtterminalen zeigen; * Strukturbaum und Ableitungsbaum vergleichen. -------------------------------------------------------------------------------- GPS-2.19 2.3 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 * Weitere aus XML abgeleitete Sprachen: SVG, MathML, SMIL, RDF, WML * individuelle XML-Sprachen werden benutzt, 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) 2009 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 219 Ziele: Rolle von XML verstehen in der Vorlesung: Die Aspekte werden einführend erklärt. -------------------------------------------------------------------------------- GPS-2.19a 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) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 219a Ziele: Prinzipien der XML-Notation in der Vorlesung: Kurze Erklärung der Prinzipien. -------------------------------------------------------------------------------- S GPS-2.20 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) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 220 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!! -------------------------------------------------------------------------------- GPS-2.21 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 Die neuesten Produktnachrichten: Die Firma Fridolin Soft hat eine neue Version des beliebten Ballerspiels HitYourStick herausgebracht. Nach Angaben des Herstellers soll die neue Version, die nun auch auf dem Betriebssystem Ganzfix läuft, um die 80 Dollar kosten. Von Ripfiles Inc. gibt es ein Patch zu der Sammel-CD Best of other people's ideas. Einige der tollen Webseiten-Templates der CD enthielten bekanntlich noch versehentlich nicht gelöschte Angaben der Original-Autoren. Das Patch ist für schlappe 200 Euro zu haben. (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 221 Ziele: Technische Angaben sehen in der Vorlesung: Am Beispiel wird erklärt: * die 3 technischen Angaben, * Text-Dokument als Beispiel. * Beispiel wird noch weiterverwendet. -------------------------------------------------------------------------------- GPS-2.22 Baumdarstellung von XML-Texten Jeder XML-Text ist durch Tag-Paare vollständig geklammert (wenn er well-formed ist). Deshalb kann er eindeutig als Baum dargestellt werden. (Attribute betrachten wir noch 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) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 222 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 -------------------------------------------------------------------------------- GPS-2.23 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) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 223 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. -------------------------------------------------------------------------------- GPS-2.24 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: X (Y)+ nicht-leere Folge X (A | B) Alternative X (A)? Option X EMPTY leeres Element (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 224 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. -------------------------------------------------------------------------------- GPS-2-31 Zusammenfassung zu Kapitel 2 Mit den Vorlesungen und Übungen zu Kapitel 2 sollen Sie nun Folgendes können: * Notation und Rolle der Grundsymbole kennen. * Kontext-freie Grammatiken für praktische Sprachen lesen und verstehen. * Kontext-freie Grammatiken für einfache Strukturen selbst entwerfen. * Schemata für Ausdrucksgrammatiken, Folgen und Anweisungsformen anwenden können. * EBNF sinnvoll einsetzen können. * Abstrakte Syntax als Definition von Strukturbäumen verstehen. * XML als Meta-Sprache zur Beschreibung von Bäumen verstehen * DTD von XML als kontext-freie Grammatik verstehen * XML lesen können (c) 2005 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Grundlagen der Programmiersprachen SS 2014 / Folie 231 Ziele: Ziele des Kapitels erkennen in der Vorlesung: Erläuterungen dazu --------------------------------------------------------------------------------