Upload
irene-miles
View
52
Download
3
Embed Size (px)
DESCRIPTION
Semantische Analyse und attributierte Grammatiken. Sarah Al-Itaibi. Gliederung. Einordnung der semantischen Analyse in die Phasen des Übersetzers Einführung in die semantische Analyse des Quellprogramms Zentrale Aufgaben der semantischen Analyse Einführung in attributierte Grammatiken - PowerPoint PPT Presentation
Citation preview
WIR
TS
CH
AF
TS
INF
OR
MA
TIK
WestfälischeWilhelms-Universität Münster
WIRTSCHAFTSINFORMATIK
Semantische Analyse und Semantische Analyse und attributierte Grammatikenattributierte Grammatiken
Sarah Al-Itaibi
2
WIRTSCHAFTSINFORMATIK
1. Einordnung der semantischen Analyse in die Phasen des Übersetzers
2. Einführung in die semantische Analyse des Quellprogramms
3. Zentrale Aufgaben der semantischen Analyse
4. Einführung in attributierte Grammatiken
5. Auswertung semantischer Regeln
6. Zusammenfassung
GliederungGliederung
3
WIRTSCHAFTSINFORMATIK
Einordnung der semantischen Analyse Einordnung der semantischen Analyse in die Phasen des Übersetzersin die Phasen des Übersetzers
Phasen des Übersetzers:Lexikalische Analyse
Code-Optimierung
Code-Erzeugung
Zwischencode-Erzeugung
Semantische Analyse
Syntaxanalyse
Quellprogramm
Zielprogramm
4
WIRTSCHAFTSINFORMATIK
Einführung in die semantische Analyse Einführung in die semantische Analyse des Quellprogrammsdes Quellprogramms
Aufbau einer künstlichen Sprache erfolgt nach festen Regeln (Syntax, Grammatik).
Wörter und Sätze besitzen wohldefinierte Bedeutungen (Semantik).
Wichtige Aufgabe bei der Übersetzung: Beibehaltung des Bedeutungsgehaltes.
Beispiele aus der deutschen Sprache:1. Der Hecht frisst die Forelle.
2. Das Plankton frisst den Hecht.
Die Wirkung eines Satzes ergibt sich aus seiner Bedeutung.
5
WIRTSCHAFTSINFORMATIK
Einführung in die semantische Analyse Einführung in die semantische Analyse des Quellprogrammsdes Quellprogramms
Semantische Analyse überprüft, ob die Teile eines Programms von der Bedeutung her zusammenpassen.
Beispiel: Überprüfung der Anzahl der Parameter bei Prozeduraufrufen.
Typüberprüfung bei Zuweisungen: Volumen := Fläche * Höhe
Quellprogramm wird auf semantische Fehler untersucht: Beispiel: Zuweisen eines Buchstabens an eine Integer-Variable
(Typkonflikt).
6
WIRTSCHAFTSINFORMATIK
Einführung in die semantische Analyse Einführung in die semantische Analyse des Quellprogrammsdes Quellprogramms
Eingabe: Syntaxbaum.
Ergänzung des Syntaxbaums um semantische Informationen
(Attribute) Bewerteter Syntaxbaum.
Verschmelzung von Syntaxanalyse und semantischer Analyse
Übergabe eines Syntaxbaumes ist hinfällig.
7
WIRTSCHAFTSINFORMATIK
Einführung in die semantische Analyse Einführung in die semantische Analyse des Quellprogrammsdes Quellprogramms
Unterscheidung zwischen statischer und dynamischer semantischer Analyse.
1. Statische semantische Analyse:- Zur Übersetzungszeit
- Semantische Eigenschaften werden mit Hilfe des Programmtextes bestimmt
- Semantische Eigenschaften: Deklaration jedes verwendeten Bezeichners Abwesenheit von Doppeldeklarationen Korrekte Verwendung jeder Variable entsprechend ihres
Datentyps
8
WIRTSCHAFTSINFORMATIK
Einführung in die semantische Analyse Einführung in die semantische Analyse des Quellprogrammsdes Quellprogramms
2. Dynamische semantische Analyse:
Zur Laufzeit.
Semantische Eigenschaften werden durch Ausführung des Programms mit Eingabedaten herausgefunden
Der Typ eines Ausdrucks wird erst bei der Auswertung, zur Laufzeit, bekannt.
9
WIRTSCHAFTSINFORMATIK
Zentrale Aufgaben der semantischen AnalyseZentrale Aufgaben der semantischen Analyse
1. Bezeichneridentifikation:- Zur Identifikation dienen Definitionen und Gültigkeitsregeln der
Programmiersprache.
- Definition: Einführung des Bezeichners als Benennung eines Objektes.
- Aufgabe: Zu jedem angewandten Auftreten des Bezeichners die
gültige Definition bestimmen.
- Jede Definition eines Bezeichners hat einen Gültigkeitsbereich.
10
WIRTSCHAFTSINFORMATIK
Zentrale Aufgaben der semantischen AnalyseZentrale Aufgaben der semantischen Analyse
Gültigkeitsbereich einer Definition ist der Abschnitt des Quellprogramms, in dem Anwendungen des Bezeichners dieser Definition zugeordnet werden.
Gültigkeitsregeln bestimmen Gültigkeitsbereich.
Beispiele für Gültigkeitsregeln: Verdeckungsregel. Keine Anwendung eines Bezeichners vor seiner Definition.
Als Hilfsmittel dient die Symboltabelle.
Charakteristische Fehlersituationen: Unzulässige Mehrfachdefinitionen im gleichen Block. Angewandte Bezeichner ohne gültige Definition.
11
WIRTSCHAFTSINFORMATIK
Zentrale Aufgaben der semantischen AnalyseZentrale Aufgaben der semantischen Analyse
2. Typüberprüfung:- Typinformationen können bei der Codegenerierung benötigt
werden.
- Sicherstellung der Typkonsistenz eines Programms.
- Überprüfung der Typkonsistenz erfolgt durch einen bottom-up Durchlauf des Baumes.
- Typanpassung von Ausdrücken.
12
WIRTSCHAFTSINFORMATIK
Einführung in attributierte GrammatikenEinführung in attributierte Grammatiken
Eine attributierte Grammatik ist die am häufigsten verwendete Technik zur formalen Beschreibung von Übersetzungsprozessen.
Sie wurden von Knuth im Jahre 1968 eingeführt.
Definition:Sie ist ein Quadrupel AG = (G, A, R, K) bestehend aus:
1. Einer kontextfreien Grammatik G = (VN, VT, P, S).
2. Einer endlichen Attributmenge A.
3. einer endlichen Menge semantischer Regeln R.
4. einer endlichen Menge von Kontextbedingungen K.
Jedem Symbol X aus VN VT werden null oder mehr Attribute zugeordnet
Jeder Produktionsregel p aus P werden ebenfalls null oder mehr semantische Regeln und Kontextbedingungen zugeordnet.
13
WIRTSCHAFTSINFORMATIK
Einführung in attributierte GrammatikenEinführung in attributierte Grammatiken
Folgendes Beispiel dient dem intuitiven Verständnis der attributierten Grammatiken:
Produktionsregel:
pOpr: Ausdruck lOpd Opr rOpd
Semantische Regel:
Ausdruck.Typ:= opr_identif(Opr.Symbol, lOpd.Type, rOpd.Type)
Ausschnitt eines bewerteten Syntaxbaumes:
Typreal
Symbol+
Typinteger
Typreal
LOpd
Opr
rOpd
pOpr
Ausdruck
14
WIRTSCHAFTSINFORMATIK
Einführung in attributierte GrammatikenEinführung in attributierte Grammatiken
Jedes Attribut hat einen Namen und einen Wert.
Attribute können repräsentieren: String, Zahl, Typ oder einen Speicherplatz.
Attributarten:1. Synthetisierte Attribute:
Werden bei der Erkennung eines Symbols erzeugt. Wert errechnet sich aus den Werten der Attribute der
Nachfolgerknoten. Lexikalischer Analysator bestimmt die synthetisierten Attribute der
Terminalsymbole. Mittels dieser Attribute können semantischen Informationen von
den Blättern bis zur Wurzel weitergereicht werden.
15
WIRTSCHAFTSINFORMATIK
Einführung in attributierte GrammatikenEinführung in attributierte Grammatiken
2. Ererbte Attribute: Werden einem Nichtterminalsymbol vor seiner Erkennung
mitgegeben. Wert errechnet sich aus den Werten der Attribute des
Vorgängerknotens und/oder Geschwisterknoten. Startsymbol hat keine ererbten Attribute. Mittels dieser Attribute können semantische Informationen von den
Nachfolgern der Wurzel bis zu den Blättern vererbt werden.
Auswertung der Attribute: Code generieren.
Informationen in einer Symboltabelle abspeichern.
Fehlermeldungen ausgeben.
16
WIRTSCHAFTSINFORMATIK
Einführung in attributierte GrammatikenEinführung in attributierte Grammatiken
Kontextbedingungen: Sind Bedingungen der statischen Semantik für die Attribute. Beschreiben Beziehungen zwischen Attributen bzw. Elementen der
Sprache. Zeitpunkt der Prüfung wird durch ihre Stellung in der Grammatikregel
festgelegt. Ein Syntaxbaum repräsentiert ein übersetzbares Programm, wenn alle
Kontextbedingungen erfüllt sind. Bedingung wird durch eine Relation zwischen Attributen ausgedrückt. Zum Beispiel:
„In einer Wertzuweisung müssen linke und rechte Seite vom selben Typ sein“
Beispiel: Bedingung einer Sprache: „alle Variablen müssen explizit deklariert
sein“. PROCEDURE P
VAR a, b : INTEGERx := yEND P
17
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Bei der Auswertung muss der Syntaxbaum auf bestimmten Wege durchlaufen werden und dabei müssen die semantischen Regeln ausgewertet werden.
Sämtliche Attributwerte, von denen eine semantische Regel oder Kontextbedingung abhängt, müssen berechnet sein, vor Anwendung der Regel.
Bei zyklischen Abhängigkeiten zwischen Attributen können deren Werte effektiv nicht berechnet werden.
Zu jedem Syntaxbaum, der Attribute enthält, gibt es einen Abhängigkeitsgraphen.
Abhängigkeitsgraph zeigt die Abhängigkeit zwischen den Attributen des Baumes, die sich aus den semantischen Regeln ergeben.
18
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Attribute bilden Knoten des Graphen.
Gerichtete Kanten geben die in den semantischen Regeln ausgedrückten Abhängigkeiten an.
Attributierte Grammatik heißt wohldefiniert, wenn die Abhängigkeitsgraphen zu allen Syntaxbäumen zyklenfrei sind.
Ein Abhängigkeitsgraph setzt sich immer aus den produktionslokalen Abhängigkeitsgraphen der angewandten Produktionen zusammen.
Beispiel einer attributierten Grammatik zur Umrechnung von Binärzahlen in Dezimalzahlen:
Attribut v: berechneter Wert. Attribut r: Rang bzw. relative Position des BIT zum binären Punkt. Attribut l: Länge des Bit-String.
19
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Attribute Grammar Bin_to_Dec:Nonterminals: {N, BIN, BIT}Attributes: syn l with BIN domain int;
Syn v with N, BIN, BIT domain real;Inh r with BIN, BIT domain int;
Production: Semantik Functions:
1: N BIN.BIN N.v = BIN1.v + BIN2.v
BIN1.r = 0
BIN2.r = -BIN2.l
2: BIN BIN BIT BIN0.v = BIN1.v + BIT.v
BIN0.l = BIN1.l + 1
BIN1.r = BIN0.r + 1
BIT.r = BIN0.r
3: BIN ε BIN.v = 0 BIN.l = 0
4: BIT 1 BIT.v = 2BIT.r
5: BIT 0 BIT.v = 0
20
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Produktionslokale Abhängigkeitsgraphen:
Dp(1):
Dp(5):Dp(4):Dp(3):
Dp(2):
N v
BINr v l BIN v BINv
BINv l
l l
r
rr. BITr v
BINr v l r BIT v
1
BIT vr
0
21
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Syntaxbaum mit Abhängigkeitsgraph zum Wort „10.01“:
N v
.BINr v l BINr lv
BIN BIN vv ll rr BITBIT rr vv
0 1
rrrr BIN BIN vv vv ll BITBIT
1 0
22
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Auswertung erfolgt:1. Nach erhalten des um die Attribute erweiterten Syntaxbaumes.2. Parallel zur Syntaxanalyse, gesteuert durch den Parser.
Auswertungsschritte bei gegebenem Syntaxbaum:1. Bildung des Abhängigkeitsgraphen und test auf Zyklenfreiheit.2. Bestimmung der Auswertungsordnung (Besuchsfolge, topologische
Sortierung).3. Auswertung der Attribute gemäß der Auswertungsordnung.
Findet die Auswertung währen der Syntaxanalyse statt, dann ist die Auswertungsreihenfolge abhängig von der Reihenfolge, in der die Knoten erzeugt werden.
Ordnung der Attribute im vorherigen Beispiel: Für BIN: l r v Für BIT: r v
23
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Auswertung des Beispiels:1. Top-down Durchlauf, gefolgt von einem bottom-up Durchlauf zur
Auswertung von l.
2. Top-down Durchlauf zur Auswertung von r.
3. Bottom-up Durch lauf zur Berechnung von v.
N
.BIN
BIN BIN BITBIT
0 1
BIN BIN BITBIT
1 0
BIN (v = 0,25; l = 2; r = -2)
(v = 0; l = 1; r = -1)
(v = 0,25;r = -2)
(v = 2; l = 2; r = 0)
(v = 2,25)
(v = 2; l = 1; r = 1)
(v = 0; r = 0)
(v = 0; l = 0; r = 2)
(v = 0; l = 0; r = 0)
(v = 0; r = -1)
(v = 2; r = 1)
24
WIRTSCHAFTSINFORMATIK
Auswertung semantischer RegelnAuswertung semantischer Regeln
Syntaxgesteuerte Definition: Notation um semantische Regeln mit Produktionsregeln zu verbinden.
Seiteneffekte in semantischen Regeln erlaubt, wie das Drucken eines Wortes.
Beispiel: S-attributierte Definition
L-attributierte Definition
Restriktion bei L-attributierten Definitionen: Jedes ererbte Attribut eines Knotens hängt nur von ererbten Attributen
des Vaterknotens und der linken Geschwisterknoten ab.
25
WIRTSCHAFTSINFORMATIK
ZusammenfassungZusammenfassung
Semantische Analyse notwendig um den Bedeutungsgehalt beizubehalten.
Wichtigste Aufgaben der semantischen Analyse sind die Typüberprüfung und die Bezeichneridentifikation.
Attributierte Grammatiken dienen der Verbreitung semantischer Informationen in Syntaxbäumen.
Attributierte Grammatiken definieren, wie in einem beliebigen Syntaxbaum alle Attribute berechnet werden können.
Auswertung der Attribute kann parallel zur Syntaxanalyse erfolgen oder nach erhalt des attributierten Syntaxbaumes.