Generování vnitřní reprezentace programu
Miroslav Beneš
Dušan Kolář
Vnitřní reprezentace programu 2
Možnosti překladu Interpretace
Okamžité provádění programu Překlad do instrukcí procesoru
Závislost na konkrétním typu procesoru Překlad do vnitřní reprezentace
Následuje interpretace nebo překlad do instrukcí procesoru
Vnitřní reprezentace programu 3
Výhody překladu do vnitřní reprezentace
Strukturalizace překladače Mnohem jednodušší přenos na více typů
procesorů Možnost optimalizace na úrovni vnitřní
reprezentace strojově nezávislé metody
Vnitřní reprezentace programu 4
Formáty vnitřní reprezentace programu
Grafová reprezentace Zásobníkový kód Tříadresový kód
Vnitřní reprezentace programu 5
Grafová reprezentace Abstraktní syntaktický strom (AST)
a:=b*(-c)+b*(-c)
assign
bb
+
*
c c
a
*
uminusuminus
Uzly - operátory
Listy - operandy
Vnitřní reprezentace programu 6
Grafová reprezentace
DAG (Directed Acyclic Graph) a:=b*(-c)+b*(-c)
assign
b
+
*
c
a
uminus
Společné podvýrazy jako sdílené uzly
Používá se pro optimalizaci
Vnitřní reprezentace programu 7
Příklad
var n, f: Integer;
begin read n; f:=1; while n>1 do begin f:=f*n; n:=n-1 end; write f,”\n”end.
Vnitřní reprezentace programu 8
Grafová reprezentace
read
seq
:=
n 1f >
while
1n
write
seq \nf
:= :=
f *
f n
n -
n 1
Vnitřní reprezentace programu 9
Zásobníkový kód
Postfixová notacea b c uminus * b c uminus * + assign výsledek průchodu AST nebo DAG typu post-
order uzel následuje bezprostředně za svými
následníky žádný formální rozdíl mezi operandy a
operátory
Vnitřní reprezentace programu 10
Zásobníkový kód
Virtuální zásobníkový procesorload b (b) vrchol zás. vpravoload c (b) (c)inv (b) (-c)mul (b*-c)load b (b*-c) (b)load c (b*-c) (b) (c)inv (b*-c) (b) (-c)mul (b*-c) (b*-c)add (b*-c+b*-c)store a
Vnitřní reprezentace programu 11
Zásobníkový kód
Virtuální zásobníkový procesor virtuální počítač s pamětí a zásobníkem P-kód (Wirth)
přenositelný mezikód pro Pascal specializované procesory
Java Virtual Machine MSIL – Microsoft Intermediate Language
(.NET – C#, C++, VB, …)
Vnitřní reprezentace programu 12
Příklad - JVM
public class Priklad {
public static void main(String[] args) {
int x = 1;
System.out.println(x + 2);
}
}
Vnitřní reprezentace programu 13
Příklad - JVM
0: iconst_1 1: istore_1 2: getstatic #2; //java/lang/System.out
5: iload_1 6: iconst_2 7: iadd 8: invokevirtual #3; //java/io/PrintStream.println11: return
Vnitřní reprezentace programu 14
Příklad - MSIL
using System;
public class Priklad {
public static void Main(string[] args) {
int x = 1;
Console.WriteLine(x + 2);
}
}
Vnitřní reprezentace programu 15
Příklad - MSIL.method public static void Main(string[] args) { .entrypoint .maxstack 2 .locals init (int32 V_0) ldc.i4.1 stloc.0 ldloc.0 ldc.i4.2 add call void System.Console::WriteLine(int32) ret}
Vnitřní reprezentace programu 16
Tříadresový kód
x := y op z x - (dočasná) proměnná y, z - (dočasné) proměnné, konstanty
Operandy nemohou být výrazy rozklad na primitivní výrazy s dočasnými
proměnnými Explicitní odkazy na operandy
možnost přesouvání příkazů při optimalizaci
Vnitřní reprezentace programu 17
Příklad 1
a:=b*(-c)+b*(-c)
t1 := -c t1 := -c t2 := b*t1 t2 := b*t1 t3 := -c t5 := t2+t2 t4 := b*t3 a := t5 t5 := t2+t4 a := t5 Strom DAG
dočasné proměnné = vnitřní uzly stromu (DAG)
Vnitřní reprezentace programu 18
Příklad 2
var n,f:integer;begin 1: read n read n; 2: f := 1 f:=1; 3: if n<=1 goto 7 while n>1 do begin 4: f := f * n f:=f*n; n:=n-1 5: n := n - 1 end; 6: goto 3 write f,"\n" 7: write f end. 8: write "\n"
Vnitřní reprezentace programu 19
Příkazy tříadresového kódu x := y op z op – binární operátor x := op y op - unární operátor
(-, not, typová konverze, …)
x := y goto L nepodmíněný skok if x relop y goto L podmíněný skok
Vnitřní reprezentace programu 20
Příkazy tříadresového kódu
param x1
… param xn volání podprogramucall p,n p(x1,…,xn)
return y návrat z podprogramu
Vnitřní reprezentace programu 21
Příkazy tříadresového kódu x := y[j]
x[j] := y indexování
x := &y reference (získání adresy)
x := *y*x := y dereference ukazatele
Vnitřní reprezentace programu 22
Čtveřice
op arg1 arg2 výsledek
(0) uminus c t1(1) * b t1 t2(2) uminus c t3(3) * b t3 t4(4) + t2 t4 t5(5) := t5 a
a:=b*(-c)+b*(-c)
Vnitřní reprezentace programu 23
Příklad – překlad výrazů
Atributy id.name – jméno identifikátoru E.place – jméno proměnné obsahující hodnotu E
Pomocné funkce newtemp – vytvoří novou proměnnou lookup – vyhledá proměnnou v tabulce emit – generuje instrukci error – hlášení chyby
Vnitřní reprezentace programu 24
Příklad – překlad výrazů
S -> id := E { p = lookup(id.name); if( p != null ) emit(p,‘:=’,E.place); else error(); }
E -> E1 + E2 { E.place = newtemp(); emit(E.place,‘:=’,
E1.place,’+’,E2.place);}
E -> E1 * E2 { E.place := newtemp(); emit(E.place,‘:=’,
E1.place,’*’,E2.place);}
Vnitřní reprezentace programu 25
Příklad – překlad výrazů
E -> - E1 { E.place = newtemp(); emit(E.place,‘:=’,
‘uminus’,E1.place);}
E -> (E1) { E.place = E1.place; }
E -> id { p := lookup(id.name);
if( p != null ) E.place := p; else error(); }
Vnitřní reprezentace programu 26
array [low..high] of T
prvek a[j] leží na adrese:
base+(j-low)*w = j*w+(base-low*w) =konstanta!
Přístup k prvkům pole
low low+1 highw=sizeof(T)
base
Vnitřní reprezentace programu 27
Přístup k prvkům pole
a[j1,j2] base+((j1-low1)*n2+j2-low2)*w =>
((j1*n2)+j2)*w+(base-((low1*n2)+low2)*w)=konstanta!
base
low1
low2
high1
n2 := high2-low2+1
high2
Vnitřní reprezentace programu 28
Přístup k prvkům pole
Obecně: a[j1, … , jk] addresa:
(…(j1n2+j2)n3+j3)…)nk+jk)*w + base-(…(low1n2+low2)n3+low3)…)nk+lowk)*w
mapovací funkce nj = highj-lowj+1
Vnitřní reprezentace programu 29
Překlad výrazů s indexy
S -> L := EE -> E1 + E2 | (E1) | LL -> Elst ] | idElst -> Elst1 , E | id [ E
Vnitřní reprezentace programu 30
Překlad výrazů s indexy
L.offsetindex (null=bez indexu)
L.placeproměnná
E.placeproměnná s hodnotou
id.place
Elst.array popis pole
Elst.ndim počet rozměrů
Elst.place proměnná obsahující
index
Vnitřní reprezentace programu 31
Překlad výrazů s indexy
const(Elst.array) konstantní část mapovací funkce
width(Elst.array) velikost prvku pole
limit(Elst.array,m) počet prvků v m-té dimenzi
Vnitřní reprezentace programu 32
Překlad výrazů s indexy
S -> L := E{ if( L.offset==null ) /* bez indexu */ emit(L.place,‘:=’,E.place); else emit(L.place,‘[’,L.offset,‘]’, ‘:=’,E.place); }
E -> E1 + E2
{ E.place = newtemp(); emit(E.place,‘:=’,E1.place, ‘+’,E2.place); }
Vnitřní reprezentace programu 33
Překlad výrazů s indexy
E -> (E1){ E.place = E1.place }
E -> L{ if( L.offset==null ) /* bez indexu */ E.place = L.place; else { E.place = newtemp(); emit(E.place,‘:=’,L.place, ‘[’,L.offset,‘]’) }}
Vnitřní reprezentace programu 34
Překlad výrazů s indexy
L -> Elst ]{ L.place = newtemp(); L.offset = newtemp(); emit(L.place,‘:=’,const(Elst.array)); emit(L.offset,‘:=’,Elst.place,‘*’, width(Elst.array)); }
L -> id{ L.place = id.place; L.offset = null; }
Vnitřní reprezentace programu 35
Překlad výrazů s indexy
Elst -> Elst1 , E{ t = newtemp(); m = Elst1.ndim+1; emit(t,‘:=’,Elst1.place,‘*’, limit(Elst1.array,m)); emit(t,‘:=’,t,‘+’,E.place); Elst.array = Elst1.array; Elst.place = t; Elst.ndim = m;}
Vnitřní reprezentace programu 36
Překlad výrazů s indexy
Elst -> id [ E{ Elst.array = id.place; Elst.place = E.place; Elst.ndim = 1;}
Vnitřní reprezentace programu 37
Příklad
A: array [1..10,1..20] of integer; sizeof(integer) = 4 n1 = 10
n2 = 20w = 4
x := A[y, z]
Vnitřní reprezentace programu 38
Příklad
x := A[y, z]
t1 := y*20t2 := t1+zt3 := c /* konstanta c = &A-84 */t4 := 4*t2 (1*20+1)*4=84t5 := t3[t4]x := t5
Vnitřní reprezentace programu 39
Překlad logických výrazů E -> E or E
| E and E | (E) | not E | id relop id | true | false
Vnitřní reprezentace programu 40
Překlad logických výrazů Reprezentace logických hodnot celými čísly:
true=1, false=0
a or b and not c x<y1: t1 := not c 1: if x<y goto 42: t2 := b and t1 2: t1 := 03: t3 := a or t2 3: goto 54: … 4: t1 := 1
5: …
Vnitřní reprezentace programu 41
Překlad logických výrazů
Zkrácené vyhodnocení reprezentace logických hodnot tokem řízení
(pozicí v programu)
a<b or c<d and e<fif a<b goto Ltruegoto L1
L1: if c<d goto L2goto Lfalse
L2: if e<f goto Ltruegoto Lfalse
Vnitřní reprezentace programu 42
Překlad řídicích příkazů
Instrukce zásobníkového kódu: LBL L – definice návěští L pro skok JMP L – nepodmíněný skok na návěští L FJP L - podmíněný skok na návěští L, pokud
je na vrcholu zásobníku False
výstupní symboly překladové gramatiky - {LBL} Pomocné funkce:
getLbl() – vygeneruje nové číslo návěští
zanoření příkazů – nelze použít konstanty!
Vnitřní reprezentace programu 43
Překlad příkazu IF
S -> if ( E ) S <E> FJP L1 <S> LBL L1
S -> if ( E ) {FJP} S {LBL} FJP.l = LBL.l = getLbl();
E
S
FJP L1
LBL L1
Vnitřní reprezentace programu 44
Překlad příkazu IF
S -> if ( E ) S1 else S2
S -> X {LBL}
LBL.l = X.l
S -> X {JMP} {LBL1} else S {LBL2} JMP.l = LBL2.l = getLbl();LBL1.l = X.l
X -> if (E) {FJP} S
FJP.l = getLbl()
E
FJP L1
S1
S1
JMP L2L1:
L2:
Vnitřní reprezentace programu 45
Překlad příkazu WHILE
S -> while ( E ) S LBL L1 <E> FJP L2 <S> JMP L1 LBL L2
E
S
L1:
L2:
FJP L2
JMP L1
Vnitřní reprezentace programu 46
Překlad příkazu WHILE
S -> {LBL1} while ( E ) {FJP2} S {JMP1} {LBL2}LBL1.l = JMP1.l = getLbl();LBL2.l = FJP.l = getLbl();
S -> break/continue ; S.blab – dědičný atribut, návěští pro break S.clab – dědičný atribut, návěští pro continue while musí zajistit předání návěští speciální hodnota návěští – poznáme, že nejsme uvnitř
cyklu, break/continue může hlásit chybu