Transcript
Formale Sprachen
Dr. Lars Hildebrand
Grafische Darstellung des Ableitungsprozesses Ausdruck Ausdruck -> Summand + Ausdruck
Ausdruck Summand + Ausdruck
Summand
` Summand -> Faktor
Ausdruck
Ausdruck
Faktor + Ausdruck
Summand
heißt Ableitungsbaum
+
+
Ausdruck
Faktor (©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
37
Formale Sprachen
Dr. Lars Hildebrand
Ableitungsbaum zu 22+kgV(4*5,18-3)
(©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
38
Erweiterte Backus-Naur Form (EBNF)
Dr. Lars Hildebrand
` Erweiterte Backus-Naur Form (EBNF)
Anmerkung: Das funktioniert nur für kontextfreie Grammatiken (©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
39
Regel(teil)menge in EBNF
Dr. Lars Hildebrand
Aus: Ausdruck → Summand, Ausdruck → Summand ”+” Ausdruck, Ausdruck → Summand ”-” Ausdruck wird: Ausdruck = Summand [ ( ”+” ⎜ ”-” ) Ausdruck ] ` Beachte Ð die Zeichen in rot sind so genannte Ð Meta-Zeichen/Meta-Symbole (=,(,) ,|, [,] ,{,}) (©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
40
Beispielgrammatik in EBNF
Dr. Lars Hildebrand
Insgesamt wird damit „unsere“ Grammatik für arithmetische Ausdrücke zu einem Dreizeiler: 1. Ausdruck = Summand [ ( ”+” ⎜ ”-” ) Ausdruck ] 2. Summand = Faktor [ ”*” Faktor ] 3. Faktor
= ({ ( ”0” ⎜ ”1” ⎜ ... ⎜ ”9” ) }1 ⎜ ( ”ggT” ⎜ ”kgV” ) ”(” Ausdruck ”,” Ausdruck ”)”)
(©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
41
Syntaxdiagramme
Dr. Lars Hildebrand
als grafische Alternative zur EBNF ` bestehen aus Ð zwei unterschiedlichen Arten von Kästen – rund = Terminal und – eckig = Nonterminal und Ð Pfeilen, die diese Kästen miteinander verbinden
(©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
42
Darstellung von Regel(teil)mengen
Dr. Lars Hildebrand
Nonterminal: enthält Anfang und Ende Namen eines Diagramms Name des Diagramms
Terminal: enthält das Zeichen selbst Beim Durchlaufen durch ein Diagramm entlang der Pfeile werden an den Terminal-Kästen Zeichen aufgesammelt und bei Nonterminal-Kästen zu dem angegebenen Diagramm verzweigt. (©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
43
Die gesamte Regelmenge
Dr. Lars Hildebrand
dargestellt über Syntaxdiagramme (ohne Summanden)
(©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
44
Einsatz von Grammatiken
Dr. Lars Hildebrand
` Nicht nur für die Struktur und den Aufbau von Programmiersprachen ` Eingabesprachen von Programmen Ð Kommando-Sprachen Ð Datendefinitionssprachen Ð Kassenterminals Ð ... ` Kommunikationsprotokolle Ð TCP/IP Ð SMTP Ð ... ` ... (©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
45
Bemerkung zur Semantik
Dr. Lars Hildebrand
Die Informatik benutzt üblicherweise drei Möglichkeiten, die Bedeutung einer formalen Sprache (hier Programmiersprache) zu beschreiben.
` operational ` denotational ` verbal
(©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
46
Operationale Semantik
Dr. Lars Hildebrand
` Die operationale Methode definiert schrittweise die Wirkung von Elementaroperationen Ð Beschreibe elementweise, wie die Elementaroperationen in den verschiedenen Situationen ausgeführt werden Ð D.h. man unterscheidet – die Elementaroperationen und – Programmsituationen
Ð Beides zusammen definiert, wie ein Programm schrittweise ausgeführt wird. ` Auf dieser Basis werden Softwareentwicklungswerkzeuge (Compiler) hergestellt.
(©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
47
Denotational Semantik
Dr. Lars Hildebrand
` Die denotationale Methode definiert die Wirkung von Programmen durch eine mathematische Funktion: Ð Die Wirkung (= Bedeutung) eines Programms wird durch die Veränderung von Zuständen beschrieben Ð Programm : Zustand, Eingabe → Zustand
` Auf dieser Basis werden formale Korrektheitsbeweise (tut ein Programm das, was es soll?) geführt.
(©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
48
Verbal Semantik
Dr. Lars Hildebrand
` Die verbale Methode definiert die Wirkung von Programmen durch eine präzise verbale Erklärung Ð Die Wirkung (= Bedeutung) eines Programms wird durch die verbale Beschreibung der einzelnen Sprachelemente der betrachteten Programmiersprache geliefert. Ð Java: Die so genannte Java Language Reference Ð ist eher ein technisches Dokument ... gedacht als Nachschlagewerk für Hersteller von Softwareentwicklungswerkzeugen ` Auf dieser Basis wird die Programmiersprache Java hier in der Vorlesung eingeführt (©M. Goedicke, UGH Essen)
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
49
Wo stehen wir jetzt?
Dr. Lars Hildebrand
` Ziel demnächst: Ð Betrachtung wesentlicher Sprachkonstrukte imperativer Programme. ` Rückblick: Ð Spezifikationsbegriff: Was sind die Eigenschaften einer Problem-/ Aufgabenbeschreibung Ð Algorithmusbegriff: Was sind die Eigenschaften automatischer Verfahrensvorschriften Ð Grammatiken: Wie können künstliche Sprachen definiert werden ` Nächster Schritt: Ð Basiskonstrukte imperativer & objektorientierter Programmierung – Zuweisung und Datentypen – Sequenz – Fallunterscheidung, Alternative – Iteration – Verfeinerung, Unterprogrammaufrufe, Prozedur – Funktion und Rekursion
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
50
