Einführung - WWW-Docs for TU

 Documents

 32 views
of 40
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Vorlesung Compilertechnik Sommersemester 2008 Zwischencodeerzeugung M. Schölzel Aufgabe der Zwischencodeerzeugung  Bereitstellung einer Schnittstelle zum…
Share
Transcript
Vorlesung Compilertechnik Sommersemester 2008 Zwischencodeerzeugung M. Schölzel Aufgabe der Zwischencodeerzeugung  Bereitstellung einer Schnittstelle zum Backend des Compilers.  Generierung einer oder mehrerer Zwischenrepräsentation für das Quellprogramm, so dass:  alle erforderlichen Informationen erhalten bleiben,  die benötigten Informationen auf eine geeignete Weise für den jeweiligen Zweck dargestellt sind,  keine oder wenig zielcodespezifische Informationen enthalten sind,  sich die Darstellung der Informationen gut in Zielcode/die nächste Zwischencoderepräsentation übersetzen lässt.  Art der Zwischenrepräsentation hängt stark vom jeweiligen Zweck ab und kann damit stark variieren. 2 Beispiele für oft genutzte Arten der Zwischencodedarstellung  C (erster C++ Compiler, Bison, Flex): Darstellung mehrerer Module, jedes davon besteht aus Funktionen.  Syntaxbaum: In der Regel Darstellung eines Moduls mit mehreren Funktionen.  Aufrufgraph: Darstellung von Funktionen und der Aufrufbeziehungen.  Steuerflussgraph: Repräsentation des Steuerflusses innerhalb einer Funktion.  CDFG: Repräsentation einer Funktion und der Datenabhängigkeiten.  DAGs: Repräsentation von Datenabhängigkeiten ohne Steuerfluss.  3-Adress-Code: Repräsentation mehrerer Funktionen.  SSA-Code: Repräsentation mehrere Funktionen.  … 3 Einbettung der Zwischencodeerzeugung in den Compiler  Da der Syntaxbaum schon eine Zwischencodeart darstellt, ist die Erzeugung des Syntaxbaums bereits Teil der Zwischencodeerzeugung.  Dieser kann in mehreren Schritten vereinfacht werden.  Die Darstellung des Zwischencodes nähert sich dabei immer mehr dem gewünschten Zielcode an. Hoch Abstraktionsebene Niedrig Syntaxbaum 3-Adress-Code Parser … t2 := t1 + t0 t3 := a Zielcode- t4 := t2 * t3 erzeugung … Zwischencodeerzeugung 4 3-Adress-Code  Folge von 3-Adress-Code-Anweisungen.  Anweisungsarten:  Binäranweisungen: x := y  z  Unäranweisungen: x :=  y  Kopieranweisungen: x:=y, x:=k, @x:=y, x:=@y, x:=&y  Sprunglabel: Label:  Funktionslabel: Function Label:  Unbedingte Sprünge: goto index  Bedingte Sprünge: if x then Label  Funktionsaufrufe: x := call FLabel(y1,…,yn)  Funktionsbeendigung: return x, return  Castoperationen: x := (Type) y  Dabei sind: k Konstante, x, y, yi und z Variablen, wobei Variablen unterschieden werden in:  Programmvariablen (lokal, global)  Temporäre Variablen (immer lokal) 5 Beispiel: 3-Adress-Code Function f: t0 := 1 int f(int n){ fak = t0 int fak = 1; while_0_cond: while(n > 0) { t1 := n fak = fak * n; t2 := 0 n = n – 1; t3 := t1 > t2 } t4 := not t3 return fak; if t4 then while_0_end } t5 := fak t6 := n t7 := t5 * t6 fak := t7 t8 := n t9 := 1 t10 := t8 – t9 n := t10 goto while_0_cond while_0_end: t11 := fak return t11 6 Speichermodell  Temporäre Variablen repräsentieren Werte, die bevorzugt in Prozessorregistern gehalten werden.  Programmvariablen repräsentieren Werte, die im Hauptspeicher gehalten werden und damit auch eine Speicheradresse besitzen.  Es wird unterschieden zwischen Programmvariablen mit:  einer absoluten Adresse (global),  einer relativen Adresse (lokal).  Parametern einer Funktion und  lokalen Variablen einer Funktion, die nicht Parameter sind.  Absolute und relative Adressen (möglicherweise als virtuelle Adresse) werden bereits während der Zwischencodeerzeugung festgelegt und zu jeder Variablen gespeichert. 7 Modell für die Zwischencodeerzeugung  Die LR(1)-Grammatik der Quellsprache wird für die Zwischencodeerzeugung zu einer attributierten Grammatiken erweitert:  S-attributierte Grammatik zum Aufbau des Syntaxbaums:  Jedes Attributvorkommen in einer Regel A0  A1…An speichert die Wurzel des Syntaxbaums, der während der Analyse zu der Ableitung Ai *  gehört.  Der LR-Parser kann diese Attribute während der Analyse direkt auswerten und berechnet somit den Syntaxbaum.  S- oder L-attributierte Grammatik zur Erzeugung von 3-Adress-Code:  Jeder Knoten erhält ein Attribut, das ein Zwischencodefragment speichern kann.  Durch geeignete semantische Funktionen werden diesen Attributen Werte zugewiesen.  Konsequenz: An Syntaxbaumknoten, an denen dieselbe Grammatik- regel angewendet wurde, wird auch dieselbe Aktion ausgeführt.  Weitere Annahme: Hierarchisch organisierte Symboltabellen sind bereits erzeugt. 8 Prinzipien bei der Übersetzung eines Syntaxbaums in 3-Adress-Code  Anweisungen ändern Speicherzustände oder den Steuerfluss: Übersetzung in entsprechende Zwischencodebefehle.  Übersetzung von Ausdrücken aus der Quellsprache:  Bedeutung ist ein Wert.  Erzeugung von Zwischencode mit derselben Bedeutung.  Berechnung des Wertes in eine temporäre Variable.  Ausdrucksanweisungen ändern Speicherzustände und haben einen Wert als Bedeutung.  Syntaxbaumknoten, die zu einem Ausdruck gehören können, speichern neben dem Zwischencodefragment auch die temporäre Variable, in die der Zwischencode den Wert berechnet.  Attribute für Syntaxbaumknoten, die zu einem Ausdruck gehören können:  (ir,t): ir Speichert den 3-Adress-Code und t die Zwischencodevariable, in die durch ir der Wert des Ausdrucks berechnet wird.  iVal, fVal sind synthetisiertes Attribute an INTLIT bzw. FLOATLIT, deren Wert durch den Scanner gesetzt wird.  Bereits vorhanden: t speichert den Typ des Ausdrucks. 9 Hilfsfunktionen, für die Übersetzung in 3- Adress-Code  getNextTemp(): liefert einen neuen, noch nicht benutzten Namen für eine temporäre Variable zurück.  getNextWhile(): liefert eine neue, noch nicht benutzten Nummer für eine while-Schleife zurück.  getNextIf(): liefert eine neue, noch nicht benutzten Nummer für eine if- Anweisunge zurück.  uniqueName(v): Liefert für die Programmvariable v ihren eindeutigen Namen durch Suchen in den hierarchisch organisierten Symboltabellen. Eindeutiger Name entsteht z.B. durch Erweiterung des Variablennamens mit der lexikografischen Nummer der Symboltabelle.  nextGlobalAdress: Nächste freie globale Adresse (relativ zu einer virtuellen Basis). Kann bereits beim Aufbau der globalen Symboltabelle festgelegt werden.  nextLocalAdress: Nächste freie lokale Adresse (relativ zu einer virtuellen Basisadresse). Kann lokal für jede Symboltabelle zu einer Funktion festgelegt werden. 10 Übersetzung von Zuweisungen und Ausdrücken  ir[Expr,6],0 := ("t:=a", t), wobei t := getNextTemp() und a = uniqueName(id1)  ir[Expr,8],0 := ("t:=iVal1", t), wobei t := getNextTemp()  ir[Expr,9],0 := ("t:=fVal1", t), wobei t := getNextTemp()  ir[Expr,7],0 := (ir  "t:=(type)t'", t), wobei t := getNextTemp(), ir4 = (ir,t'), type = t2  ir[Expr,5],0 := ir2  ir[Expr,1],0 := (irl  irr  "t:=tl + tr", t), wobei t := getNextTemp(), ir1 = (irl,tl) und ir3 = (irr,tr)  ir[Expr,2],0 := (irl  irr  "t:=tl - tr", t), wobei t := getNextTemp(), ir1 = (irl,tl) und ir3 = (irr,tr)  ir[Expr,3],0 := (irl  irr  "t:=tl * tr", t), wobei t := getNextTemp(), ir1 = (irl,tl) und ir3 = (irr,tr)  ir[Expr,4],0 := (irl  irr  "t:=tl / tr", t), wobei t := getNextTemp(), ir1 = (irl,tl) und ir3 = (irr,tr)  id[LVal,1],0 := id1  ir[Assign,1],0 := ir  " t:=t' ", wobei t = uniqueName(id1), ir3 = (ir,t') 11 Beispiel Syntaxbaum für den Ausdruck c := a+2*b: Quelltextfragment: Assign ir= t0:=a$0 { t1:=2 int a; t2:=b$01 … t3:=t1*t2 { t4:=t0+t3 int b,c; c$01:=t4 … ir=( t0:=a$0 c := a+2*b; LVal id=c$01 Expr t1:=2 … t2:=b$01 } t3:=t1*t2 t4:=t0+t3,t4) … } IDENT id=c Expr ir=(t0:=a$0,t0) Expr ir=( t1:=2 t2:=b$01 t3:=t1*t2,t3) Symtab0 Name UniquName Typ Scope Adresse IDENT id=a Expr ir=(t1:=2,t1) Expr ir=(t2:=b$01,t2) a a$0 int lokal 0 INTLIT iVal=2 IDENT id=b Symtab0.1 Name UniquName Typ Scope Adresse b b$01 int lokal -4 c c$01 int lokal -8 12 Übersetzung von Anweisungsfolgen  ir[Stmt,1] := "BlBegin_i:"  ir1  "BlEnde_i", wobei i = getNextBlock().  Einfügen von Labeln, um an den Blockgrenzen auch Basisblöcke zu abzuschließen.  Für die übrigen Alternativen 2,…,k zu Stmt: ir[Stmt,k] := ir1, für 1 < k.  ir[StmtL,1] := ir1  ir3  ir[StmtL,2] :=   ir[Block,1] := ir3  ir[Program,1] := ir1 13 Beispiel Syntaxbaum für das Programm: { Program ir= 1 BlBegin_1: 2122 BlEnd_1:34 Stmt1; { Block Stmt21; Stmt12; }; { DeclL StmtL ir=  BlBegin_1:   BlEnd_1:  } Stmt3; 1 21 22 3 4 Stmt4; } Stmt1 ; StmtL ir=BlBegin_1: 2122 BlEnd_1:34 ir=1 Stmt2 ; StmtL ir=  ir=BlBegin_1: 2122 BlEnd_1: 3 4 Block ir=  Stmt3 ; StmtL ir= 21 22 4 ir=3 { DeclL StmtL ir=  } Stmt4 ; StmtL 21 22 ir=4 Stmt21 ir= ; StmtL ir= 21 22 Stmt22 ; StmtL ir=22 14 Erweiterung der Grammatik um Schleifen und bedingte Verzweigungen Program ::= Block Block ::= { DeclL StmtL } DeclL ::= Type VarL ; DeclL |  Type ::= TYPELIT VarL ::= IDENT , VarL | IDENT StmtL ::= Stmt ; StmtL |  Stmt ::= Block | Assign | While | If Assign ::= LVal = Expr LVal ::= IDENT Expr ::= Expr + Expr | Expr - Expr | Expr * Expr | Expr / Expr | ( Expr ) | IDENT | ( Type ) Expr | INTLIT | FLOATLIT While ::= while Cond Block If ::= if Cond then Block else Block Cond ::= … 15 Übersetzung einer While-Anweisung  ir[While,1],0 := "while_i_cond:"  irc  "tcn:= not tc"  "if tcn then goto while_i_end"  irb  "goto while_i_cond"  "while_i_end:", wobei:  ir2 = (irc,tc),  ir3 = irb,  tcn = getNextTemp(),  i = getNextWhile(). 16 Übersetzung einer if-Anweisung  ir[If,1],0 := (irc  "if tc then goto then_i"  irb2  "goto if_i_end"  "then_i:"  irb1  "if_i_end:"), wobei:  ir2 = (irc,tc),  ir4 = irb1,  ir6 = irb2,  i = getNextIf(). 17 Typkonstruktoren  Es sei B = {int, float} die Menge der Basisdatentypen.  Zu jedem Programm gehört eine Menge T von Typen mit B  T, die auch selbst definierte Datentypen enthält.  Es existieren die Typkonstruktoren:  array(T, n), wobei T  T ein Datentyp ist und n  ,  struct(T1 k1,…,Tn kn).  Für T  T stehen folgende Hilfsfunktionen bereit:  sizeof(T): Speicherbedarf des Datentyps T in Byte.  typeOfElem(T) = T', falls T = array(T', n).  typeOfElem(T,k) = Ti, falls T = struct(T1 k1,…,Tn kn) und ki = k.  Für einen Variablenbezeichner a:  lookUp(a) = T, falls T der Datentyp des Bezeichners a ist. 18 Deklarationen eigener Datentypen Grammatik erweitert um Deklaration eigener Datentypen: Program ::= TypeDeclL Block TypeDeclL ::= TypeDecl ";" TypeDeclL |  TypeDecl ::= IDENT = NewType NewType ::= IDENT | "array" [INTLIT] "of" NewType | "struct" { NewTypeL } newTypeL ::= NewType IDENT| NewType IDENT , NewTypeL Block ::= { DeclL StmtL } Beispiel zur Deklaration eigener Datentypen: myint = int; a1int = array [10] of int; a2int = array [10] of array [5] of int; t = array [20] of struct {int a, a2int b}; Beim Parsen erzeugte Datentyptabelle: Typbezeichner Typkonstruktor Größe in Byte myint int 4 a1int array (int, 10) 40 anonym_1 array (int, 5) 20 a2int array (anonym_1,10) 200 anonym_2 struct (int a, a2int b) 204 t array (anonym_2,20) 4080 19 Attributierte Grammatik zur Übersetzung von Struktur- und Feldzugriffen Stmt ::= Block | Assign | While | If Assign ::= LVal = Expr LVal ::= IDENT Expr ::= Expr + Expr | Expr - Expr | Expr * Expr | Expr / Expr | ( Expr ) | IDENT | ( Type ) Expr | INTLIT | FLOATLIT | IDENT Q While ::= while Cond Block Q ::= [ Expr ] Q | . IDENT Q | [ Expr ] | . IDENT 20 Beispiel  Für Felder und Strukturen sind folgende Informationen Im Syntaxbaum annotiert:  In der Regel Expr  IDENT Q ist t2 = array(T,n), falls lookUp(id1) = array(T,n) ist.  In der Regel Expr  IDENT Q ist t2 = struct(T1 n1,…,Tm kn), falls lookUp(id1) = struct(T1 n1,…,Tm kn) ist.  In der Regel Q  [ Expr ] Q ist t4 = T', falls t0 = array(T',n).  In der Regel Q  . IDENT Q ist t3 = Ti, falls t0 = struct(T1 n1,…,Tm kn) und id2 = ki.  Beispiel: Expr Deklaration: t i; IDENT id=i t=array(anonym_2,20) Q Zugriff: i[15].b[8][4]; [ Expr ] t=struct(int a, a2int b) Q INTVAL iVal=15 . IDENT id=b t=array(anonym_1,10) Q Typbezeichner Typkonstruktor [ Expr ] Q t=array(int, 5) myint int a1int array (int, 10) INTVAL iVal=8. [ Expr ] anonym_1 array (int, 5) a2int array (anonym_1,10) INTVAL iVal=4. anonym_2 struct (int a, a2int b) t array (anonym_2,20) 21 Übersetzung von Feld- und Strukturzugriffen in Ausdrücken (1)  ir[Expr,10],0 := ( iro  Expr ::= IDENT Q "tb:=&id1"  "tp:=tb+to"  "t:=@tp", t), wobei  (iro,to) = ir2,  tb := getNextTemp(), tp := getNextTemp(), t := getNextTemp().  ir[Q,3],0 := ( ire  "ts:=s"  "to:=ts*te", to), wobei Q ::= [ Expr ]  ir2 = (ire,te)  t0 = array(T',n) und s = sizeof(T')  ts := getNextTemp()  to := getNextTemp()  ir[Q,4],0 := ( "to:=off", to), wobei i- 1 Q ::= . IDENT  off = å k= 1 sizeof (T, ifalls ) t0 = struct(T1 n1,…,Tm nm) und id2 = ni  to := getNextTemp(). 22 Übersetzung von Feld- und Strukturzugriffen in Ausdrücken (2)  ir[Q,1],0 := (ire  irlo  Q ::= [ Expr ] Q "ts:=s"  "to:=ts*te"  "tno:=to+tlo", tno), wobei  ir2 = (ire,te),  ir4 = (irlo,tlo),  t0 = array(T',n) und s = sizeof(T'),  ts := getNextTemp(),  tno := getNextTemp(),  to := getNextTemp(). Q ::= . IDENT Q  ir[Q,2],0 := (irlo  "to:=off"  "tno:=to+tlo", tno), wobei  off = offset(ni), falls t0 = struct(T1 n1,…,Tm nm) und id2 = ni,  ir3 = (irlo,tlo),  to := getNextTemp(),  tno := getNextTemp(). 23 Beispiel ir=( t0:=15 t1:=8 t2:=4 t3:=4 //sizeof(int) t4:=t3*t2 t5:=20 ir=( t0:=15 t6:=t5*t1 t1:=8 t7:=t6+t4 t2:=4 t8:=4 //offset b t3:=4 //sizeof(int) t9:=t8+t7 t4:=t3*t2 t10:=204 t5:=20 //sizof(anonym_1) ir=( t1:=8 t11:=t10*t0 t6:=t5*t1 t2:=4 t12:=t11+t9 t7:=t6+t4 t3:=4 //sizeof(int) t13:=&i t8:=4 //offset b t4:=t3*t2 Expr t14:=t13+t12, t9:=t8+t7 t5:=20 //sizof(anonym_1) t15:=@t14,t15) t10:=204 //sizeof(anonym_2 t6:=t5*t1 t11:=t10*t0 t7:=t6+t4 IDENT id=i t=array(anonym_2,20) Q t12:=t11+t9,t12) t8:=4 //offset b t9:=t8+t7,t9) [ Expr ] t=struct(int a, a2int b) Q ir=( t0:=15,t0) INTVAL iVal=15 Q ir=( t1:=8 . IDENT id=b t=array(anonym_1,10) t2:=4 t3:=4 //sizeof(int) ir=( t2:=4 t4:=t3*t2 [ Expr ] ir=( t1:=8,t1) t=array(int, 5) Q t3:=4 //sizeof(int) t5:=20 //sizof(anonym_1) t4:=t3*t2,t4) t6:=t5*t1 t7:=t6+t4,t7) INTVAL iVal=8. [ Expr ] ir=( t2:=4,t2) INTVAL iVal=4. 24 Grammatik zur Übersetzung von Funktionsaufrufen und -deklarationen Program ::= TypeDeclL FuncL FuncL ::= IDENT IDENT ( ) Block | IDENT IDENT ( FormalParam ) Block FormalPram::= IDENT IDENT , FormalParam | IDENT IDENT Block ::= { DeclL StmtL } … Expr ::= Expr + Expr | Expr - Expr | Expr * Expr | Expr / Expr | ( Expr ) | IDENT | ( Type ) Expr | INTLIT | FLOATLIT | IDENT Q | IDENT ( ParamList ) | IDENT ( ) ParamL ::= Expr | Expr , ParamL While ::= while Cond Block Q ::= [ Expr ] Q | . IDENT Q | [ Expr ] | . IDENT 25 Übersetzung einer Deklaration  Eine Funktion funcDecl speichert die Signaturen der im Programm deklarierten Funktionen:  Rückgabetyp,  Name,  Typen der formalen Parameter.  Eine Deklaration der Art t f(t1 i1,…,tn in) im Programm führt zu einem Eintrag (f, (t, t1, …,tn)) in funcDecl.  Leicht durch geeignete Attribute zu realisieren. 26 Übersetzung von Funktionsaufrufen  ParamL erhält ein Attribut pl zur Speicherung der aktuellen Parameterliste und ein Attribut ir zur Speicherung des Zwischencodes, der bei der Übersetzung der Ausdrücke in der Parameterliste entstanden ist:  pl[ParamL,1],0 := te und ir[ParamL,1],0 := ire, wobei (ire,te) = ir1.  pl[ParamL,2],0 := (te ,pl3) und ir[ParamL,2],0 := ire  ir3, wobei (ire,te) = ir1. Expr ir=( '    tr := call f(t',t), tr) IDENT id=f ( ParamList pl=(t', t) ) ir= '   Exprir=(',t') , , ParamList pl=t ir= Expr ir=(,t) 27 Basisblöcke  Ein Basisblock ist eine Folge maximaler Länge von Anweisungen im 3- Adress-Code, für die gilt:  Nur die erste Anweisung darf ein Label sein (d.h., dass ein Sprung in einen Basisblock nur zu seiner ersten Anweisung führen kann) und  nur die letzte Anweisung darf eine Sprunganweisung sein (d.h., dass alle Anweisungen des Basisblocks ausgeführt werden, wenn die erste Anweisung ausgeführt wird).  Anmerkung: Unterprogrammaufrufe können als k-näre Operation betrachtet werden, falls sie keine Seiteneffekte verursachen. return-Anweisungen sind Sprunganweisungen.  Der erzeugte unoptimierte Zwischencode hat folgende nützlichen Eigenschaften:  Vor jeder Benutzung einer temporären Variablen wird diese im selben Basisblock beschrieben.  Nachdem eine temporäre Variable beschrieben wurde, wird sie genau einmal im selben Basisblock benutzt.  Programmvariablen treten nur in Anweisungen der Art x := y auf, wobei entweder x oder y eine Programmvariable ist.  Es ist eine totale Ordnung für die Anweisungen innerhalb eines Basisblocks vorgegeben. 28 DFGs zur Repräsentation von Basisblöcken  Totale Ordnung einer Anweisungsfolge im 3-Adress-Code wird zu einer partiellen Ordnung abgeschwächt.  G = (N, E, A, ord, label) sei ein gerichteter azyklischer Graph (DAG):  Knoten repräsentieren Operationen in den 3-Adress-Code- Anweisungen.  Kanten in E repräsentieren durch Variablen modellierte Datenabhängigkeiten:  Lese-Schreib-Abhängigkeit (input-dependence),  Kanten in A repräsentieren durch Speicherzugriffe entstehende Datenabhängigkeiten:  Schreib-Lese-Abhängigkeit (anti-dependence),  Schreib-Schreib-Abhängigkeit (output-dependence)  ord : E   modelliert die Reihenfolge der eingehenden Kanten (Operanden) eines Knotens. Bei ord(e) < ord(e') ist e linker und e' rechter Operand.  label : N  {const k, store, load, write a, read a,  | k  , a  +,  ist Operation im 3-Adress-Code} ist eine Beschriftung der Knoten mit Operationen. 29 Konstruktion eines DAGs zu einem Basisblock mit Eliminierung gemeinsamer Teilausdrücke  Eingabe: Basisblock als Folge von 3-Adress-Code-Anweisungen ir0,…,irn  Ausgabe: DAG (N, E, A, ord, label)  Algorithmus: N := , E := , A := , ord := , label :=  S :=  // Enthält für die aktuelle Situation bei der Übersetzung für jede Variable // des Zwischencodes u.a. den Knoten im DAG, der ihren Wert berechnet for i = 0 to n do switch(iri) case "x := y  z": TranslateBinStmt(iri); break; case "x :=  y : TranslateUnaStmt(iri); break; case "x := y" : TranslateCopy(iri); break; case "@x := y" : TranslateStore(iri); break; case "x := @y" : TranslateLoad(iri); break; end od Für jedes (a,n,W)  S mit a ist Programmvariable erzeuge Knoten m mit label(m) = write a, N := N  {m}, E := E  {(n,m)}, A := A  {(h,m) | label(h) = read a oder label(h) = load oder label(h) = store}  Hilfsfunktionen: findVar(var) findLabel(label,l,r) if (var,n,x)  S then return n if n  N mit Beschriftung label und else return 0 ((l,n)  E oder l = 0) und fi ((r,n)  E oder r = 0) then return n else return 0 30 fi Übersetzung von Kopieranweisungen TranslateConst(x := k) if findLabel(const k,0,0) = 0 then Erzeuge Knoten n mit label(n) = const k N := N  {n} fi n := findLabel(const k,0,0) S := S  {(x,n,W)} TranslateCopy(x := y) if findVar(y) = 0 then Erzeuge Knoten n mit label(n) = read y // passiert nur, wenn y Programmvariable N := N  {n} S := S  {(y,n,R)} fi l := findVar(y) S := S – {(x,n,k) | n  N und k  {R,W}) S := S  {(x,l,W)} 31 Übersetzung binärer und unärer Operationen TranslateUnaStmt(x :=  y) l := findVar(y) // immer erfolgreich if findLabel(, l) then m := n else Erzeuge neuen Knoten m mit label(m) =  N := N  {m} E := E  {(l,m)} fi S := S – {(x,n,k) | n  N und k  {R,W}) S := S  {(x,m,W)} TranslateBinStmt(x := y  z) l := findVar(y) r := findVar(z) if  n  N mit label(n) =  und (l,n)  E und (r,n)  E und not ((r,n) < (l,n)) then m := n else Erzeuge einen Knoten m mit Beschriftung  N := N  {m} E := E  {(l,m),(r,m)} ord((l,m)) := 0; ord((r,m)) := 0, falls  kommutativ, sonst ord((r,m)) := 1 fi S := S – {(x,n,k) | n  N und k  {R,W}) S := S  {(x,m,W)} 32 Beispiel 1 Beispiel: a = 2*(b+a-2) * (b+a) const 2 read b read a S 1 2 3 t0 := 2 (t0,1,W) t1 := b (b,2,R) t2 := a + t3 := t1+t2 4 (t1,2,W) t4 := 2 (a,3,R) t5 := t3 – t4 - (t2,3,W) t6 := t0 * t5 5 t7 := b (t3,4,W) t8 := a t9 := t7 + t8 (t4,1,W) t10 := t6 * t9 * (t5,5,W) a := t10 6 (t6,6,W) (t7,2,W) (t8,3,W) (t9,4,W) * (t10,7,W) 7 (a,7,W) write a 8 33 Übersetzung von Speicherzugriffen TranslateLoad(x := @y) l := findVar(y) Erzeuge neuen Knoten n mit label(n)=lo
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks