Aus: Ausdruck

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

Download Report