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