Upload
kioshi
View
24
Download
0
Embed Size (px)
DESCRIPTION
Vorlesung Compilertechnik Sommersemester 2009. Kontextprüfung M. Schölzel. Aufgabe der Kontextprüfung. Zu Erinnerung: Programmiersprachen sind im Allgemeinen Typ-1 Sprachen. Aus Effizienzgründen wird aber eine Obermenge dieser Sprache durch eine Typ-2 – Grammatik beschrieben. - PowerPoint PPT Presentation
Citation preview
Vorlesung CompilertechnikSommersemester 2009
Kontextprüfung
M. Schölzel
2
Aufgabe der Kontextprüfung
Zu Erinnerung: Programmiersprachen sind im Allgemeinen
Typ-1 Sprachen. Aus Effizienzgründen wird aber eine
Obermenge dieser Sprache durch eine Typ-2 – Grammatik beschrieben.
Es gibt Programmtexte, die der kontextfreien Syntax entsprechen, aber kein Text der Programmiersprache sind.
Eliminierung der Quelltexte, die der kontextfreien Syntax entsprechen, aber nicht der Syntax, der Typ-1 – Sprache.
3
Dynamische und Statische Eigenschaften
Eine zu prüfende Eigenschaft eines Konstrukts einer Programmiersprache wird als statische (semantische) Eigenschaft bezeichnet, falls:
für jedes Vorkommen dieses Konstrukts in jedem Programm der Wert der Eigenschaft in diesem Programm für alle Programmausführungen konstant ist und
für jedes Vorkommen des Konstrukts in einem syntaktisch korrekten Programm der Wert der Eigenschaft berechnet werden kann.
Andernfalls handelt es sich um eine dynamische (semantische) Eigenschaft.
Die Kontextprüfung behandelt nur statische Eigenschaften.
4
Typische statische/dynamische Eigenschaften
Beispiele für statische Eigenschaften: Verwendete Bezeichner müssen deklariert worden sein. Bezeichner dürfen nur einmal deklariert werden. Anzahl und Typ der aktuellen Parameter beim
Funktionsaufruf muss mit Anzahl und Typ der formalen Parameter übereinstimmen.
Operanden einer Operation müssen mit kompatiblen (oder denselben) Typen deklariert worden sein.
Fälle in einer Mehrfachauswahl müssen verschieden sein. Beispiele für dynamische Eigenschaften:
Wert einer Variablen. Exakter Typ eines referenzierten Objekts. Wird eine bestimmte Anweisung ausgeführt.
5
Abgrenzung der Kontextprüfung
Kontextprüfung erforderlich für Eigenschaften, die sich nicht durch Typ-2-Grammatiken beschreiben lassen.
In der Praxis: Eigentlich kontextfrei beschreibbare Eigenschaften werden auch durch die Kontextprüfung überprüft.
Dadurch Vereinfachung der kontextfreien Syntax.
Beispiel: break-Anweisung nur innerhalb einer Schleife oder switch-Anweisung zulässig.
6
Einbettung der Kontextprüfung in den Compiler
Kontextbedingungen können an verschiedenen Stellen geprüft werden:
Sind nur wenige und einfache Kontextbedingungen zu prüfen, kann dies direkt während der Analyse des Quelltextes geschehen; z.B. beim Aufbau einer Symboltabelle während des Parsens kann auf Mehrfachdeklarationen geprüft werden.
Als separater Schritt nach dem Aufbau des Syntaxbaums. Während der Erzeugung des Zwischencodes. Verteilt in mehreren dieser Phasen
ParserScannerToken Zwischen-
codeerzeu-gung
Syntaxbaum
Kontextprüfung
Maximallänge von Bezeichnern
Mehrfachdeklaration von Bezeichnern
Typverträglichkeit in Ausdrücken
Maximallänge von BezeichnernMehrfachdeklaration von BezeichnernTypverträglichkeit in Ausdrücken
7
Ein Rahmenwerk zur Kontextprüfung
Kontextprüfung kann vollständig auf der Datenstruktur des (abstrakten) Syntaxbaums durchgeführt werden.
Phase 1: Berechnung der Werte der Eigenschaften: Für die zu prüfenden Eigenschaften werden an den Knoten des Baums
Attributexemplare angeheftet. Berechnung der Werte dieser Attributexemplare durch semantische
Funktionen aus den Werten anderer Attributexemplare im Baum. Phase 2: Prüfen der Kontextbedingung
Durch geeignete Prädikate werden die berechneten Werte der zu prüfenden Eigenschaften ausgewertet.
Formales Modell für dieses Vorgehen sind attributierte Grammatiken:
Attribute repräsentieren Eigenschaften. Attributexemplare speichern im Syntaxbaum den Wert einer
Eigenschaft. Ein Attributvorkommen ist das Vorkommen eines Attributs an einem
Symbol einer Grammatikregel. Die funktionalen Abhängigkeiten zwischen den Attributexemplaren im Syntaxbaum werden durch Funktionen auf den Attributvorkommen definiert.
8
Attributierte Grammatiken
Es sei G = (, M, R, S) eine kfG. G wird zu einer attributierten Grammatik erweitert durch die Festlegung von:
einer Attributmenge , einer Zuordnung einer Menge zu jedem Attribut a
durch D(a), Funktionen inh : M () und syn : M () mit syn(x)
inh(x) = und attr(x) = syn(x) inh(x) für jedes x M,
der Angabe einer semantischen Funktion a[A,i],k : D(bu1
) … D(bun) D(a) für jede Regel A [A,i] und
jedes Vorkommen eines Attributs a inh([A,i,k-1]) mit 1 k |[A,i]| und jedes Vorkommen eines Attributs a syn(A) mit k = 0, wobei jedes bui
ein Attributvorkommen am ui-ten Symbol der Regel A [A,i] ist.
9
Notationen
Wir sagen a hat ein Vorkommen am Symbol xj M, in der Regel x0 x1… xn falls a attr(xj). Schreibweise: a[x
0,i],j für x1…xn = [x0,i] bzw. aj,
falls die Regel aus dem Kontext hervorgeht. In einer Regel x0 x1… xn heißt ein Attributvorkommen ai definierendes
Vorkommen, falls i = 0 und a syn(x0) oder 1 i n und a inh(xi)
Alle anderen Attributvorkommen heißen angewandte Vorkommen. Eine attributierte Grammatik ist in Normalform, wenn alle Argumente aller
semantischen Funktionen angewandte Attributvorkommen sind. Im Folgenden betrachten wir nur noch attributierte Grammatiken in Normalform.
Attribute a syn(xi) heißen synthetisierte Attribute. Attribute a inh(xi) heißen ererbte Attribute. Terminalsymbole dürfen auch synthetisierte Attribute besitzen. Die Werte
dieser Attributvorkommen werden durch den Scanner definiert. Außerdem sei eine Menge von Attributen, für die gilt: k D(k) =
{0,1}. Diese Attribute werden verwendet, um die Gültigkeit von Kontextbedingungen explizit sichtbar zu machen.
10
Semantik einer attributierten Grammatik
Es sei (B,) der konkrete Syntaxbaum zu einem Wort w der kfG G. Ein Knoten n und seine Söhne n.i seien mit den Symbolen der Regel x0
x1… xk beschriftet. Für jedes Attributvorkommen a0 attr(x0) existiert ein Attributexemplar an
am Knoten n und für jedes Attributvorkommen ai attr(xi) (1 i k) existiert ein Attributexemplar an.i-1 am Knoten n.i-1.
Der Wert eines Attributexemplars an im Syntaxbaum wird mit val(an) bezeichnet, wobei val(an) D(a).
Für jedes Attributexemplar an eines synthetisierten Attributvorkommens an einem Terminalsymbol (Morphem) x gilt: val(an) := val(x), wobei (x,val(x)) das vom Scanner erzeugt Token zum erkannten Morphem x ist.
Für jedes Attributexemplar an eines synthetisierten Attributvorkommens a0 mit a[A,i],0(bu1
,…, bum) an einem Knoten n mit den Söhnen n.0,…,n.k gilt:
val(an) = a[A,i],0(val(bn1),…,val(bnm)), wobei nj = n, falls uj = 0, sonst nj = n.u1-1
Für jedes Attributexemplar an.z-1 eines ererbten Attributvorkommens az mit a[A,i],z(bu1
,…,bum) an einem Knoten n.z-1 mit dem Vater n und den
Geschwistern n.0,…,n.k gilt: val(an.z-1) = a[A,i],z(val(bn1),…,val(bnm)),
wobei nj = n, falls uj = 0, sonst nj = n.u1-1 Für die Attributexemplare eines Syntaxbaums ergibt sich damit ein
Gleichungssystem, das Abhängigkeiten zwischen den Attributexemplaren erzeugt.
11
Attribut, Attributvorkommen, Attributexemplar
Ein Attribut kann Vorkommen in mehreren Regeln und in jeder Regel wiederum in verschiedenen Metasymbolen haben.
Ein Attributvorkommen bei einem Symbol einer Regel kann mehrere Exemplare im Syntaxbaum besitzen, wenn die entsprechende Regel im Syntaxbaum mehrfach angewendet wurde.
Semantische Funktionen sind für jedes Attributvorkommen definiert, da die entsprechende Aktion nicht an das Attribut sondern die Regel und das Grammatiksymbol, an dem das Attribut auftritt, gebunden sein soll. Diese semantischen Funktionen werden auf die Attributexemplare an Knoten im Syntaxbaum angewendet; entsprechend der Regel, die an diesem Knoten angewendet wurde.
Es entsteht damit ein Gleichungssystem, in dem: der Wert eines ererbten Attributexemplars an einem Knoten n ergibt sich somit aus
den Werten von Attributexemplaren an n, am Vater von n und an den Brüdern von n. der Wert eines synthetisierten Attributexemplars an einem Knoten n ergibt sich aus
den Werten von Attributexemplaren an n und den Söhnen von n. Das Gleichungssystem besitzt eine eindeutige Lösung, falls das
Gleichungssystem nicht rekursiv ist (Beispiel). Die attributierte Grammatik ist genau dann wohlgeformt, wenn das
Gleichungssystem zu jedem Syntaxbaum der Sprache nicht rekursiv (zyklenfrei) ist.
Im Folgenden: Betrachtung der Abhängigkeiten zur Feststellung der Zyklenfreiheit einer attributierten Grammatik.
12
Regellokaler Abhängigkeitsgraph
Es sei G eine attributierte Grammatik und A [A,i] eine Regel. Zu A [A,i] lokaler Abhängigkeitsgraph G[A,i] = (N,E) ist definiert als:
N := {a | a attr(A)} {bk | 0 k < |[A,i]| und b attr([A,i,k])}
E := {(bn,am) | Es ex. a[A,i],#(m)(…,b#(n),…)}, wobei #() = 0
und #(k) = k+1 für k .
Expr
Type ) Expr(
symt t st
symt t stt
symt[Expr,7],4(symt0) := symt0
t[Expr,7],0(t2) := t2
st[Expr,7],0() := 1
Beispiel für Regel Expr ( Type ) Expr:
N = {symt, t, st, t1, symt3, t3, st3}
E = {(symt, symt3), (t1, t)}
13
Individueller Abhängigkeitsgraph
Darstellung der Abhängigkeiten zwischen den Attributexemplaren in einem Syntaxbaum durch den individuellen Abhängigkeitsgraphen.
Es sei (B,) ein konkreter Syntaxbaum. Für jeden Knoten B, mit () M, sei (N,E) der regellokale Abhängigkeitsgraph zu der Regel () (.0)…(.k). Der zu diesem Syntaxbaum gehörende individuelle Abhängigkeitsgraph G(B,) = (N,E) ist gegeben durch:
N := {b.n | B und () M und bn N} {(b.n,a.m) | B und () M und (bn,am) E)}
Folgerung: Eine Attributgrammatik ist genau dann zyklenfrei, wenn zu jedem Syntaxbaum der individuelle Abhängigkeitsgraph zyklenfrei ist.
Expr
Type ) Expr(
symt t st
symt t stt
Expr
Expr
symt t st
symt t stExprsymt t st +
Type t
TYPELIT tIDENT id
Exprsymt t st
declared IDENT id
Exprsymt t st
typedeclaredtype
14
Beispiel: Individueller Abhängigkeitsgraph für einen Teil eines Syntaxbaums
Expr
Type ) Expr(
symt t st
symt t stt
Exprsymt t stExprsymt t st +
TYPELIT t
IDENT idtypedeclared IDENT idtypedeclared
15
Auswertungsordnung
Eine Auswertungsordnung für einen Syntaxbaum (B,) ist eine totale Ordnung T(B,) mit E+ T(B,), wobei G(B,) = (N,E) der individuelle Abhängigkeitsgraph zu (B,) ist.
Durch eine Auswertungsordnung zu einem Syntaxbaum ist festgelegt, in welcher Reihenfolge Attributexemplare ausgewertet werden müssen.
symt < symt3 < symt3.0 < declared3.0.0
symt3.0 < t3.0 < t3
id3.2.0 < declared3.2.0
symt3 < symt3.2 < declared3.2.0
symt3.2 < t3.2 < t3
id3.2.0 < t3.2 < st3
t1.0 < t1 < t
id3.0.0 < t3.0 < st3
id3.0.0 < declared3.0.0
Partielle Ordnung E+ (< := E+): Totale Ordnung T(B,) (< := T(B,)):
symt < id3.0.0 < id3.2.0 < symt3 < symt3.0 < declared3.0.0 < t3.0 < symt3.2 < t3.2 < t3 < st3 < declared3.2.0 < t1.0 < t1 < t
16
Individuelle untere charakteristische Relation: G(B,)/ = {(symt,t), (symt,st)}.
Teil des individuellen Abhängigkeitsgraph G(B,) mit unterliegendem Syntaxbaum (B,).
Individuelle untere charakteristische Relation
Die im Syntaxbaum (B,) zum Unterbaum an Adresse gehörende individuelle Abhängigkeitsrelation sei: G(B,)/ = {(a,b) | G(B,) = (N,E) und (a,b) E} – {(a,b) | a syn(()) und b inh(())}.
Die individuelle untere charakteristische Relation im Syntaxbaum (B,) zur Adresse istG(B,)/ = {(a,b) | a inh(()), b syn(()) und (a,b) (G(B,)/)+}.
Expr
Type ) Expr(
symt t st
symt t stt
Exprsymt2 t2 st2Exprsymt0 t0 st0 +
TYPELIT t
IDENT id00type00declared00 IDENT id20type20declared20
Exprsymt t st
Exprsymt2 t2 st2Exprsymt0 t0 st0 +
IDENT id00type00 IDENT id20type20declared20declared00
Individueller Abhängigkeitsgraph G(B,)/ mit unterliegendem Syntaxbaum.
17
Individuelle untere/obere charakteristische Relation
Im Syntaxbaum (B,) gilt (a,b) G(B,)/ gdw. a inh(()) und b syn(()) und es einen Weg von a nach b in der individuellen Abhängigkeits-relation zum Unterbaum an Adresse gibt.
Analog wird die individuelle obere charakteristische Relation definiert: Im Syntaxbaum (B,) ist (a,b) G(B,)/ gdw. a syn(()) und b inh(()) und im individuellen Abhängigkeitsgraphen ein Weg von a nach b führt, der nicht zur individuellen unteren charakteristischen Relation bei X gehört.
Xa b cd e
Xb c d a
18
Berechnung aller unteren charakteristischen Relationen
Berechnung aller unteren charakteristischen Relationen für Syntaxbäume (B,) mit () = A bis zu einer Höhe von 0 durch: UCR0(A) :=
Berechnung aller unteren charakteristischen Relationen für Syntaxbäume bis zu einer Höhe von n+1 durch Einsetzen der unteren charakteristischen Relationen bis zu einer Höhe von n in die rechten Seiten der Alternativen zu A: UCRn+1(A) := {{(a,b) | (a,b) (E (1\E1) … (k\Ek))+ } | 1 i |[A]| und [A,i] = A1…Ak und G[A,i] = (N,E) und Ej UCRn(Aj)}.
Dabei ist z\R := {(az,bz) | (a,b) R}. Fixpunktiteration zur Berechnung, bis UCRn+1(A) = UCRn(A) für alle
A M. Fixpunkt wird erreicht, weil Menge der Attribute endlich ist und
damit auch die Menge aller Teilmengen von Attributpaaren. UCR(A) := UCRn+1(A) mit UCRn+1(A) = UCRn(A) Es wurde gezeigt, dass die Anzahl aller unteren charakteristischen
Relationen exponentiell mit der Anzahl der Attribute wachsen kann.
19
Testen auf Zyklenfreiheit
Berechnung der UCR(A) für alle A M. Eine attributierte Grammatik ist zyklenfrei, gdw. für alle A M und alle
1 i |[A]| und alle a und alle Ej UCRn(Aj) gilt: (a,a) {(E (1\E1) … (k\Ek))+}, wobei G[A,i] = (N,E) und [A,i] = A1…Ak.
D.h. es werden in jeden regellokalen Abhängigkeitsgraphen G[A,i] zu einer Regel A A1…Ak für jedes Metasymbol auf der rechten Seite die charakteristischen Graphen Ej dieser Metasymbole in jeder Kombination eingesetzt und die entstehende Relation durch Bildung des transitiven Abschlusses auf Zyklen getestet.
A
A1 AnA2 A3 …
20
Phasen der Attributauswertung
Strategiephase; Festlegung einer Auswertungsordnung: Dynamisch
Vollständig dynamisch: Suchen und Berechnen eines Attributexemplars, das nur von bereits berechneten Attributexemplaren abhängt.
Festlegen der Auswertungsordnung nach der Erzeugung des Syntaxbaums
Statisch Festlegung einer Auswertungsordnung, die für jeden möglichen
Syntaxbaum gültig ist. Auswertungsphase; Durchführung der Attributauswertung,
entweder: Bedarfsgetrieben: Auswerter erhält die auszuwertenden
Attribute und wertet dann rekursiv die dafür benötigten Attribute aus.
Datengetrieben: Auswertung beginnt bei den Attributen, die von keinen anderen Attributen abhängen. Auswertung wird an den Attributen fortgesetzt, die nur von solchen Attributen abhängen, die bereits ausgewertet wurden.
21
Vollständig dynamisch - datengetrieben
Initial sind alle Attributexemplare mit dem Wert für undefiniert initialisiert.
Der Wert val(a) eines Attributexemplars a kann durch
berechnet werden, sobald alle Argumente der semantischen Funktion einen Wert verschieden von haben.
1
1
1
1
. .( ),0
. .( ),
( ( ), , ( )), falls ( ( ))( ) :
( ( ), , ( ))
, falls 0wobei . und , wobei das -te
1, sonst
Argument in de
n
n
n
n
i
x xAlt j j
x xAlt k j j
i
i ji
a val b val b a synval a
a val b val b
jk x b i
j
a aa
ab b
b
s a
ea b
ì Îïïï= íïïïîì =ïïï= = íï -ïïî
K
K
r semantischen Funktion für ist,a
22
Vollständig dynamisch - bedarfsgetrieben
Die Berechnung des Attributexemplars a erfolgt durch:
Um Mehrfachberechnungen von Attributen zu vermeiden, kann dynamische Programmierung verwendet werden.
1
1
1
1
. .( ),0
. .( ),
( , , ), falls ( ( )):
( , , )
, falls 0wobei . und , wobei das -te
1, sonst
Argument in der semantischen Funktion f
n
n
n
n
i
x xAlt j j
x xAlt k j j
i
i ji
a b b a syna
a b b
jk x b i
j
a aa
ab b
b
s a
ea b
ì Îïïï= íïïïîì =ïïï= = íï -ïïî
K
K
ür ist.a
23
Klassenstruktur einer Implementierungsvariante
TNode
A1
TNode parentint myPosAttribute von A1
An
TNode parentint myPosAttribute von An
…
A1_1Verweise auf SöhneSemantische Funk-tionen
A1_m1
Verweise auf SöhneSemantische Funk-tionen
… An_1Verweise auf SöhneSemantische Funk-tionen
An_mn
Verweise auf SöhneSemantische Funk-tionen
…
Knote
n im
Syn
taxb
au
m
Alt
ern
ati
ven
der
Meta
sym
bole
Meta
sym
bole
24
Implementierungsvariante bedarfsgetrieben
Jede Klasse A stellt für jedes Attribut eine Methode eval_a() bereit.
Jede Klasse A_i stellt für jede semantische Funktion a[A,i],k eine Funktion eval_a(k) bereit:
Dabei ist Xi der Verweis auf die Instanz eines Metasymbols, zu dem das zu berechnende Attribut gehört (this oder ein Verweis auf einen Sohn).
TValue A_i::eval_a(k) { switch(k) { case j1: b1 = Xj1->eval_b1(); …; bm1 = Xjm1->eval_bm1(); return a[A,i],j1
(b1,…,bm1)
... case jz: b1 = Xjz->eval_b1(); …; bmz = Xjmz->eval_bmz(); return a[A,i],jz
(b1,…,bmz)
}}
TValue A::eval_a() { return eval_a(0);}
TValue A::eval_a() { return parent->eval_a(myPos);}
25
Statische Auswertungsordnung: S-attributierte-Grammatiken
Eine attributierte Grammatik ist S-attributiert, falls jedes Attribut synthetisiert ist.
Offensichtlich ist dann eine Auswertungsordnung der Attributexemplare statisch bestimmt, indem die Attributexemplare im Syntaxbaum Bottom-Up ausgewertet werden.
Dies entspricht der Form, in der der Syntaxbaum durch einen LR(k)-Parser erzeugt wird.
Falls die Grammatik auch eine LR(k)-Grammatik ist, können die Attribute während der syntaktischen Analyse direkt ausgewertet werden.
26
Statische Auswertungsordnung:L-Attributierte-Grammatiken
Eine attributierte Grammatik ist L-attributiert, falls für jede Regel A [A,i] und jede semantische Funktion a[A,i],k(bu1
,…,bum) zu dieser
Regel gilt: Falls a inh([A,i,k-1]), dann gilt 0 un < k für alle 1 n m, d.h:
a ist synthetisiert oder a ist ererbt und a hängt nur von Attributvorkommen in Symbolen links
von a ab. Offensichtlich ist dann eine Auswertungsordnung der Attribute
statisch bestimmt, indem die Attribute im Syntaxbaum durch einen Links-Rechts-Tiefendurchlauf ausgewertet werden, wobei:
ererbte Attribut, beim ersten Betreten eines Knotens ausgewertet werden und
alle übrigen Attribute beim letztmaligen Verlassen eines Knotens. Dies entspricht der Form, in der der Syntaxbaum durch einen
LL(k)-Parser erzeugt wird. Falls die Grammatik eine LL(k)-Grammatik ist, können die Attribute
während der syntaktischen Analyse direkt ausgewertet werden.
27
Kontextprüfung ohne Attribute
In vielen praktischen Fällen werden zur Kontextprüfung nicht direkt attributierte Grammatiken eingesetzt.
Es wird aber die zentrale Idee genutzt, dass für jede Knotenart im Syntaxbaum eine oder mehrere semantische Funktionen existieren und eine statische Auswertungsordnung bekannt ist.
D.h. der Syntaxbaum wird möglicherweise mehrmals traversiert und dabei die semantischen Funktionen aufgerufen, um alle gewünschten Informationen zu berechnen.
Um den umständlichen Transport von Attributwerten zu vermeiden, werden Informationen dabei oft in globalen Datenstrukturen gespeichert.
Als Beispiel betrachten wir den Aufbau einer Symboltabelle während einer Bottom-Up-Analyse.
28
Modifizierte Grammatik
Program ::= BlockBlock ::= { DeclL StmtL }DeclL ::= Type VarL ; DeclL | eType ::= TYPELITVarL ::= IDENT , VarL | IDENTStmtL ::= Stmt ; StmtL | eStmt ::= Block | Assign Assign ::= LVal = ExprLVal ::= IDENTExpr ::= Expr + Expr |
Expr - Expr | Expr * Expr |Expr / Expr | ( Expr ) | IDENT | ( Type ) Expr | INTLIT | FLOATLIT
Program ::= BlockBlock ::= { BlBegin DeclL StmtL }BlBegin ::= DeclL ::= DeclType VarL ; DeclL | eDeclType ::= TypeType ::= TYPELITVarL ::= IDENT , VarL | IDENTStmtL ::= Stmt ; StmtL | eStmt ::= Block | Assign Assign ::= LVal = ExprLVal ::= IDENTExpr ::= Expr + Expr |
Expr - Expr | Expr * Expr |Expr / Expr | ( Expr ) | IDENT | ( Type ) Expr | INTLIT | FLOATLIT
Originalgrammatik: Modifizierte Grammatik:
29
Beispiel Symboltabelle
Blöcke im Programm werden lexikografisch nummeriert.
Zu jedem Block wird eine Symboltabelle mit der Nummer des Blocks bei der Reduktion BlBegin erzeugt.
Der Typ der Variablen in einer Liste wird durch Reduktion mittels DeclType Type festgelegt.
Bei Reduktion mittels VarL Ident bzw. VarL IDENT "," VarL werden die Bezeichner mit dem zuvor festgelegten Typ in die aktuelle Symboltabelle eingetragen. Hierbei ist ein Test auf Mehrfachdeklarationen leicht möglich.
Bei Reduktion mittels Block "{" DeclL StmtL "}" wird die Nummer des nächsten Blocks auf derselben Ebene erzeugt.
Vollständiger Quelltext Ausführbares Programm
Ende der Kontextprüfung
Weiter zur Zwischencodeerzeugung
31
Beispiel für Sammeln und Weiterreichen der Deklarationen
DeclL
Type
TYPELIT
VarL DeclL;
IDENT , VarL
IDENT
Block
Program
t=float
t=float
id=a
id=b
ids={b}
ids={a,b} dcl=
dcl={(float,{a,b})}
DeclL
Type
TYPELIT
VarL DeclL;
IDENTt=int
t=int
id=a
ids={a}dcl=
dcl={(int,{a})}
Block
StmtL
Stmt ; StmtL
StmtL
symt=
symt=(,{(float,{a,b})}){ }
}{
symt=(,{(float,{a,b})})symt=(,{(int,{a,b})})
symt=(,{(float,{a,b})})
symt=( (,{(float,{a,b})}), {(int,{a})})
32
Beispiel zum Prüfen der Typverträglichkeit
StmtLsymt=((,{(float,{a,b})}), {(int,{a})})
Stmt ; StmtL
Assign
LVal Expr
IDENT id=bExpr * Expr
INTLIT iVal=2 IDENTid=a
symt=((,{(float,{a,b})}), {(int,{a})})
symt=((,{(float,{a,b})}), {(int,{a})})
symt=((,{(float,{a,b})}), {(int,{a})}) symt=((,{(float,{a,b})}), {(int,{a})})
symt=((,{(float,{a,b})}), {(int,{a})}) symt=((,{(float,{a,b})}), {(int,{a})})declared=serach(b,symt0)=1
declared=serach(a,symt0)=1
t=int t=int
t=int
t=float=
st=1 st=1
st=1
st=0
33
Beispiel Mengengleichungssystem
DeclL
Type
TYPELIT
VarL DeclL;
IDENT , VarL
IDENT
t=float
t=float
id=a
id=b
ids={b}
ids={a,b} dcl=
dcl={(float,{a,b})}
t0.0() = float
t0(t0.0) = t0.0
id1.0() = a
id1.2.0() = b
ids1.2(id1.2.0) = {id1.2.0}
ids1(id1.0,ids1.2) = {id1.0} ids1.2
dcl3() =
dcl(t0,ids1,dcl3) = dcl3 {(t0,ids1)} Zurück