close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Kapitel 2: Spezifikation, Algorithmus, form. Sprache Teil 1 - Lehrstuhl

EinbettenHerunterladen
Wo stehen wir?
Dr. Lars Hildebrand
Gliederung
`
`
`
`
`
Stationen im Entwurf von Algs und Progs
Wie geht es weiter
Spezifikation
Algorithmus
Formale Sprache
Ð Grammatik
Ð Syntaxdiagramm
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
26
Formale Sprachen
Dr. Lars Hildebrand
Einführung in die Beschreibung Formaler Sprachen mittels
(kontextfreier) Grammatiken
` Ziel:
Ð Beschreibung von (Teilen von) syntaktisch korrekten Programmen
(über [speziell dargestellte] kontextfreie Grammatiken).
` Zu obigem Ziel nötig:
Ð Sei A = {a1, a2, ....., an} eine endliche Menge von Zeichen (Alphabet).
– Beispiel: A1:= {0,1,2}
– Vorsicht: Zeichen eines Alphabets können selbst zusammengesetzt
sein!
Ð Sei A* die Menge aller endlichen Wörter über dem Alphabet A.
– Am Beispiel: A1* := {0, 1, 2, 00, 01, 02, 10, ...., 000, 001, 002,...,
100, .., 0000,..}
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
27
Formale Sprachen
Dr. Lars Hildebrand
Einführung in die Beschreibung Formaler Sprachen mittels
(kontextfreier) Grammatiken
` Das Hintereinanderhängen von Zeichen wird häufig -wie auch
hier- ohne ein explizites Operatorzeichen, also allein durch das
Hintereinanderschreiben von links nach rechts ausgedrückt.
` Länge eines Wortes aus A*: Anzahl der vorhandenen
Zeichen/Buchstaben unter Berücksichtigung der Vielfachheit
des Vorkommens.
` Man nimmt auch das sog. "leere" Wort der Länge 0, z. B häufig
bezeichnet durch ε, hinzu!
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
28
Formale Sprachen
Dr. Lars Hildebrand
Einführung in die Beschreibung Formaler Sprachen
mittels (kontextfreier) Grammatiken
` Aufgabe:
Ð Zu einem gegebenen Alphabet A (Menge von Zeichen)
beschreibe eine geeignete Teilmenge von A* in möglichst
kompakter Form.
Ð Beispiel:
– Sei L1(A1*):
– Menge aller Wörter, die mit einer 1 beginnen und einer
1 enden, sonst aber keine 1 mehr aufweisen.
Ð Kompakte Darstellung?
– Beispiele von Wörtern aus L1(A1*): 11, 1001, 12002021
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
29
Formale Sprachen
Dr. Lars Hildebrand
Einführung in die Beschreibung Formaler Sprachen mittels
(kontextfreier) Grammatiken
` Eine Lösung:
Ð Eine (kontextfreie) Grammatik G beschreibt eine
ausgezeichnete Teilmenge der Menge aller Zeichenketten
über einem gegebenen Alphabet (den Terminalzeichen T).
Ð Dies geschieht durch einen Erzeugungsprozess.
Ð Die durch diesen Erzeugungsprozess eindeutig festgelegte
Teilmenge von T*: L(G) heißt "Sprache" von G.
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
30
Formale Sprachen
Dr. Lars Hildebrand
Einführung in die Beschreibung Formaler Sprachen mittels
(kontextfreier) Grammatiken
` Darstellung der Grammatik:
Ð Als 4-Tupel G = (V, T, P, S) aus
– endlicher Menge von Nichtterminalzeichen (V),
– endlicher Menge von Terminalzeichen (T),
– endlicher Menge von Produktionen/Regeln (P) und
– Startsymbol (S).
– Randbedingung: V ∩ T = ∅
` Hilfsgrößen:
Ð sog. Nichtterminale auch syntaktische Variable, daher V:
Stellen "Zwischengrößen" dar, die durch weitere Anwendung von
Regeln (im Endeffekt) in Wörter über Terminalzeichen überführt
werden. Wie? Vgl. unten.
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
31
Formale Sprachen
Dr. Lars Hildebrand
Einführung in die Beschreibung Formaler Sprachen mittels
(kontextfreier) Grammatiken
` Regeln (Produktionen):
Ð Allgemeiner Aufbau einer Regel
Linke Seite → Rechte Seite
– Linke Seite wird durch genau ein Nichtterminalzeichen
gebildet.
– Beispiel: Bezeichner1
– Rechte Seite: i. a. Wort über (V ∪ T), d.h. ∈ (V ∪ T)*.
Ð Später werden zusätzliche Sonderzeichen erlaubt.
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
32
Formale Sprachen
Dr. Lars Hildebrand
Einführung in die Beschreibung Formaler Sprachen mittels
(kontextfreier) Grammatiken
` Eine Regel
Ð beschreibt die Überführung von Nichtterminalzeichen
(dargestellt auf der linken Seite vom Pfeil) in Wörter aus
Terminal- und/oder Nichtterminalzeichen.
` Startsymbol
Ð stellt das Nichtterminalzeichen dar, von dem aus sog.
Ableitungen gestartet werden.
Zu Ableitungen später nach Einführung eines Beispiels.
` Kommentare
Ð wollen wir (u.a.) durch /*... */ notieren.
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
33
Formale Sprachen
Dr. Lars Hildebrand
Beispiel
` Nichterminalzeichen
Ð V ={ Ausdruck, Summand, Faktor, Funktion, Zahl }
` Terminazeichen
Ð T ={ „0“, „1“, „2“, „3“, „4“, „5“, „6“, „7“, „8“, „9“, „+“, „-“, „*“,
„kgV“, „(“ , „)“, „ , “ }
„ggT“,
` Produktionen
Ð P ={Ausdruck → Summand,
Ð Ausdruck → Summand „+“ Ausdruck, Ausdruck → Summand „-“ Ausdruck,
Ð Summand → Faktor, Summand → Faktor „*“ Faktor,
Ð Faktor → Zahl,
Ð Faktor → „ggT“ „(“ Ausdruck „ , “ Ausdruck „)“ ,
Ð Faktor → „kgV“ „(“ Ausdruck „ , “ Ausdruck „)“ ,
Ð Zahl → „0“,... , Zahl → „9“, Zahl → Zahl Zahl }
` Startsymbol
Ð S = Ausdruck
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
34
Formale Sprachen
Dr. Lars Hildebrand
Grammatik ist Erzeugendensystem
` G =(V,T,P,S)
` L(G) = {w ∈ T* : ∃ w1, ... , wk ∈ (V ∪ T)*:
S →P w1, w1 →P w2, ... , wk →P w}
` mit
wi →P wj :
aus dem Wort wi wird wj mit Hilfe einer Regel aus P
` d.h. sukzessive wird aus dem Startsymbol ein Wort abgeleitet,
das nur noch Terminalsymbole enthält.
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
35
Formale Sprachen
Dr. Lars Hildebrand
Beispiel zur Erzeugung eines Ausdrucks
`
`
`
`
`
`
`
`
`
`
Ausdruck
Summand + Ausdruck
Faktor + Ausdruck
Faktor + Summand
Faktor + Faktor
Zahl + Faktor
Zahl + kgV(Ausdruck,Ausdruck)
Zahl Zahl + kgV(Ausdruck,Ausdruck)
2 Zahl + kgV(Ausdruck,Ausdruck)
2 2 + kgV(Ausdruck,Ausdruck)
Startsymbol
Regel 2
Regel 4
Regel 1
Regel 4
Regel 6
Regel 8
Regel 10
Regel 9
Regel 9
PIWIN I Kap. 2 Spezifikation – Algorithmus – Formale Sprache
36
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
Document
Kategorie
Seele and Geist
Seitenansichten
1
Dateigröße
136 KB
Tags
1/--Seiten
melden