Embed Size (px)
Citation preview
Theorie der Programmiersprachen
© Günter RiedewaldDie Folien sind eine Ergänzung der Vorlesung und nur für den internen
Gebrauch konzipiert.
Motivation
Eines der fundamentalen Probleme der Informatik ist die Beziehung Syntax-Semantik
In der Vorlesung wird dieses Problem für Programmiersprachen behandelt, da
- Programmiersprachen mit am besten erforscht sind
- und eine wichtige praktische Bedeutung als Werkzeug der Softwareentwicklung haben
Beziehung Syntax-SemantikBeispiele
Nachricht Interpretation Information
Zeichenkette ohne Bedeutung
a + z Addition zweier Operanden vom gleichen Typ
Nachricht an Objekt a mit Methode + und Parameter z
ADT zur Beschreibung von Datenstrukturen:
Signatur beschreibt Struktur (über Terme)
Termgleichungen beschreiben Eigenschaften der Operationen; Termersetzungsregeln beschreiben Ausführung der Operationen
Verifikation:
Verallgemeinerte Formel {Q} p {R}
Q, R Formeln; p Programmstück
Bedeutung (durch Interpretation):
Wenn Q gilt und p terminiert, dann gilt auch R. (Partielle Korrektheit)
TGI: regulärer Ausdruck reguläre Sprache
Beispiel:
a.b Verkettung der regulären Ausdrücke a und b
L(a.b) = L(a).L(b) zu a.b zugeordnete Sprache
Programmiersprachen als Werkzeug der Softwareentwicklung
Programmiersprachen sind für unterschiedliche
Einsatzgebiete unterschiedlich gut geeignet
Weiterentwicklung der Softwaretechnik
erfordert neue Programmiersprachen
ständig neuer Bedarf an Compilern/ Interpretern
Notwendigkeit der schnellen und effizienten Entwicklung von Compilern/ Interpretern (Automatisierung!)
Möglichkeiten der Beschreibung von Programmiersprachen
In natürlicher Sprache:
+ (scheinbare) schnelle Verständlichkeit
- Missverständnisse wegen Mehrdeutigkeit der natürlichen Sprachen Compiler realisieren unterschiedliche Sprachvarianten
- Keine Möglichkeit der Verifikation von Compilern und Programmen
Formalisierte Beschreibung:
- Anspruchsvolles Kenntnisniveau der Anwender bzgl. Theorie
+ Nachteile der Beschreibung in natürlicher Sprache verschwinden
+ Möglichkeit der automatisierten Erstellung von Compilern (Basis: Grammatiken, Automaten)
Pragmatisches Vorgehen:
Gegeben: universelle Programmiersprache P mit Compiler
Zu definieren: Spezialsprache S mit Compiler
Voraussetzung: P und S seien verwandt
a) S als Untersprache von P (unter Nutzung von Typkonzept, Prozedurkonzept, Operatorkonzept,...) kein neuer Compiler
b) S als Erweiterung von P:
- Makroerweiterung: neue Konstrukte von S werden durch Makros in P beschrieben
Makrogenerator und Compiler von P
- Präcompilerkonzept: neue Konstrukte von S werden als Kombinationen von Konstrukten aus P definiert
Präcompiler und Compiler von P
Programm in S
Präcompiler
Programm in P
Compiler für P
Programm in
Zielcode
Literatur
R. Cezzar: A Guide to Programming Languages
Overview and Comparison, ARTECH HOUSE,Inc.,1995
E. Fehr: Semantik von Programmiersprachen,
Studienreihe Informatik, Springer-Verlag, 1989
R. A. Finkel: Advanced Programming Language Design,
Addison-Wesley, 1996
M.J.C. Gordon: The Denotational Description of
Programming Languages - An Introduction,
Springer-Verlag, 1979
C.A. Gunter: Semantics of Programming Languages
Structures and Techniques, The MIT Press, 1993
B. Kirkerud: Programming Language Semantics
Imperative and Object Oriented Languages,
International Thomson Computer Press, 1997
K.C. Louden: Programmiersprachen
Grundlagen, Konzepte, Entwurf
International Thompson Publ., 1994
M.E. Majster: A Unified View of Semantics
Technical Report TR 79-394, Dept. of Comp. Sc.,
Cornell University
M. Marcotty, H.F. Ledgard, G.V. Bochmann: A Sampler
of Formal Definitions, ACM Computing Surveys
8,2(1976), 191-276
P.D. Mosses: Action Semantics
Cambridge University Press, 1992
H.R. Nielson, F. Nielson: Semantics with Applications
A Formal Introduction, John Wiley & Sons, 1992
F.G. Pagan: Formal Specification of Programming
Languages: A Panoramic Primer
Prentice-Hall, 1981
G. Riedewald, J. Maluszynski, P. Dembinski: Formale
Beschreibung von Programmiersprachen
Eine Einführung in die Semantik, Akademie-Verlag
Berlin, Oldenbourg Verlag München, 1983
R.W. Sebesta: Concepts of Programming Languages
Addison-Wesley, 5. Auflage, 2002
K. Slonneger, B.L. Kurtz: Formal Syntax and Semantics
of Programming Languages
A Laboratory Based Approach
Addison-Wesley Publ. Company, 1995
G. Winskel: The Formal Semantics of Programming
Languages
An Introduction
The MIT Press, 1993
Theorie der Programmiersprachen1 Einleitung
Komponenten einer Programmiersprache: Syntax: Beschreibung von Struktur und
Aussehen der Sprachkonstrukte (Syntaxbaum und Programmrepräsentation)
Semantik: Beschreibung der Bedeutungen der Sprachkonstrukte bzgl. eines bestimmten Bedeutungsraums
Bauer/Goos: Bedeutung eines Programms als Funktion seines Syntaxbaums
F. L. Bauer, G. Goos in Informatik, II. Teil, Springer, 1971:
Ein Wort aus dem Sprachschatz einer formalen Sprache trägt verschlüsselt in sich den zugehörigen Strukturbaum, den die syntaktische Analyse freilegt. Was durch das Wort an Bedeutung übermittelt wird, muss eine Funktion des Strukturbaums sein. Damit ergibt sich die Forderung, dass die Syntax einer bedeutungstragenden Sprache bedeutungstreu sein muss: sie muss es erlauben, an das Skelett der syntaktischen Struktur unter allen Umständen das Fleisch der Semantik hängen zu können.
Fragen:
- Welche Bedeutungsräume kommen in Frage?
- Wie ist diese Funktion zu definieren? Pragmatik: gibt die Beziehungen der Sprache
zur Umwelt (Nutzer, Rechner, Betriebssystem,...) an erscheint nicht explizit in der Sprachdefinition („nicht weiter definiert“)
Frage: Wozu gehören Kontextbedingungen einer Programmiersprache?
statische Semantik
Pragmatik in einer Prolog III-Definition:
The boolean and arithmetical operations have their usual mathematical meaning. Rational numbers are represented in the machine in perfect precision, i.e., with as many digits as is required to express them exactly. Of course this is subject to the condition that this must not exceed your computer´s memory capacity.
Beschreibungsmittel für Sprachkomponenten: Syntax: kontextfreie Grammatiken in
verschiedenen Ausprägungen (Syntaxdiagramme, BNF, EBNF, van Wijngaarden-Notation,...)
Existenz von nichtdeterministischen Kellerautomaten zur Spracherkennung (syntaktische Analyse in Compilern)
Semantik:
- verbal
- halbformal durch Aktionen eines hypothetischen Rechners
- indirekt durch Compiler/Interpreter – Translationssemantik
- mathematische Beschreibungsmittel (streng formal)
- Selbstdefinition: Semantik der Sprache wird in der Sprache selbst beschrieben
2 Konkrete und abstrakte Syntax2.1 Ergänzungen zu kontextfreien Sprachen
Ergänzung zu Syntaxbäumen
Beispiel: kontextfreie Grammatikprog: <Programm> ::=
begin <Vereinbarungen>;<Anweisungen> end
verein1: <Vereinbarungen> ::= <Vereinbarung>
verein2: <Vereinbarungen> ::= <Vereinbarung>;<Vereinbarungen>
ver: <Vereinbarung> ::= <Typ> <Identifikator>
typi: <Typ> ::= int
typb: <Typ> ::= bool
idx: <Identifikator> ::= x
idy: <Identifikator> ::= y
anweis1: <Anweisungen> ::= <Anweisung>
anweis2: <Anweisungen> ::= <Anweisung>;<Anweisungen>
anweis: <Anweisung> ::= A
Syntaxbäume von begin int x; A end
in linearer Darstellung: Programm(begin
Vereinbarungen(Vereinbarung(Typ(int) Identifikator(x))) ;
Anweisungen(Anweisung(A)) end)
Kantorovič-Schreibweise:
prog(verein1(ver(typi, idx)), anweis1(anw))
oder als Kantorovič-Baum
prog
verein1 anweis1
ver anw
typi idx
Gewöhnliche grafische Darstellung:
Programm
begin end
Vereinbarungen ; Anweisungen
Vereinbarung Anweisung
Typ Identifikator A
int x
Gewöhnliche grafische Darstellung mit Regelbezeichnungen:
Programm
begin prog end
Vereinbarungen ; Anweisungen
verein1 anweis1Vereinbarung Anweisung
ver anwTyp Identifikator A
typi idxint x
Kontextfreie GrammatikAlgebraische Betrachtung
Vorgehensweise: Nichtterminale werden als Sorten verwendet Syntaxregeln werden als syntaktische
Operationen aufgefasst, die Sprachkonstrukte zu komplexeren Konstrukten zusammensetzen Verwendung von Regelbezeichnungen als Operationssymbole
Beispiel: Signatur der obigen Grammatik
Programm
progVereinbarungen Anweisungen
verein1 verein2 anweis1 anweis2
Vereinbarung Anweisung
verTyp Identifikator anw
typi typb idx idy
Bemerkungen: Durch die algebraische Betrachtungsweise
wird von der konkreten Programmrepräsentation abstrahiert.
Ableitbare Terme sind Syntaxbäume in Kantorovič-Schreibweise.
Um Programmeigenschaften festzulegen müssen zusätzlich Termgleichungen definiert werden.
Über Algebren können z.B. konkrete Programmrepräsentationen oder konkrete Syntaxbäume definiert werden.
Beispiel:
a) - Zuordnung einer Trägermenge
MX = {w|X + w, w T*}
zu einem Nichtterminal X
Z.B.: <Programm> {w|<Programm> + w, w T*}
- Zuordnung einer typisierten Verkettungsoperation oa : MX1x...xMXn MX
zum Operationssymbol o: X1x...xXn X
Z.B. prog: Vereinbarungen x Anweisungen Programm
proga: Mvereinbarungen x MAnweisungen MProgramm
Dabei gilt:
proga(x, y) = begin x; y end ,
x Mvereinbarungen, y Manweisungen
b) - Zuordnung der Menge aller Syntaxbäume mit der Wurzel X zum Nichtterminal X
- Zuordnung von typisierten Verkettungen von Syntaxbäumen als Operationen zu den entsprechenden Operationssymbolen
Substitution kontextfreier Sprachen
Beispiel:
Beschreibung der Grobstruktur von Zahlen:
L = {s dn k dm|n > 0, m 0}, s Vorzeichen,
k Trennzeichen, d Ziffer,
T = {s, d, k} Alphabet
Verfeinerung zu Dezimalzahlen mit Vorzeichen:
Ls = {+,-} Ld = {0, 1,..., 9} Lk = {,} werden in L „eingesetzt“
L´ Menge aller Dezimalzahlen
Verfeinerung zu Binärzahlen mit Vorzeichen:
Ls = {+,-} Ld = {0, 1} Lk = {.}
L´ Menge aller Binärzahlen
Substitution kontextfreier Sprachen:
Gegeben:- Kontextfreie Sprache L (zu verfeinernde Sprache)
über einem Alphabet T
- {Lt}tT Familie kontextfreier Sprachen Lt über einem Alphabet T´ (Verfeinerung)
Substitutionssprache L´ (verfeinerte Sprache):
x1...xn L´ t1...tn L, ti T, xi Lti
2.2 Beschreibungsmittel kontextfreier Sprachen
Backus-Naur-Form (BNF)
Syntaxbeschreibung durch endliche Menge von Metaregeln:
Metavariable: in spitze Klammern eingeschlossene Folge von Schriftzeichen
Metakonstante: spezielle Schriftzeichenfolge Metaregel: Metavariable gefolgt von ::= mit
anschließender Folge aus Metavariablen oder Metakonstanten
Zusammenfassung von Metaregeln mit gleicher linker Seite:
<V> ::= 1 , ... , <V> ::= n
<V> ::= 1|...| n (*)
Interpretation einer Menge von Metaregeln (*): Metavariable: Unbekannte in einem
Mengengleichungssystem; gesuchter Wert ist eine Sprache
Metakonstante: Bestandteil von Worten Metaregel: Mengengleichung, wobei (*) bedeutet
Die V zugehörige Sprache ist eine Vereinigung der den i zugehörigen Sprachen
Beispiel:BNF-Regeln:
<Identifikator> ::= <Buchstabe>| <Identifikator><Buchstabe>|<Identifikator><Ziffer>
<Buchstabe> ::= A|...|Z
<Ziffer> ::= 0|1|...|9
Mengengleichungssystem:
I = B I.B I.Z
B = {A,..., Z}, Z ={0, 1,...,9}
Gesucht: L(<Identifikator>) = I
Fragen: Wann hat das System eine Lösung? Wie viel Lösungen existieren? Welche Lösungsalgorithmen gibt es?
Algorithmus:
Beginnend mit einem Startwert berechne eine Folge von Näherungen bis zur „Konvergenz“.
Hier: Startwert: I0 = n-te Näherung: In ist die Menge aller
Zeichenfolgen beginnend mit Buchstaben und mit nachfolgend maximal (n-1) Buchstaben oder Ziffern
Lösung: I = B.(B Z)*
Bemerkung:
Die Lösungssprachen eines durch eine BNF
definierten Gleichungssystems sind kontextfreie
Sprachen.
Metaregeln entsprechen kontextfreien Syntaxregeln:
Metavariablen entsprechen Nichtterminalen Metakonstante sind mit Terminalen
gleichzusetzen.
Eine BNF kann einer kontextfreien Grammatik gleichgesetzt werden.
Kontextfreie Grammatik der Beispielprogrammiersprache BPS
Grundversion
1 <Programm> ::= begin <Vereinbarungen> ; <Anweisungen> end
2 <Vereinbarungen> ::= <Vereinbarung>| <Vereinbarung> ; <Vereinbarungen>
3 <Vereinbarung> ::= <Typ> <Identifikator>
4 <Typ> ::= int|bool
5 <Anweisungen> ::= <Anweisung>|
<Anweisung> ; <Anweisungen>
6 <Anweisung> ::= skip|
<Variable> := <Ausdruck>|
if <Ausdruck> then <Anweisungen>
else <Anweisungen>
fi|
while <Ausdruck> do <Anweisungen> od|
read <Variable>|
write <Ausdruck>
7 <Ausdruck> ::= <Konstante>| <Variable>|
(<op1> <Ausdruck>)|
(<Ausdruck> <op2> <Ausdruck>)
8 <Variable> ::= <Identifikator>
9 <Konstante> ::= <log. Konstante>|
<arith. Konstante>
10 <log. Konstante> ::= true|false
11 <arith. Konstante> ::= + <Zahl>|- <Zahl>|<Zahl>
12 <Zahl> ::= <Ziffer>|<Zahl><Ziffer>
13 <Ziffer> ::= 0|1|...|9
14 <op1> ::= +|-|not
15 <op2> ::= +|-|/|*|=|||||||and|or
16 <Identifikator> ::= <Buchstabe>| <Identifikator><Buchstabe>|<Identifikator><Ziffer>
17 <Buchstabe> ::= a|b|...|z
Ausgewählte Kontextbedingungen
- Jede in einem Ausdruck oder einer Anweisung auftretende Variable muss im gleichen Programm vereinbart sein.
- Jede Variable darf höchstens einmal vereinbart sein.
- In einer Wertzuweisung müssen die Typen der Variablen auf der linken Seite und des Ausdrucks auf der rechten Seite übereinstimmen.
- Die Typen der Operanden eines dyadischen (zweistelligen) Ausdrucks müssen übereinstimmen.
- ...
Spracherweiterungen
18 <Anweisung> ::= <Block>
19 <Block> ::=
begin <Vereinbarungen> ; <Anweisungen> end
20 <Vereinbarung> ::=
array [<arith. Konstante>] <Typ> <Identifikator>
21 <Variable> ::= <Identifikator>[<Ausdruck>]
Vorteile und Schranken der Verwendung kontextfreier Grammatiken
Vorteile: Entscheidbarkeit kontextfreier Sprachen (
nichtdeterministischer Kellerautomat Syntaxanalysator in Compilern)
Syntaxbäume als Mittel der Strukturbeschreibung und als Voraussetzung für Semantikdefinition (in Compilern Codedefinition)
Substitution als Voraussetzung für modulare Sprachdefinition (schrittweise Verfeinerung)
Nachteil:
Kontextbedingungen sind nicht durch kontextfreie Grammatiken definierbar (Beweis über Pumping Lemma für kontextfreie Sprachen).
Ist G = (N, T, P, S) die kontextfreie Grammatik, die die Syntax einer Programmiersprache beschreibt, und ist P die entsprechende Sprache, die die Kontextbedingungen erfüllt, dann gilt:
P L(G) T*
2.3 Abstrakte Syntax und ihre Beschreibungsmittel
Abstrakte Syntax Abstrahiert von der konkreten Repräsentation
einer Sprache Enthält nur die Strukturelemente, die für die
Semantikdefinition wichtig sind
Beispiel: konkreter und abstrakter Syntaxbaum von x := (x1 * 3)
Anweisung Konkreter Syntaxbaum
Variable := Ausdruck
Identifikator ( op2 )
Buchstabe Ausdruck * Ausdruck
x Variable Konstante
Identifikator arith. Konstante
Identifikator Ziffer Zahl
Buchstabe 1 Ziffer
x 3
:= Abstrakte Syntaxbäume
x *
x1 3
Anweisung
x Ausdruck
* x1 3
Formen abstrakter SyntaxBeispiel BPS
1.Variante
Syntaktische Kategorien: Programm, Anweisung, Ausdruck, Deklaration, Operationssymbol1, Operationssymbol2, Identifikator, Arithmetische Konstante, Logische Konstante, Typ
Regeln:
Programm ::= Deklaration* Anweisung+
Deklaration ::= Identifikator Typ
Anweisung ::= Ausdruck Anweisung+ Anweisung+
Anweisung ::= Identifikator Ausdruck
Anweisung ::= Ausdruck Anweisung+
Anweisung ::= Identifikator
Anweisung ::= Ausdruck
Ausdruck ::= Konstante| Identifikator| Arith_Konstante|
Log_Konstante| Operationssymbol1 Ausdruck| Operationssymbol2 Ausdruck Ausdruck
Variation durch Metavariablen:
An Anweisung, I Identifikator, Au Ausdruck
An ::= I Au| Au An1+ An2+|...
...
2. Variante
Programm ::= prog(Deklaration*, Anweisung+)
Deklaration ::= dekl(Identifikator, Typ)
Anweisung ::= if(Ausdruck, Anweisung+, Anweisung+)
Anweisung ::= assign(Identifikator, Ausdruck)
Anweisung ::= while(Ausdruck, Anweisung+)
Anweisung ::= in(Identifikator)
Anweisung ::= out(Ausdruck)
Ausdruck ::= Konstante| Identifikator| Arith_Konstante| Log_Konstante| op1(Ausdruck)|
op2(Ausdruck, Ausdruck)
x := (x1 * 3) als abstrakter Syntaxbaum nach Variante 2
assign
x *
x1 3
oder als Term
assign(x, *(x1, 3))
Formale BeschreibungsmittelVienna Definition Language (VDL)
Sprachelemente: Datenstrukturen: abstrakte Objekte Operationen: Selektion, Substitution
Abstrakte Objekte
Gegeben: nichtleere Menge elementarer Objekte E nichtleere Menge von Selektoren S
Abstraktes Objekt: Jedes elementare Objekt aus E ist ein
abstraktes Objekt. a1,..., an seien abstrakte Objekte und
s1,..., sn Selektoren aus S, wobei für i j auch si sj. Dann ist die Menge aller Paare <si : ai>, i=1,...,n ein abstraktes Objekt.
Notation: (<s1 : a1>, ..., <sn : an>)
Weitere abstrakte Objekte gibt es nicht.
Graphische Darstellung:
s1 s2 sn
a1 a2 an
Beispiel: E = {e1, ..., e4}, S = {, , }
e1
e3
e1 e2 e3
Lineare Notation:
(< : e1>,
< :
(< : (< : e1>, < : e2>, < : e3>)>,
< : e3>)
>)
Schachtelnotation: e1
e1
e2
e3
e3
Operationen: Auswahloperation: Auswahl eines abstrakten
Objekts aus einem gegebenen abstrakten Objekt anhand eines Selektors
a = (<s1 : a1>, ..., < sn : an>), s Selektor
ai , wenn s = si
s(a) =
, sonst
( ist das leere abstrakte Objekt)
Beispiel: a sei abstraktes Objekt aus obigem Beispiel. Dann (((a))) = e2 .
Substitution: Ein durch eine Selektorfolge bestimmtes abstraktes Objekt in einem gegebenem abstrakten Objekt wird durch ein neues abstraktes Objekt ersetzt.
Notation: (a, b, c)
a umzuformendes Objekt
b Selektorfolge
c einzufügendes Objekt
Beispiel: a obiges abstraktes Objekt
(a, .., ) = (< : e1>,
< : (< : (< : e1>, < : e3>)>, < : e3>)>)
Darstellung der abstrakten Syntax durch die VDL
Vorgehensweise:
1. Festlegung von Mengen elementarer Objekte und Selektoren bezogen auf die Programmiersprache
2. Einführung von Klassen abstrakter Objekte
3. Definition der Objektklassen durch Regeln (Mengengleichungen)
Beispiel: BPS Zu 1.: Mengen elementarer Objekte
Konstante, Variable, op1 (monadische Operatoren), op2 (dyadische Operatoren)
Zu 2.: Klassen abstrakter Objekte
Ausdruck, monadischer_Ausdruck, dyadischer_Ausdruck, Anweisung, Vereinbarung,...
Zu 3.: Regeln
Ausdruck = Konstante|Variable|monadischer_Ausdruck| dyadischer_Ausdruck
Die Objektklasse Ausdruck ergibt sich als Vereinigung der Objektklassen Konstante, Variable, monadischer_Ausdruck und dyadischer_Ausdruck.
monadischer_Ausdruck =
(<op : op1>, <arg : Ausdruck>)
Ein Element der Klasse monadischer_Ausdruck ist ein abstraktes Objekt mit der Struktur beschrieben auf der rechten Seite der Gleichung.
Analog:
dyadischer_Ausdruck = (<op : op2>,
<arg1 : Ausdruck>, <arg2 : Ausdruck>)
Beispiel: abstraktes Objekt zu ((-(x/y)) + 1)
op arg1 arg2
+ op arg 1
-
op arg1 arg2
/ x y
(<op : +>, <arg1 : (<op : ->, <arg : (<op : />, <arg1 : x>, <arg2 : y>)>)>, <arg2 : 1>)
Darstellung der abstrakten Syntax durch die Vienna Development Method (VDM)
Elemente der Beschreibungssprache Meta IV (neue Bezeichnung: VDM-SL):
:: Trennzeichen von linker und rechter Seite in Regeln zur Definition baumartiger Objekte
= | Verwendung wie in VDL (K m L) Menge aller Funktionen mit dem
Definitionsbereich K und dem Resultatsbereich L A* Menge aller endlichen Folgen von Objekten der
Objektklasse A einschließlich der leeren Folge _ bezeichnet elementare Objekte
Beispiel: ausgewählte Regeln für BPS
Programm :: Vereinbarungen Anweisung+
Objekt aus Objektfolge aus
Vereinbarungen Anweisung
(In VDL:
Programm = (<decl : Vereinbarungen>,
<stats : Anweisungen>) )
Vereinbarungen :: (Variable m Typ)
Endliche Funktion, die jedem Objekt aus der Klasse Variable ein Objekt aus der Klasse Typ zuweist.
Typ = INT|BOOLDie Klasse Typ enthält die Objekte INT und BOOL.
Anweisung = leere_Anweisung|Wertzuweisung|
bedingte_Anweisung|LaufanweisungDie Klasse Anweisung ist eine Vereinigung der
Klassen ...
leere_Anweisung :: SKIP
Wertzuweisung :: Variable Ausdruck
Variable :: Identifikator
bedingte_Anweisung ::
Ausdruck Anweisung+ Anweisung+
Laufanweisung :: Ausdruck Anweisung+
Ausdruck = ... Siehe VDL
Klassen elementarer Objekte: Konstante, Identifikator, op1, op2, leere_Anweisung, Typ
Strukturelle Syntax (konkret und abstrakt)
Beispiel: BPS
Syntaktische KategorienNotation: v M bedeutet, v vertritt ein beliebiges Objekt
aus M
ak ArithKonstante lk LogKonstante
li LogIdentifikator ai AritIdentifikator
aa ArithAusdruck la LogAusdruck
ao1 ArithOperator1 ao2 ArithOperator2
lo1 LogOperator1 lo2 LogOperator2
vo Vergleichsoperator an Anweisung
Regeln (Auswahl)
Axiome
ak : ArithAusdruckEine arithmetische Konstante ist ein arithmetischer
Ausdruck.
ai : ArithAusdruckEin arithmetischer Identifikator ist ein arithmetischer
Ausdruck.
lk : LogAusdruck
li : LogAusdruck
Schlussregelnaa : ArithAusdruck
ao1 aa : ArithAusdruck
Ist aa ein arithmetischer Ausdruck, dann ist auch ein beliebiger unärer (monadischer) arithmetischer Operator gefolgt von aa ein arithmetischer Ausdruck.
aa1 : ArithAusdruck aa2 : ArithAusdruck
aa1 ao2 aa2 : ArithAusdruck
la : LogAusdruck an1 : Anweisung an2 : Anweisung
if la then an1 else an2 fi : Anweisung
3 SemantikdefinitionFormale Methoden
Arten der Semantikdefinition:
Vor.: P Menge der erlaubten Programmkonstrukte, p P
Operational:
p b1, ..., bn Befehlsfolge eines abstrakten
Rechners
z0 b1 z1 b2 ... bn
zn Zustandsübergänge des abstrakten Rechners
Denotational:
p mathematisches Objekt
Speziell: f [C p C] Funktion zur Änderung von Variablenbelegungen
C = [Variable Wert] Menge der Variablenbelegungen
Axiomatisch:
p {} p {} verallgemeinerte Formel,
, logische Formeln mit geeigneter Interpretation
3.1 Operationale Semantik3.1.1 Grundbegriffe
Maschine (abstrakter Rechner): M = (Z, T) mit
Zustandsmenge Z und binärer Relation T (Übergangsrelation) auf Z
(Befehle können als Bestandteil eines Zustands aufgefasst werden)
Deterministische Maschine: Maschine mit partieller Übergangsfunktion
Berechnung auf einer Maschine:
Beliebige Zustandsfolge z0, z1,... , wobei
zi T zi+1 (deterministisch: T(zi) = zi+1), i=0, 1,...
Endzustand z: Es existiert kein Zustand z´ mit
z T z´ (deterministisch: T(z) ist nicht definiert).
Echte Berechnung:
1. Unendliche Berechnung oder
2. Endliche Berechnung, die auf einen Endzustand endet.
Ergebnisrelation: binäre Relation ResM, wobei
z ResM z´ z0, ..., zn echte Berechnung mit
z = z0 und z´= zn.
(Bei deterministischen Maschinen existiert zu jedem z höchstens 1 echte Berechnung. ResM ist eine partielle Funktion.)
Allgemeine Vorgehensweise für operationale Semantikdefinition:
1. Definition der abstrakten Syntax der Programmiersprache
2. Definition einer geeigneten abstrakten Maschine in Abhängigkeit von der Programmiersprache
3. Zuordnung von Befehlsfolgen/Zustandsfolgen der abstrakten Maschine zu jedem Programmkonstrukt einschließlich kompletten Programmen
3.1.2 Operationale Semantikdefinition unter Nutzung der VDL
Definition der abstrakten Maschine –
w-Maschine: Zustand (abstraktes Objekt im Sinne der
VDL)
s iz ev
Steuerteil Innerer Zustand Umgebung
Steuerteil: enthält hierarchisch organisiert Anweisungen (Befehle) der w-Maschine mit abstrakten Programmteilen als Parameter
Innerer Zustand: Zuordnung von Werten zu Adressen (Speicherbelegung)
Umgebung: Zuordnung von Adressen zu Variablen (Speicherzuteilung zu Programmvariablen)
Zustandsübergänge:
- Realisierung durch Ausführung von Anweisungen in den Blättern des Steuerteils (bei Vorhandensein aller Parameterwerte)
- Endzustand: Zustand mit leerem Steuerteil
- Fehlerzustand: keine Anweisung ist ausführbar und Endzustand wurde nicht erreicht
Beispiel: Abarbeitung der Wertzuweisung x := (y * 3) aus BPS im Zustand mit x = 1 und y = 5
Startzustand
s iz ev
int-Ergibt x y
(´x:=(y*3)´) 1 5
´x:=(y*3)´ bedeutet die abstrakte Repräsentation der Wertzuweisung; und sind Adressen;
n repräsentiert Werte
Abarbeitung einer Wertzuweisung (Anweisung int-Ergibt mit abstrakter Struktur der Wertzuweisung als Parameter):
Bestimmung der Adresse der Variablen der linken Seite
Berechnung des Werts des Ausdrucks der rechten Seite
Abspeicherung des berechneten Werts auf der bestimmten Adresse
Widerspieglung im Steuerteil:
int-Ergibt(´v:=A´) subst(ad,w)
ad: Adresse(´v´) w: int-Ausdr(´A´)
Adresse(´v´) = v(ev(z)) - Adressenbestimmung für Variable v
subst(ad,w) = (z, ad(iz(z)), w) - Änderung des Werts (neuer Wert w) einer
Variablen repräsentiert durch Adresse ad
Berechnung eines Ausdrucks (int-Ausdr): Fall 1: Ausdruck ist Konstante k:
int-Ausdr(´k´) = Wert(´k´) = k Fall 2: Ausdruck ist Variable v:
int-Ausdr(´v´) = Inhalt(´v´) = v(ev(z))(iz(z))
(v(ev(z)) ist die Adresse von z) Fall 3: Ausdruck ist dyadischer Ausdruck:
- Berechnung der Werte der Operanden
- Verknüpfung der Operandenwerte durch entsprechende Operation
int-Ausdr(´A op2 B´) c: int-op(´op2´, a, b)
a: int-Ausdr(´A´) b: int-Ausdr(´B´)
(Berechnung von (Berechnung von
Operand A) Operand B)
Fall 4: Ausdruck ist monadisch: analog zu Fall 3
Arten von Anweisungen im Steuerteil: Anweisungen zur Erzeugung von Werten:
- Berechnung von Argumenten der Anweisungen an Vorgängerknoten
bzw. Änderungen im inneren Zustand oder in der Umgebung
- Entfernung des Knotens aus dem Steuerteil nach der Berechnung
Anweisungen zur Entwicklung des Steuerteils (Aufgabenzerlegung in Teilaufgaben):
Ersetzen des Knotens mit der Anweisung durch Baum mit Anweisungen
Fortsetzung des Beispiels beginnend mit dem Startzustand (Verzicht auf inneren Zustand und Umgebung):
int-Ergibt(´ x:=(y*3)´) subst(ad,v)
ad: Adresse(´x´) v: int-Ausdr(´(y*3)´)
subst(, v) subst(, v)
v: int-op(´*´, a, b)
v: int-Ausdr(´(y*3)´)
a: int-Ausdr(´y´) b: int-Ausdr(´3´)
subst(, v) subst(, v) v: int-op(´*´, a, b) v: int-op(´*´, 5,
b)
a: Inhalt(´y´) b: int-Ausdr(´3´) b: int-Ausdr(´3´)
subst(, v) subst(, v) subst(,15)
v: int-op(´*´, 5, b) v: int-op(´*´, 5,3)
b: Wert(´3´)
Endzustand
iz ev
x y
15 5
3.1.3 Strukturelle operationale Semantik
Beispiel: BPS
Zustände
st(in, out, sto), wobei
in Eingabedatei in Form einer Liste
out Ausgabedatei in Form einer Liste
sto: Variable Wert Variablenbelegung im Zustand
Hilfsfunktionen: Listenmanipulation: head (erstes Element),
tail (Restliste nach Entfernen des ersten Elements), append (Listenverkettung)
Leere Variablenbelegung (Speicher-initialisierung): emptySto
Speicheraktualisierung durch Zuweisung eines Wertes w zu einer Variablen v:
updateSto(sto, v, w) = sto´, wobei
sto´(v) = w und sto´(y) = sto(y) für alle y v
(Andere Notation: sto´= sto{v/w})
Bestimmung des Wertes einer Variablen v: applySto(sto, v) = w, wenn sto(v) = w
Berechnung von monadischen (unären) Ausdrücken:
compute1(op1, arg) = w, wobei
op1 ArithOperator1, arg ist der Wert des Operanden und w das Ergebnis der Berechnung
Analog erfolgt die Berechnung dyadischer Ausdrücke durch
compute2(op2, arg1, arg2) = w
Übergangsrelation:
Nutzung von Konfigurationen und Regeln zur Beschreibung des Übergangs zwischen Konfigurationen
Konfiguration: <Programmstück, Zustand>
Übergang: <A, z> <A´, z´>
Beendigung des Übergangs: Erreichen einer Endkonfiguration <skip, z> Erreichen einer Konfiguration, in der keine
Regel anwendbar ist
Regeln für BPS (Auswahl)(1) Bestimmung des Wertes einer arithmetischen
Variablen (syntaktisch identisch mit arithmetischem Identifikator) im Zustand st(_,_, sto):
<ai, st(_,_,sto)> <applySto(sto, ai), st(_,_, sto)>
(Speicherbelegung wird nicht geändert)
(2) Berechnung eines arithmetischen Ausdrucks, dessen Operanden als Konstanten, und damit wertmäßig, vorliegen:
<ak1 ao2 ak2, st(_,_, sto)>
<compute2(ao2, ak1, ak2), st(_,_, sto)>, wobei (ao2 /) oder (ak2 0)
(3) Transformation arithmetischer Ausdrücke in die Form von Regel (2):<aa1, st(_,_, sto)> <aa1´, st(_,_, sto)>
<aa1 ao2 aa2, st(_,_, sto)> <aa1´ ao2 aa2, st(_,_, sto)>
(4) Ausführung einer Wertzuweisung mit Konstante auf rechter Seite:
<ai := ak, st(_,_, sto)>
<skip, st(_,_,update(sto, ai, ak))>
(5) Einlesen eines Wertes von der Eingabedatei in und Zuweisung an eine Variable:
<read ai, st(in,_, sto)> <skip, st(tail(in),_, update(sto, ai, head(in)))>
vorausgesetzt in [ ]
(6) Transformation einer Wertzuweisung in die Form (4):
<aa, st(_,_, sto)> <aa´, st(_,_, sto)>
<ai := aa, st(_,_, sto)> <ai := aa´, st(_,_, sto)>
Beispiel: Berechnung von x := (y * 3)
Vor.: x = 1, y = 5 sto0(x) = 1, sto0(y) = 5
Startkonfiguration:
<x := (y * 3), st(_,_, sto0)>
Betrachtung von
< y * 3, st(_,_, sto0)>
Betrachtung von
<y, st(_,_, sto0)>
Wertbestimmung für y nach Regel (1)
<applySto(sto0, y), st(_,_, sto0)>
Anwendung von Regel (3)
<y, st(_,_, sto0)> <5, st(_,_, sto0)>
< y * 3, st(_,_, sto0)> <5*3, st(_,_, sto0)>
Anwendung von Regel (2)
<5*3, st(_,_, sto0)>
<compute2(*, 5, 3), st(_,_, sto0)>
Anwendung von Regel (6)< y * 3, st(_,_, sto0)> <15, st(_,_, sto0)>
<x := (y * 3), st(_,_, sto0)> <x := 15, st(_,_, sto0)>
Anwendung von Regel (4)<x := 15, st(_,_, sto0)> <skip, st(_,_, sto1)>, wobei sto1 = updateSto(sto0, x, 15)
Probleme
Konsistenz: Widerspruchsfreiheit der Regeln
Vollständigkeit: Semantik kann entsprechend Realität ausgedrückt werden
Hier:
Konsistenz: Der durch die Regeln berechnete Wert eines Ausdrucks ist eindeutig bestimmt.
Vollständigkeit: Hat ein Ausdruck einen Wert w, dann kann dieser durch die Regeln berechnet werden.
Behauptung: Alle Ausdrücke unserer Programmiersprache lassen sich durch die Regeln richtig berechnen, d.h. die Regeln sind konsistent und vollständig.
Beweis: durch strukturelle Induktion:
1. Eigenschaft gilt für Variablen und Konstanten
2. Wenn die Eigenschaft für alle Operanden eines Ausdrucks gilt, dann gilt sie auch für alle daraus zusammengesetzten (erlaubten) Ausdrücke.
3.2 Denotationale SemantikGrundbegriffe
Prinzip: Baukastenprinzip
- Bedeutung komplexer Konstrukte ist aus Bedeutungen der Komponenten zusammengesetzt
- Relativ isolierte Betrachtung der Bausteine möglich
- Beweise durch strukturelle Induktion
- Austauschbarkeit semantisch äquivalenter Bausteine
Vorgehensweise: Definition der syntaktischen
Definitionsbereiche (Strukturen) Definition der semantischen
Definitionsbereiche (Bedeutungen) Einführung funktionaler Operatoren zur
Umsetzung des Baukastenprinzips
(Kombination von Bedeutungen) Festlegung von Basisfunktionen Schrittweise Definition der Semantik
elementarer und zusammengesetzter Programmkonstrukte
3.2.1 Denotationale Semantikdefinition am Beispiel BPS
Voraussetzung: Alle Programmkonstrukte sind syntaktisch korrekt und erfüllen die Kontextbedingungen.
Syntaktische Definitionsbereiche (Auswahl)
Ausdruck Anweisung Variable
Konstante op1 op2
Semantische Definitionsbereiche
Variablenwerte
ℤ Menge der ganzen Zahlen
WF = {W, F} Menge der Wahrheitswerte W (wahr) und F (falsch)
W = WF ℤ {} Menge aller möglichen Variablenwerte einschließlich undefiniertem Wert
C = [Variable W] Menge aller Variablenbelegungen
Bedeutungen von Ausdrücken und Anweisungen
CW = [C W] Menge aller Wertberechnungen von Ausdrücken in Abhängigkeit von den Variablenbelegungen
S = [C p C] Menge aller Änderungen von Variablenbelegungen
Beispiele:
- c0 C mit c0 = {(x, -30), (y, 1), (z, ),...} , d.h. c0(y) = 1 usw.
- (x + y) Ausdruck f CW,
wobei f eine gegebene Variablenbelegung (und damit die Werte für x und y) auf den Wert des Ausdrucks abbildet;
also f(c0) = –29 .
- x := (x + y) Anweisung g S,
wobei g eine gegebene Variablenbelegung für die Variable x abändert; also g(c0) = c1.
x hat nun den Wert des Ausdrucks, somit
c1(x) = -29 und c1(v) = c0(v) für v x oder
kürzer g(c0) = c0{x/-29} .
Basisfunktionen
Den Operatoren von BPS werden die üblichen Operationen (Basisfunktionen) als Bedeutungen zugeordnet.
Notation: unterstrichener Operator bedeutet die zugeordnete Operation
Beispiel:
+ op2 + Addition zweier integer-Zahlen
Operator zugeordnete Operation
Funktionale Operatoren
Verkettung partieller Funktionen:
f: A p B , g: B p C f.g: A p C
mit (f.g)(x) = g(f(x)), wenn f(x) und g(f(x)) definiert sind
Auswahloperation:
f: A p B , g: A p B, Bed: A p WF ...
(Bed f, g): A p B mit
f(a), wenn Bed(a) = W
(Bed f, g)(a) = g(a), wenn Bed(a) = F
? , sonst
Modifizierung:
f: A p B , a A, b B f{a/b}: A p B mit f{a/b}(a) = b und f{a/b}(x) = f(x) für x a.
Fixpunktoperator:
У(f) liefert den kleinsten Fixpunkt der Funktionalgleichung f(x) = x.
Voraussetzungen: s.u.
Semantikdefinition für ausgewählte Konstrukte
Semantik von Ausdrücken
Wert: Ausdruck CW
Wert ordnet jedem Ausdruck als Bedeutung eine Funktion aus CW zu, d.h.
Wert 〚 a 〛 CW und Wert 〚 a 〛 (c) W,
a Ausdruck, c C.
Bedeutung logischer Konstanten
Wert 〚 true 〛 (c) = W Wert 〚 false 〛 (c) = F
Bedeutung von integer-Zahlen
Wert 〚 n 〛 (c) = n , n integer-Zahl, c C
Bedeutung von Variablen
Wert 〚 x 〛 (c) = c(x) , x Variable, c C
Bedeutung monadischer und dyadischer Ausdrücke
Wert 〚 (o E) 〛 (c) = o Wert 〚 E 〛 (c)
Wert 〚 (E1 o E2) 〛 (c) = Wert 〚 E1 〛 (c) o Wert 〚 E2 〛(c)
E, E1, E2 Ausdrücke, c CBeispiel:
Wert 〚 (y + 3) 〛 (c0) = Wert 〚 y 〛 (c0) + Wert 〚 3 〛 (c0)
= c0(y) + 3 = 1 + 3 = 4
Semantik von Anweisungen
SD: Anweisung S
Jeder Anweisung wird als Bedeutung eine Funktion aus S zugeordnet, die die durch die Abarbeitung bewirkte Änderung der Variablenbelegung beschreibt; somit
SD 〚 A 〛 S , SD 〚 A 〛 (c) C
für A Anweisung und c C.
Semantik der skip-Anweisung
SD 〚 skip 〛 = Id , Id Identität auf C
Die Ausführung der skip-Anweisung lässt Variablenbelegungen unberührt.
Semantik von Wertzuweisungen
SD 〚 x := E 〛 (c) = c{x/ Wert 〚 E 〛 (c)}
x Variable, E Ausdruck, c C
Durch die Abarbeitung der Wertzuweisung wird die ursprüngliche Variablenbelegung modifiziert. Die Variable der linken Seite bekommt als Wert den Wert des Ausdrucks der rechten Seite zugeordnet.
Beispiel:
SD 〚 x := (y + 3) 〛 (c0) = c0{x/ Wert 〚 (y + 3) 〛 (c0)}
= c0{x/4}
= c1
Folglich: c1(x) = 4 , c1(v) = c0(v) für v x
Semantik der if-Anweisungen
SD 〚 if B then A1 else A2 fi 〛 (c) =
(Wert 〚 B 〛 SD 〚 A1 〛 , SD 〚 A2 〛 )(c)
Die Bedeutung einer if-Anweisung ist im regulären Fall die Bedeutung der Anweisungsfolge A1 oder der Anweisungsfolge A2 in Abhängigkeit vom Wahrheitswert des Ausdrucks (Bedingung).
Beispiel:
SD 〚 if (x > 0) then y := 1 else y := 0 fi 〛 =
(Wert 〚 (x > 0) 〛 SD 〚 y := 1 〛 , SD 〚 y := 0 〛 )
Semantik von Anweisungsfolgen
SD 〚 A1 ; A2 〛 = SD 〚 A1 〛 . SD 〚 A2 〛A1, A2 Anweisung
Anweisungsfolgen werden sequentiell abgearbeitet.
Beispiel:
SD 〚 x := (y – 1) ; y := (z + 25) 〛 =
SD 〚 x := (y – 1) 〛 . SD 〚 y := (z + 25) 〛
SD 〚 x := (y – 1) 〛 SD 〚 y := (z + 25) 〛
c0 c1 c2
Semantik der while-Anweisung
SD 〚 while B do A od 〛 =
SD 〚 if B then A; while B do A od else skip fi 〛 =
(Wert 〚 B 〛 SD 〚 A 〛 . SD 〚 while B do A od 〛 , Id)
= F() mit = SD 〚 while B do A od 〛 und
F() = (Wert 〚 B 〛 SD 〚 A 〛 . , Id) , S (*)
Gesucht wird also eine Funktion aus S, die die Fixpunktgleichung (*) erfüllt.
Abarbeitung von while B do A od
- Darstellung als Programmablaufplan
B nein
ja
A
- Ablauf zeitlich gestreckt mit Variablenbelegungenc0 c1 c2
B nein B nein B nein
c0 c1 c2
ja ja ja
A A A
c3
Abbruchsituationen:
1. Abbruch nach der Bedingungsüberprüfung des ersten Durchlaufs wegen Nichterfüllung der Bedingung: Ergebnis ist Variablenbelegung c0
2. Abbruch nach der Bedingungsüberprüfung des (i+1)-ten Durchlaufs wegen Nichterfüllung der Bedingung: Ergebnis ist Variablenbelegung ci
3. Abbruch wegen Fehlersituation: Ergebnis ist undefinierte Variablenbelegung
4. Kein Abbruch (unendliche Schleife): Ergebnis ist undefinierte Variablenbelegung (sollte von Fall 3 unterschieden werden)
Eigenschaften der Lösungsfunktion *:
undef. c bei unendlicher Schleife
*(c0) = ci , Wert 〚 B 〛 (cj) = W für j=0,1,...,i-1 und Wert 〚 B 〛 (ci) = F
c0 , Wert 〚 B 〛 (c0) = F
? , Fehlerabbruch
FixpunktsatzMathematische Grundlagen(Theorie der semantischen Bereiche von Scott)
Intuitive Vorstellung eines semantischen Bereichs:
- Als Träger Struktur mit Datenobjekten eines bestimmten Typs (endliche und unendliche Objekte)
- Berechnung unendlicher Objekte durch endliche Approximation
Beispiel: partielle einstellige Funktionen über natürlichen Zahlen (f: M p N, M N)
Endliche Objekte: Funktionen mit endlichem Definitionsbereich (M endlich)
Unendliche Objekte: Funktionen mit unendlichem Definitionsbereich (M unendlich)
Approximation ( ): ⊑f approximiert g (f g) genau dann, wenn gilt:⊑Ist f(x) definiert, dann ist auch g(x) definiert und
f(x) = g(x).
Endliche Datenobjekte:
fn: N p N 2x, wenn 0 x n
mit fn(x) =
undef., sonst
Daher: fn f⊑ m für n,m N und n m
Unendliches Datenobjekt: f*(x) = 2x , x N
Es gilt: f⊥ ⊑ 1 f⊑ 2 f⊑ 3 ⊑ ... f⊑ *
Definition (semantischer Bereich im Sinne von cpo = complete partial order):
Eine Struktur A = (A, ⊑A) ist ein semantischer Bereich, wenn gilt:
1. ⊑A ist eine Halbordnung auf der Trägermenge A
2. In A existiert bzgl. ⊑A ein kleinstes Element ⊥A.
3. Jede Kette K A besitzt bzgl. ⊑A eine kleinste obere Schranke K in ∐ A.
(Kette = geordnete Menge)
Beispiele: N {} 0 1 2 3 ...
N mit ∞ ∞
.
.
2
1
0
Menge von Teilmengen der Menge {a, b, c}
{a, b, c}
{a, c}
{a, b} {b, c}
{b}
{a} {c}
=
Definition: A, B semantische Bereiche
f: A p B
f ist monoton: Für alle a1, a2 A folgt aus
a1 ⊑A a2 auch f(a1) ⊑B f(a2).
f ist stetig: Für jede Kette K A gilt, f(K) ist eine Kette und f( K) = f(K).∐ ∐
f ist strikt: f(A) = B.
Notation: [A B] semantischer Bereich aller Funktionen, die A in B abbilden, mit Approximation als Halbordnung.⊑
Fixpunktsatz:
A semantischer Bereich, F [A p A] stetig
Der kleinste Fixpunkt der Gleichung F() =
ist gegeben durch
У(F) = ∐n=0
∞ Fn(A)
Anwendung für die while-Anweisung:
- = F() mit = SD 〚 while B do A od 〛 und
F() = (Wert 〚 B 〛 SD 〚 A 〛 . , Id) , S
- F() = (Wert 〚 B 〛 SD 〚 A 〛 . , Id) = F1
- Fi+1()) = (Wert 〚 B 〛 SD 〚 A 〛 . Fi, Id)
- Lösungsfunktion:
C , Wert 〚 B 〛 (c0) = W für j=0,1,2,...
ci , Es existiert ein i so, dass
*(c0) = Wert 〚 B 〛 (cj) = W für j=0,1,2,...,i-1 und Wert 〚 B 〛 (ci) = F
c0 , Wert 〚 B 〛 (c0) = F
? , sonst
Semantik für Ein- und Ausgabeanweisungen
Wirkung der Eingabeanweisung read x, x Variable:
Lesen eines Wertes von einer Eingabedatei (mit Löschen) und Zuweisung zur Variablen
Wirkung der Ausgabeanweisung write A,
A Ausdruck:
Berechnung des Ausdrucks und Ausgabe auf eine Ausgabedatei
Modellierung der Ein- und Ausgabedateien durch zwei interne Variablen Ein und Aus, wobei jeder Variablen eine Wertefolge zugeordnet ist:
c(Ein) W* , c(Aus) W*
Denotationale Modellierung:
SD 〚 read x 〛 (c) = c´, x Variable, wobei gilt:
1. Wenn c(Ein) = w1 w2 ... wn , dann c´(Ein) = w2 ... wn
(Fehler bei c(Ein) = ).
2. c´(x) = w1
3. c´(y) = c(y) für alle übrigen Variablen
SD 〚 write A 〛 (c) = c´, A Ausdruck, wobei gilt:
1. Wenn c(Aus) = w1 w2 ... wn ,
dann c´(Aus) = w1 ... wn Wert 〚 A 〛 (c) .
2. c´(y) = c(y) für alle übrigen Variablen.
Semantik von Vereinbarungen (hier für Variablen)
Wirkung der Variablenvereinbarungen: Information über die Eigenschaften der im Programm
verwendeten Variablen Basis für Compileraktionen:
Speicherplatzreservierung, Initialisierung
Denotationale Umsetzung: c(x) = ? Variable x wurde noch nicht vereinbart c(x) W Variable x wurde vereinbart und besitzt
einen Wert aus W
Einführung einer Anfangsbelegung (Startzustand) c0 für ein Programm:
c0(x) = ? für x Variable ( x ist nicht deklariert)
c0(Ein) = w1 w2 ... wn W* Eingabedatei
c0(Aus) = Ausgabedatei
SD 〚 t x 〛 (c) = c´, x Variable, t Typ, wobei gilt:
1. c´(x) = ( x ist deklariert)
2. c´(y) = c(y) für alle übrigen Variablen
Semantik von Programmen
SD 〚 begin V; A end 〛 =
(SD 〚 V 〛 . SD 〚 A 〛 . SD1 〚 V 〛 ) ,
V Vereinbarung, A Anweisung
SD1 macht Anweisungen „rückgängig“:
SD1 〚 t x 〛 (c) = c´, x Variable, t Typ, wobei gilt
c´(x) = ? ( x ist nicht mehr deklariert)
Beispiel:
begin int x; int y; V1 V2
read y; A1
x := (y – 5); A2
write x A3
end
SD 〚 P 〛 = SD 〚 V1 〛 . SD 〚 V2 〛 .
SD 〚 A1 〛 . SD 〚 A2 〛 . SD 〚 A3 〛 .
SD1 〚 V1 〛 . SD1 〚 V2 〛
Anfangsbelegung: c0(Ein) = -3 c0(Aus) =
c0(x) = c0(y) = ?
c Ein Aus x y Sem. Funktion
c0 -3 ? ? SD 〚 int x 〛
c1 -3 ? SD 〚 int y 〛
c2 -3 SD 〚 read y 〛
c3 -3 SD 〚 x := (y – 5) 〛c4 -8 -3 SD 〚 write x 〛
c5 -8 -8 -3 SD1 〚 int x 〛
c6 -8 ? -3 SD1 〚 int y 〛
c7 -8 ? ?
Denotationale Semantik für eine Erweiterung von BPS
Blockkonzept
Syntax:
<Anweisung> ::= <Block>
<Block> ::=
begin <Vereinbarungen>;<Anweisungen> end
Rolle von Blöcken: Einführung eines neuen Vereinbarungsniveaus Beschränkung der Lebensdauer von Objekten auf
den Block Beschränkung der Zugriffsrechte: neu vereinbarte
Identifikatoren verdecken bis zum Blockende das bisher mit dem Identifikator verbundene Objekt
Identifikationsprozess für Identifikatoren: Zu jedem angewandten Auftreten eines Identifikators Suche des definierenden Auftretens zunächst im Block des angewandten Auftretens und bei Fehlen im unmittelbar umfassenden Block; Fortsetzung des Prozesses bis zum Erfolg oder, bis der Misserfolg sicher ist.
Beispiel: Ik(x, y) bedeutet eine Anweisungsfolge mit x und y
1: begin int x; int y;
I1(x, y);
2: begin bool y;
I2(x, y);
3: begin int x;
I3(x, y)
end;
I4(x, y);
4: begin int y;
I5(x, y)
end;
I6(x, y)
end;
I7(x, y)
end
Realisierung des Blockkonzepts: Allgemein: Umgebungskonzept zur
Zuordnung von Objekten zu Identifikatoren Hier: Orientierung an der Verwendung von
Kellerspeichern für die Datenverwaltung in Compilern 1. Erweiterung der Funktionen c aus C:
c: Variable {Ein, Aus} W* mit
c: Variable W+ , wobei
c(x) = ? x ist nicht vereinbart
c(x) = w1 w2 ... wn
w1 Wert im sichtbaren Block
wi, i > 1, Werte in umfassenden Blöcken
Beispiel: Programm siehe obiges Beispiel
Belegung von y in I5: c(y) = w1 w2 w3 , wobei
w1 der Wert in I5, w2 der Wert am Ende von I4 und w3 der Wert am Ende von I1 sind
2. Verlängerung der Wertefolge einer Variablen von links um 1 Element beim Auftreten des Identifikators in einer Vereinbarung:
SD 〚 t x 〛 (c) = c´, x Variable, t Typ, wobei gilt:
- Wenn c(x) = ?, dann c(x) = .
- Wenn c(x) = w1 w2 ... wn ,
dann c(x) = w1 w2 ... wn.
3. Arbeit nur mit dem ersten Element der Wertefolge:
- SD 〚 x := E 〛 (c) = c´ , x Variable,
E Ausdruck, wobei gilt:
Wenn c(x) = w1 w2 ... wn ,
dann c´(x) = Wert 〚 E 〛 (c) w2 ... wn .
Analog: SD 〚 read x 〛- Wert 〚 x 〛 (c) = [c(x)]1 , x Variable
4. Verkürzung der Wertefolge einer Variablen von links um 1 Element beim Verlassen eines Blocks mit definierendem Auftreten der Variablen:
SD1 〚 t x 〛 (c) = c´, x Variable, t Typ, wobei gilt:
- Wenn c(x) = w , dann c´(x) = ? .
- Wenn c(x) = w1 w2 ... wn ,
dann c´(x) = w2 ... wn .
5. Semantik von Programmen oder Blöcken:
SD 〚 begin V; A end 〛 =
(SD 〚 V 〛 . SD 〚 A 〛 . SD1 〚 V 〛 ) ,
V Vereinbarung, A Anweisung
Beispiel:
begin int x; int y; V1 V2 B1
read y; A1
x := (y – 5); A2
begin bool x; read y; V3 A3 B2
x := (y > 0); A4
write x A5
end;
y := x; A6
write y A7
end
Anfangsbelegung:
c0(Ein) = -3 0 c0(Aus) = c0(x) = c0(y) = ?
SD 〚 B1 〛 = SD 〚 V1 〛 . SD 〚 V2 〛 . SD 〚 A1 〛 .
SD 〚 A2 〛 . SD 〚 B2 〛 . SD 〚 A6 〛 . SD 〚 A7 〛 .
SD1 〚 V1 〛 . SD1 〚 V2 〛SD 〚 B2 〛 = SD 〚 V3 〛 . SD 〚 A3 〛 . SD 〚 A4 〛 .
SD 〚 A5 〛 . SD1 〚 V3 〛
c Ein Aus x y Sem. Funktion
c0 -3 0 ? ? SD 〚 V1 〛
c1 -3 0 ? SD 〚 V2 〛
c2 -3 0 SD 〚 A1 〛 c3 0 -3 SD 〚 A2 〛 c4 0 -8 -3 SD 〚 V3 〛 c5 0 -8 -3 SD 〚 A3 〛 c6 -8 0 SD 〚 A4 〛
c7 F -8 0 SD 〚 A5 〛 c8 F F -8 0 SD1 〚 V3 〛
c9 F -8 0 SD 〚 A6 〛
c Ein Aus x y Sem. Funktion
c10 F -8 -8 SD 〚 A7 〛
c11 F -8 -8 -8 SD1 〚 V1 〛
c12 F -8 ? -8 SD1 〚 V2 〛
c13 F -8 ? ?
Vektoren
Voraussetzung: Der kleinste Index wird mit 1 festgesetzt und der größte durch eine Konstante in der Vereinbarung angegeben.
Syntax:
<Vereinbarung> ::= array [<Konstante>] <Typ>
<Variable> ::= <Identifikator>[<Ausdruck>]
Realisierung: Vektor x als endliche Funktion V
V:{1, ..., Konstante} W
Beispiel: x = (x1 x2 x3) = (1 7 -5)
Als Funktion: x = {(1, 1), (2, 7), (3, -5)}
Bezeichnung: VEKTOR bedeute im Weiteren die Menge aller endlichen Abbildungen dieser Art
Erweiterung der Funktionen c aus C:
c(x) {W VEKTOR}+, x Variable, d.h.
c(x) = wv1 ... wvn mit wvi W VEKTOR
wvi VEKTOR heißt, x wurde auf dem i-ten Deklarationsniveau als Vektor vereinbart und wvi ist demzufolge eine endliche Abbildung, die den Indizes Werte zuordnet (Vektorkomponenten).
Wert 〚 x(E) 〛 (c) = [c(x)]1(Wert 〚 E 〛 (c) )
= wv1(Wert 〚 E 〛 (c))
mit c(x) = wv1 ... wvn .
Beispiel: v = {(1, 1), (2, 7), (3, -5)}, c(x) = v
Wert 〚 x(2) 〛 (c) = [c(x)]1(Wert 〚 2 〛 (c) ) = v(2) = 7
SD 〚 array [k] t x 〛 (c) = c´, K Konstante, T Typ, x Variable, wobei gilt:
1. Wenn c(x) = ?, dann c´(x) = v mit
v = {(1, ), (2, ), ..., (k, )}.
2. Wenn c(x) = w1 ...wn , dann c´(x) =v w1 ...wn mit v = {(1, ), (2, ), ..., (k, )}.
SD 〚 x[E1] := E2 〛 (c) = c´, E1,E2 Ausdruck, wobei gilt:
Wenn [c(x)]1 = v VEKTOR,
dann [c´(x)]1 = v´ VEKTOR und
- v´(Wert 〚 E1 〛 (c)) = Wert 〚 E2 〛 (c) (Setzen der Komponente Wert 〚 E1 〛 (c) des Vektors x
auf den Wert Wert 〚 E2 〛 (c))
- v´(i) = v(i) für i = 1, ..., k , i Wert 〚 E1 〛 (c)(restliche Komponenten bleiben unverändert)
- c´(y) = c(y) für y x (restliche Variablen bleiben unverändert)
Beispiel: c(i) = 2 , c(x) = v w1 ...wn mit
v = {(1, 1), (2, 7), (3, -5)},
SD 〚 x[i] := 0 〛 (c) = c´, wobei
c´(x) = v´ w1 ...wn mit
v´ = {(1, 1), (2, 0), (3, -5)},
Axiomatische Semantik
Charakterisierung und Ziele:- Abstraktion vom Berechnungsverlauf- Formulierung von Aussagen über
Programmen und Teilprogrammen- Ableitung von Programmeigenschaften, z.B.
Korrektheit- Ableitung korrekter Programme
Formulierung von Aussagen:
Verallgemeinerte Formel {} P {} , (*)
, logische Formeln, P Programmstück
Logische Formel Interpretation Aussage
Verallgemeinerte
Formel
Interpretation von (*) (partielle Korrektheit):
Wenn vor der Ausführung von P (interpretiert) galt und die Ausführung von P terminiert, dann gilt danach (interpretiert).
Fragen: Welche „Formulierungssprache“ verwenden
wir für und ? Wie setzen sich Aussagen zu komplexen
Programmfragmenten aus Aussagen der Komponenten zusammen?
Wie lassen sich Programmeigenschaften beschreiben oder ableiten?
Wie sind , und {} P {} zu interpretieren?
Komponenten der axiomatischen Semantik: Abstrakte Syntax der Programmiersprache Logisches System (L, A, R), L Sprache des
Systems, A L Axiome, R Schlussregeln Axiome und Schlussregeln zu Eigenschaften
der Programmiersprache Geeignete Interpretation für das logische
System
In imperativen Sprachen wird als logisches System i.d.R. die Prädikatenlogik erster Stufe verwendet.
Symbolmengen in der Prädikatenlogik: V Menge von Individuenvariablen Fm Menge von m-stelligen
Funktionssymbolen (m = 0: Individuen-konstanten)
true, false Pm, m = 1, 2, ... Menge von m-stelligen
Prädikatsymbolen {, , , , , , } ⌝ ∀ ∃ logische
Operationssymbole und Quantifikatoren ( ) , Hilfssymbole (unvollständig)
Terme (TR):
1. V TR, F0 TR
2. f Fm , t1,..., tm TR f(t1,..., tm ) TR
3. Keine anderen Elemente sind aus TR.
Formeln (FR):
1. true, false FR
2. q Pm , t1,..., tm TR q(t1,..., tm ) FR
3. , FR, x V ⌝, , , , x∀ , x∃ , (), FR
4. Keine anderen Elemente sind Formeln.
Verallgemeinerte Formel:
{} P {} , , logische Formeln,
P Programmstück
Axiomatische Semantik von BPS
Gegeben: geeignete abstrakte Syntax
Axiome und Schlussregeln nach Hoare (Auszug)
Axiom der skip-Anweisung:
{} skip {}
(Die skip-Anweisung verändert Programmeigenschaften nicht.)
Axiom für die Wertzuweisung V := E
(V Variable, E Ausdruck):
{P’} V := E {P} ,
wobei P’ aus P durch Ersetzen der nichtquantifizierten Auftreten von V durch E entsteht (P’ ist die schwächste Vorbedingung; P’ = P[V/E])
Verkettungsregel für Anweisungen A1 und A2:
{P} A1 {Q}, {Q} A2 {R}
{P} A1; A2 {R}
Regel für die while-Anweisung:
{PB} A {P}
{P} while B do A od {P not B}
P Schleifeninvariante
Regel für die if-Anweisung:
{ B} A1 {}, { B} A2 {⌝ }
{} if B then A1 else A2 fi {}
Implikationsregeln:
{P} S {Q}, Q R P R, {R} S {Q}
{P} S {R} {P} S {Q}
Ableitung von Eigenschaften
Begriff des Theorems:
Eine (verallgemeinerte) Formel ist ein Theorem, wenn für ein Beweis 0, 1,..., n existiert, wobei
n =
- und für i = 0, 1,..., n ist i entweder ein Axiom oder die Schlussfolgerung einer Schlussregel, deren Komponenten der Voraussetzung in 0, 1,..., i-1 enthalten sind.
Notation: ⊢
Interpretation von (verallgemeinerten) Formeln
Beweise sind syntaktische Manipulationen unter Verwendung eines Axiomen- und Schlussregelsystems.
Inwieweit drücken die bewiesenen Formeln wirkliche Eigenschaften unserer Programmfragmente aus?
Notwendigkeit einer geeigneten Interpretation
Beispiel:
x y Interpretation Die Werte der Integer-
variablen x sind Interpretation größer oder gleich
den Werten der
Integer- Größer-Gleich- Integervariablen y.
variablenVergleich für
mit best. Integerwerte
Belegungen
Wahre oder falsche Aussage in Abhängigkeit von den Belegungen für x und y.
Beispiel: { a > 0} a := (a – 1) {a 0}
Interpretation
Der Wert der Integer- Der Wert der Integervariablen a
Variablen a ist vor der ist nach der Abarbeitung der
Abarbeitung der Zuweisung größer oder gleich 0.
Zuweisung größer als 0.
Wenn die Variablenbelegung vor Abarbeitung der Zuweisung
a einen Wert größer als 0 zuordnet und die Abarbeitung
terminiert, dann ordnet die durch die Zuweisung neu
entstandene Variablenbelegung a einen Wert größer oder gleich
0 zu.
Interpretation (I) im Sinne der denotationalen Semantik
Bemerkung: Ausdrücke in BPS und logische Terme werden gleichgesetzt.
Konstantensymbol ( Individuenkonstante) k:≙kI(c) = Wert 〚 k 〛 (c) = k
(Die Interpretation kI einer Konstanten k bei beliebiger Variablenbelegung c liefert ihren Wert k.)
Variable x: xI(c) = Wert 〚 x 〛 (c) = c(x)
Funktionssymbol f Fm: fI ist eine m-stellige Operation
Beispiel: +I ist die Addition zweier Integerwerte
Term t: tI(c) = Wert 〚 t 〛 (c)
Prädikatsymbol p: pI ist ein m-stelliges Prädikat
Beispiel: <I ist der Kleiner-Vergleich zweier Integerwerte
Programmfragment P: PI = SD 〚 P 〛
(Die Interpretation eines Programmfragments ist seine denotationale Bedeutung.)
Formel : I [C p WF] , wobei gilt:
(q(t1, ..., tm))I(c) = qI(t1I(c), ..., tmI
(c)) , q Pm ,
t1, ..., tm TR
Beispiel: (x > 0)I(c) = c(x) >I 0
( ⌝ )I(c) = W I(c) = F , FR
Beispiel: ( (y > 0))⌝ I(c) = W (c(y) >I 0) = F
( )I(c) = F I(c) = I(c) = F , , FR
( )I(c) = W I(c) = I(c) = W , , FR
( )I(c) = F I(c) = W, I(c) = F , , FR
( x∀ )I(c) = W I(c´) = W für alle c´, die sich von c höchstens für x unterscheiden, FR
( x∃ )I(c) = W es existiert c´, das sich von c höchstens für x unterscheidet, und I(c´) = W
Verallgemeinerte Formel {} P {}:
- Partielle Korrektheit:
({} P {})I(c) = W
(I(c) = W, SD 〚 P 〛 (c) = c´ I(c´) = W)
- Totale Korrektheit:
({} P {})I(c) = W
(I(c) = W SD 〚 P 〛 (c) = c´, I(c´) = W)
Beispiel: ({a > 0} a := (a – 1) {a 0})I (c) = W
(c(a) >I 0) = W,
SD 〚 a := (a – 1) 〛 (c) = c´
= c{a/Wert 〚 a – 1 〛 (c)} = c{a/(c(a) – 1)}
(c´(a) I 0) = W)
Notation: ⊨I (c) Eine (verallgemeinerte) Formel ist
unter der Interpretation I bei Variablenbelegung c wahr (I(c) = W).
⊨I ist für jede Variablenbelegung wahr
(I ist ein Modell für ).
Probleme: sei eine beweisbare (verallgemeinerte)
Formel (Theorem), d.h. aus dem gegebenen Axiomen- und Schlussregelsystem ableitbar ( ⊦ ).
Existiert ein Modell für , d.h. eine Interpretation I so, dass I(c) = W für alle c?
Notation: ⊦ ⊨I ?
(Widerspruchsfreiheit, Konsistenz, Korrektheit des Axiomen- und Schlussregelsystems, Soundness)
A sei eine wahre Aussage über ein Programmfragment P.
Existiert zu P eine beweisbare verallgemeinerte Formel , deren Interpretation A liefert?Notation: ⊨I ⊦
(Vollständigkeit, Completeness)
Satz: Das Hoaresche Axiomen- und Schlussregelsystem ist für Pascal-ähnliche Sprachen widerspruchsfrei aber nicht vollständig.
Weitere SemantikartenAktionssemantik (P. Mosses)
Ziele: Praktisch nützliche Semantikdefinition für realistische
Programmiersprachen Kombination von Formalismus und guten praktischen
Elementen Spracherweiterung ohne Neuformulierung alter
Konstrukte Wiederverwendbarkeit der Bausteine
(Kompositionalität) Gute Lesbarkeit und Verständlichkeit
Aktion: Element der Datenverarbeitung
Elementare Aktionen, zusammengesetzte Aktionen (Kombination entsprechend algebraischen Gesetzen Ableitung von Eigenschaften)
Beispiele: Wert eines Identifikators
evaluate I: Identifier =
give the value bound to I or
give the number stored in the cell bound to I
Semantik einer Anweisungsfolge
execute 〚 S1: Statement ´´;´´ S2: Statement 〛 = execute S1 and then execute S2.
Semantik der Wertzuweisung
execute 〚 I: Identifier ´´:=´´ E: Expression 〛 =
(give the cell bound to I and evaluate E)
then store the given number 2 in the given cell 1.
Gemeinsame Beschreibungsmittel für Syntax und Semantik
VDL: Beschreibung von abstrakter Syntax und operationaler Semantik
Deduktive Regeln: Beschreibung einer strukturellen Syntax und einer strukturellen operationalen Semantik
Problem: Darstellung der Kontextbedingungen (statische Semantik)
Möglich z.B. durch partielle Semantikfunktionen oder über erweiterte kontextfreie Grammatiken
Verallgemeinerung kontextfreier Grammatiken - Zweistufengrammatik
Beispiel (modifizierte Notation):
1 <start> ::= <a hoch N> <b hoch N> <c hoch N>
2 <a hoch Ni> ::= a <a hoch N>
3 <b hoch Ni> ::= b <b hoch N>
4 <c hoch Ni> ::= c <c hoch N>
5 <a hoch i> ::= a
6 <b hoch i> ::= b
7 <c hoch i> ::= c
Definierte Sprache L: unter der Voraussetzung, dass L(N) = {i}* , ist L = {anbncn| n 1}
Komponenten von Zweistufengrammatiken: Hyperregeln: können als parametrisierte
kontextfreie Syntaxregeln oder als Regelmuster für kontextfreie Regeln betrachtet werden, wobei die Nichtterminale durch Hyperbegriffe ersetzt wurden
Beispiel: <a hoch Ni> ::= a <a hoch N> ist eine Hyperregel mit den Hyperbegriffen <a hoch Ni> und <a hoch N> sowie dem Parameter (Metabegriff) N
Metabegriffe: spielen die Rolle der Parameter in den Hyperregeln
Metaregeln: sind kontextfreie Syntaxregeln, deren Erzeugungen die Definitionsbereiche der Parameter (aus Metabegriffen abgeleitete Sprachen) festlegen
Beispiel: Der Definitionsbereich von N im obigen Beispiel ist L(N) = {i}* , d.h. die Menge aller natürlichen Zahlen im Einersystem. Diese Sprache könnte nun durch kontextfreie Metaregeln beschrieben werden:
N | Ni
Erzeugung von Wörtern: Ableitung von kontextfreien Syntaxregeln aus
den Hyperregeln durch konsistentes Ersetzen der Metabegriffe (Parameter) durch aus ihnen abgeleitete Wörter (Wertebereiche der Parameter)
Beispiel: aus obigen Regeln abgeleitete Regeln
1´ <start> ::= <a hoch iii> <b hoch iii> <c hoch iii>
(N wurde durch iii in Regel 1 ersetzt)
2´ <a hoch iii> ::= a <a hoch ii>
(N wurde durch ii in Regel 2 ersetzt)
2´´ <a hoch ii> ::= a <a hoch i>
(N wurde durch i in Regel 2 ersetzt)
Analog könnten 3´, 3´´, 4´ und 4´´ abgeleitet werden.
Wortableitung unter Verwendung der erzeugten kontextfreien Regeln
Beispiel: Erzeugung von a a a b b b c c c
<start> 1´ <a hoch iii> <b hoch iii> <c hoch iii>
2´ a <a hoch ii> <b hoch iii> <c hoch iii>
3´,4´ a <a hoch ii> b<b hoch ii> c<c hoch ii>
2´´,3´´,4´´ a a<a hoch i> b b<b hoch i> c c<c hoch i>
5,6,7 a a a b b b c c c
Darstellung von Kontextbedingungen (prinzipiell):
Nutzung des Prinzips der konsistenten Ersetzung eines Parameters innerhalb einer Hyperregel
Beispiel:
<Ausdruck: T> ::= <Ausdruck: T> + <Ausdruck: T>
L(T) = {int, real}
Der +-Operator verknüpft entweder zwei Integerausdrücke oder zwei Realausdrücke zu einem Integerausdruck bzw. Realausdruck.
Nutzung spezieller Hyperbegriffe mit Erzeugung des leeren Wortes (primitive Prädikate)
Beispiel: Die Gleichheit zweier Buchstaben kann durch das Prädikat <where X is identical with Y> zusammen mit der Hyperregel
<where X is identical with X> ::= (*)
und den Definitionsbereichen für X und Y
L(X) = L(Y) = {a, b, ..., z}
definiert werden.
Mögliche Fälle:
1. X und Y vertreten den gleichen Buchstaben, z.B. i. Dann kann aus der Hyperregel (*) die kontextfreie Regel
<where i is identical with i> ::= abgeleitet werden.
2. X und Y vertreten unterschiedliche Buchstaben, z.B. k und l. Es kann zwar
<where k is identical with l>
aber keine kontextfreie Regel abgeleitet werden. Das abgeleitete Nichtterminal ist eine Sackgasse.
Die Erzeugung des leeren Wortes signalisiert Erfüllung und eine Sackgasse Nichterfüllung einer Eigenschaft.
Beispiel: Erfüllung der Kontextbedingung:
In der gleichen Vereinbarungsfolge darf ein Identifikator höchstens einmal vereinbart werden.
Vorgehen: Erstellung einer kontextfreien Grammatik zur
Erzeugung von Vereinbarungsfolgen Einführung von Parametern:
- TABLE: steht für eine Tabelle aller vereinbarten Identifikatoren zusammen mit ihrem Typ
- ENTRY: symbolisiert einen Eintrag in der Tabelle und besteht aus einem Identifikator (ID) zusammen mit seinem Typ (TYPE)
Einführung eines Prädikats für die Kontextbedingung (<where ENTRY is not in TABLE>)
Einführung von Hilfsprädikaten
(z.B. <where ID is not ID1>) Definition der Parameterwerte durch kontextfreie
Syntaxregeln oder durch kontextfreie Sprachen
Hyperregeln (Auszug)1 <declaration list with ENTRY TABLE> ::=
var <variable declaration with ENTRY> ; <dec list with TABLE>
<where ENTRY is not in TABLE>
2 <dec list with ENTRY TABLE> ::=
<variable declaration with ENTRY> ; <dec list with TABLE>
<where ENTRY is not in TABLE>
3 <dec list with > ::=
4 <variable declaration with ID and TYPE> ::=
<type with TYPE> <identifier with ID>
5 <type with bool> ::= bool
6 <type with int> ::= int
7 <where ENTRY is not in > ::= 8 <where ID and TYPE is not in ID1 and TYPE1> ::=
<where ID is not ID1>
9 <where ENTRY is not in ID and TYPE TABLE> ::=
<where ENTRY is not in ID and TYPE>
<where ENTRY is not in TABLE>
Mit Hilfe abgeleiteter Regeln lässt sich
var int x; bool y;
erzeugen, aber nicht
var int x; bool x; (Sackgasse <where x is not x>)
Zweistufengrammatiken können auch genutzt werden um Operationen über ihre Eigenschaften (vergl. ADT) zu definieren.
Beispiel: Multiplikation natürlicher Zahlen
Eigenschaften:- a * b = c a * (b – 1) = c – a- a * 0 = 0
Umsetzung in Hyperregeln:
1 < NL1 N ist N mal NL2 i> ::= <NL1 ist N mal NL2>
2 <NULL ist N mal NULL> ::= L(NULL) = {} L(N) = {i}+ L(NL1) = L(NL2) = L(N) {}
Charakteristika von Zweistufengrammatiken: Kontextfreie Grammatiken mit parametrisierten
syntaktischen Elementen Definitionsbereiche der Parameter: kontextfreie
Sprachen (beschrieben durch eine kontextfreie Grammatik – Metagrammatik)
Ableitungsbegriff:
- Ableitung kontextfreier Syntaxregeln aus den Hyperregeln
- Nutzung der abgeleiteten Regeln zur Spracherzeugung
Mächtigkeit: Definition von Typ-0-Sprachen
Vor- und Nachteile von Zweistufengrammatiken:
+ Möglichkeit der kompletten Beschreibung einer Programmiersprache
- Zu allgemein, nicht ausführbar, schwer sinnvoll einschränkbar
Entwicklungen für praktische Anwendungen:
Affixgrammatiken, CDL, GSF, Erweiterte Affixgrammatiken
Attributierte Grammatiken
Beispiel (nach Irons):
a =:: letter {Ax}
b =:: letter {Bt}
letter =:: iden {P1}
iden letter =:: iden {P1 P2‖t m‖}
iden =:: sinnvar {P1 ‖x y‖}
(iden =:: sinnvar {₤1 ‖ P1‖})
Attributierte Grammatik nach KnuthDefinition
Kontextfreie Basisgrammatik B = (N, T, P, S) mit Nichtterminalen N, Terminalen T, Startsymbol S und Regelmenge P
X N: A(X) = Ae(X) As(X), Ae(X) As(X) =
A(X) Attributmenge zu X
Ae(X) (As(X)) ererbte (synthetisierte) Attribute zu X
A(X) = As(X) für X = S und X T
a A(X): Da Definitionsbereich von a
p: X0 X1 X2 ...Xn
a(Xi), a A(Xi) Auftreten des Attributs a beim Element Xi in der Regel p (auch Xi.a)
Menge semantischer Regeln Fp zur Regel p:
Für alle a As(X0): a(X0) = fpa,0(aa
01,..., aa0ka
),
aa01,..., aa
0ka A(p) = Un
i=0 A(Xi)
Für alle a Ae(Xi), i=1,...,n: a(Xi) = fpa,i(aa
i1,..., aaika
),
aai1,..., aa
ika A(p) = Un
i=0 A(Xi)
Definierte Attribute einer Regel p: As(X0), Ae(Xi), i=1,...,n
Angewandte Attribute einer Regel p: Ae(X0), As(Xi), i=1,...,n
Eingabe/Abhängigkeitsmenge von a: {aai1,..., aa
ika}
Attributierte Grammatik in Normalform: Eingabemengen enthalten nur angewandte Attribute
Synthetisierte Attribute
Ererbte Attribute
Fq
Fp
Beispiel (Knuth)
Basisgrammatik (Struktur der Binärzahlen)
1: B 0 einzelne Binärziffer
2: B 1
3: L B Folge von Binärziffern
4: L1 L2B
5: N L ganze Binärzahl
6: N L1.L2 gebrochene Binärzahl
Beispiel (Knuth) - Fortsetzung
Semantische Regeln
F1: b(B) := 0
F2: b(B) := 2p(B)
F3: b(L) := b(B)
l(L) := 1
p(B) := p(L)
F5: b(N) := b(L)
p(L) := 0
Beispiel (Knuth) - Fortsetzung
Semantische Regeln
F4: b(L1) := b(L2) + b(B)
p(B) := p(L1)
p(L2) := p(L1) + 1
l(L1) := l(L2) + 1
F6: b(N) := b(L1) + b(L2)
p(L1) := 0
p(L2) := -l(L2)
Beispiel (Knuth) – AbhängigkeitsgraphenD(1): p B b D(2): p B b
0
0 1
D(3): p L l b D(5): N b
0
1
p B b p L l b
Beispiel (Knuth) – AbhängigkeitsgraphenD(4): p L l b
p L l b p B b
D(6): N b
0
.
p L l b p L l b
Beispiel (Knuth) – AbhängigkeitsrelationN b
p L l b . p L l b
p L l b p B b
p L l b p B b
p B b 0
p B b 1
1 0
Attributierte GrammatikenAnwendung in Compiler-Compilern
Compilerbeschreibung in Form einer attributierten Grammatik:
- Syntax der Programmiersprache als kontextfreie Basisgrammatik
- Statische und dynamische Semantik durch Attribute und semantische Regeln
Automatische Compilererzeugung durch Compiler-Compiler
Arbeitsweise des erzeugten Compilers: Erzeugung eines (abstrakten) Syntaxbaums Dekorierung des Syntaxbaums durch
Attributwerte unter Verwendung eines geeigneten Berechnungsalgorithmus´ (muss die durch die Attributabhängigkeiten induzierte Halbordnung beachten)
Beispiel – Statische Semantik von BPS´ (Ausschnitt)
<Ausdruck> ::= <Konstante>
Typ(<Ausdruck>) := Typ(<Konstante>)
<Ausdruck> ::= <Variable>
Typ(<Ausdruck>) :=
Symtab (Tabelle(<Ausdruck>), Text(<Variable>)
<Ausdruck>0 ::= (<op1> <Ausdruck>1)
Tabelle(<Ausdruck>1) := Tabelle(<Ausdruck>0)
Typ(<Ausdruck>0) := if Typ(<Ausdruck>1) = „int“
then „int“ else „undef“ fi
<Ausdruck>0 ::= (<Ausdruck>1 <op1> <Ausdruck>2)
Tabelle(<Ausdruck>1) := Tabelle(<Ausdruck>0)
Tabelle(<Ausdruck>2) := Tabelle(<Ausdruck>0)
Typ(<Ausdruck>0) :=
Typ(Art(<op2>), Typ(<Ausdruck>1), Typ (<Ausdruck>2))
<op1> ::= +|-
<op2> ::= +|-|/|* Art(<op2>) := „arit“
<op2> ::= =||| Art(<op2>) := „Vergl“
<op2> ::= || Art(<op2>) := „log“
Attributierte GrammatikenPraktische Probleme
Reihenfolge der Berechnung der Werte der Attributauftreten effiziente Berechnungsalgorithmen
Vermeidung/Detektion von Zyklen der Attributabhängigkeiten Einschränkungen in der Definition
Speicherplatzbedarf für semantische Bäume Vermeidung der kompletten Abspeicherung
S-attributierte Grammatik
Besitzt ausschließlich synthetisierte Attribute Berechnung der Attribute von den Blättern zur Wurzel unter Nutzung der Kellertechnik
Jede zyklenfreie attributierte Grammatik kann in eine äquivalente S-attributierte Grammatik transformiert werden.
Beachte Analogie zu YACC (Bison) – Grammatiken!
Berechnungsalgorithmus im Einpassverfahren
Voraussetzung: Alle ererbten Attribute von u sind berechnet; p: X0 X1 ...Xnp
, vp = vp(1),..., vp(np)
procedure eval(u);
begin for i := 1 to np
do berechne alle ererbten Attribute von u.vp(i);
eval(u.vp(i)
od;
berechne alle synthetisierten Attribute von u
end
Spezialfall: vp = 1,..., np
e0 X0 s0
e1 X1 s1 e2 X2 s2 enp Xnp snp
eval(u)
eval(u.1), ..., eval(u.np)
