編譯原理 6 中間代碼生成學(xué)習(xí)課件

中間代碼生成

哈爾濱工業(yè)大學(xué)陳鄞第六章6.1聲明語句的翻譯6.2賦值語句的翻譯6.3控制語句的翻譯6.4回填6.5開關(guān)語句的翻譯6.6過程調(diào)用語句的翻譯提綱6.1聲明語句的翻譯3聲明語句翻譯的主要任務(wù)：收集標(biāo)識(shí)符的類型等屬性信息，并為每一個(gè)名字分配一個(gè)相對(duì)地址名字的類型和相對(duì)地址信息保存在相應(yīng)的符號(hào)表記錄中基本類型是類型表達(dá)式integercharrealbooleantype_error(出錯(cuò)類型)void(無類型)類型表達(dá)式(TypeExpressions)基本類型是類型表達(dá)式可以為類型表達(dá)式命名，類型名也是類型表達(dá)式將類型構(gòu)造符(typeconstructor)作用于類型表達(dá)式可以構(gòu)成新的類型表達(dá)式數(shù)組構(gòu)造符array若T是類型表達(dá)式，則array(I,T)是類型表達(dá)式(I是一個(gè)整數(shù))類型表達(dá)式(TypeExpressions)類型類型表達(dá)式int

[3]array(3,int)int

[2][3]array(2,array(3,int))基本類型是類型表達(dá)式可以為類型表達(dá)式命名，類型名也是類型表達(dá)式將類型構(gòu)造符(typeconstructor)作用于類型表達(dá)式可以構(gòu)成新的類型表達(dá)式數(shù)組構(gòu)造符array指針構(gòu)造符pointer

若T

是類型表達(dá)式，則pointer(T)是類型表達(dá)式，它表示一個(gè)指針類型類型表達(dá)式(TypeExpressions)基本類型是類型表達(dá)式可以為類型表達(dá)式命名，類型名也是類型表達(dá)式將類型構(gòu)造符(typeconstructor)作用于類型表達(dá)式可以構(gòu)成新的類型表達(dá)式數(shù)組構(gòu)造符array指針構(gòu)造符pointer

笛卡爾乘積構(gòu)造符

若T1

和T2是類型表達(dá)式，則笛卡爾乘積T1

T2是類型表達(dá)式類型表達(dá)式(TypeExpressions)基本類型是類型表達(dá)式可以為類型表達(dá)式命名，類型名也是類型表達(dá)式將類型構(gòu)造符(typeconstructor)作用于類型表達(dá)式可以構(gòu)成新的類型表達(dá)式數(shù)組構(gòu)造符array指針構(gòu)造符pointer

笛卡爾乘積構(gòu)造符

函數(shù)構(gòu)造符→若T1、T2、…、Tn和R是類型表達(dá)式，則T1

T2

…

Tn→R是類型表達(dá)式類型表達(dá)式(TypeExpressions)基本類型是類型表達(dá)式可以為類型表達(dá)式命名，類型名也是類型表達(dá)式將類型構(gòu)造符(typeconstructor)作用于類型表達(dá)式可以構(gòu)成新的類型表達(dá)式數(shù)組構(gòu)造符array指針構(gòu)造符pointer

笛卡爾乘積構(gòu)造符

函數(shù)構(gòu)造符→記錄構(gòu)造符record若有標(biāo)識(shí)符N1

、N2

、…、Nn與類型表達(dá)式T1、T2

、…、Tn，則record((N1

T1

)

(N2

T2

)

…

(Nn

Tn))

是一個(gè)類型表達(dá)式類型表達(dá)式(TypeExpressions)設(shè)有C程序片段：和stype綁定的類型表達(dá)式

record((name

array(8,char))

(score

integer))和table綁定的類型表達(dá)式

array(50,stype)和p綁定的類型表達(dá)式

pointer(stype)例structstype{ char[8]name;

int

score;};stype[50]table;stype*p;對(duì)于聲明語句，語義分析的主要任務(wù)就是收集標(biāo)識(shí)符的類型等屬性信息，并為每一個(gè)名字分配一個(gè)相對(duì)地址從類型表達(dá)式可以知道該類型在運(yùn)行時(shí)刻所需的存儲(chǔ)單元數(shù)量，稱為類型的寬度(width)在編譯時(shí)刻，可以使用類型的寬度為每一個(gè)名字分配一個(gè)相對(duì)地址局部變量的存儲(chǔ)分配P→{offset=0}DD→Tid;{enter(id.lexeme,T.type,offset);

offset=offset+T.width;}D

D→εT→B

{t=B.type;w=B.width;}

C

{T.type=C.type;T.width=C.width;

}T→↑T1{T.type=pointer(T1.type);T.width=4;}B→int{B.type=int;B.width=4;}B→real{B.type=real;B.width=8;}C→ε{C.type=t;C.width=w;

}C→[num]C1

{C.type=array(num.val,C1.type);

C.width=num.val*C1.width;}enter(name,type,offset):在符號(hào)表中為名字name創(chuàng)建記錄，將name的類型設(shè)置為type，相對(duì)地址設(shè)置為offset

變量作用offset下一個(gè)可用的相對(duì)地址t,w將類型和寬度信息從語法分析樹中的B結(jié)點(diǎn)傳遞到對(duì)應(yīng)于產(chǎn)生式C→ε的結(jié)點(diǎn)符號(hào)綜合屬性Btype,widthCtype,widthTtype,width變量聲明語句的SDT

例：“realx;inti;”的語法制導(dǎo)翻譯①P→{offset=0}

D②D→Tid;{enter(id.lexeme,T.type,offset);

offset=offset+T.width;}D

③D→ε④T→B

{t=B.type;w=B.width;}

C

{T.type=C.type;T.width=C.width;

}⑤T→↑T1{T.type=pointer(T1.type);T.width=4;}⑥B→int{B.type=int;B.width=4;}⑦B→real{B.type=real;B.width=8;}⑧C→ε{C.type=t;C.width=w;

}⑨C→[num]C1

{C.type=array(num.val,C1.type);

C.width=num.val*C1.width;}type=realwidth=8type=realwidth=8type=realwidth=8type=intwidth=4type=intwidth=4type=intwidth=4εoffset=0PD{a}Tid;D{a}BC{a}{a}real{a}ε{a}Tid;D{a}BC{a}{a}int{a}ε{a}t=real

w=8offset=8offset=12t=int

w=4enter(x,real,0)enter(i,int,8)例：數(shù)組類型表達(dá)式“int[2][3]”的語法制導(dǎo)翻譯type=intwidth=4type=array(2,array(3,int))width=24TBC{a}{a}int{a}]{a}[numC]{a}[numCε{a}type=intwidth=4type=array(3,int)width=12type=array(2,array(3,int))width=24t=intw=4①P→{offset=0}

D②D→Tid;{enter(id.lexeme,T.type,offset);

offset=offset+T.width;}D

③D→ε④T→B

{t=B.type;w=B.width;}

C

{T.type=C.type;T.width=C.width;

}⑤T→↑T1{T.type=pointer(T1.type);T.width=4;}⑥B→int{B.type=int;B.width=4;}⑦B→real{B.type=real;B.width=8;}⑧C→ε{C.type=t;C.width=w;

}⑨C→[num]C1

{C.type=array(num.val,C1.type);

C.width=num.val*C1.width;}6.1聲明語句的翻譯6.2賦值語句的翻譯6.3控制語句的翻譯6.4回填6.5開關(guān)語句的翻譯6.6過程調(diào)用語句的翻譯提綱6.2賦值語句的翻譯166.2.1簡單賦值語句的翻譯6.2.2數(shù)組引用的翻譯6.2.1簡單賦值語句的翻譯17賦值語句的基本文法①S

id=E；②E

E1

+E2③E

E1

*E2④E

E1

⑤E

(E1)⑥E

id賦值語句翻譯的主要任務(wù)生成對(duì)表達(dá)式求值的三地址碼例源程序片段x=(a+b)*c;三地址碼t1

=a+b

t2=t1*cx

=t2賦值語句的SDTS

id=E；{p=lookup(id.lexeme);if

p==nilthen

error;

S.code=E.code||

gen(p‘=’E.addr);E

E1

+E2{E.addr=newtemp();

E.code=E1.code||E2.code||

gen(E.addr‘=’E1.addr‘+’E2.addr);E

E1

*E2{E.addr=newtemp();

E.code=E1.code||E2.code||

gen(E.addr‘=’E1.addr‘*’E2.addr);E

E1

{E.addr=newtemp();

E.code=E1.code||

gen(E.addr‘=’‘uminus’E1.addr);E

(E1){E.addr=E1.addr;

E.code=E1.code;

E

id {E.addr=lookup(id.lexeme);ifE.addr==nilthen

error;

E.code=′′;lookup(name)：查詢符號(hào)表返回name

對(duì)應(yīng)的記錄newtemp()：生成一個(gè)新的臨時(shí)變量t，返回t的地址gen(code)：生成三地址指令code符號(hào)綜合屬性ScodeEcodeaddr}}}}}}增量翻譯(IncrementalTranslation)S

id=E；{p=lookup(id.lexeme);if

p==nilthen

error;

gen(p‘=’E.addr);E

E1

+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);E

E1

*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);

E

E1

{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);

E

(E1){E.addr=E1.addr;

E

id {E.addr=lookup(id.lexeme);ifE.addr==nilthen

error;

}}}}}}在增量方法中，gen()不僅要構(gòu)造出一個(gè)新的三地址指令，還要將它添加到至今為止已生成的指令序列之后①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例：x=(a+b)*c;idx$02=3(6ida7例例：x=(a+b)*c;idx$02=3(6Ea12+9idb7①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例例：x=(a+b)*c;idx$02=3(6Ea12+9Eb13t1=a+b

①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例例：x=(a+b)*c;idx$02=3(6Et112t1=a+b

)15①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例例：x=(a+b)*c;idx$02=3Et14t1=a+b

*10idc7①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例例：x=(a+b)*c;idx$02=3Et14t1=a+b

*10Ec14t2=t1*c①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例例：x=(a+b)*c;idx$02=3Et24t1=a+b

t2=t1*c;8x

=t2①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例例：x=(a+b)*c;$0S1t1

=a+b

t2=t1*cx

=t2①S

id=E;{p=lookup(id.lexeme); if

p==nilthen

error;

gen(p‘=’E.addr);}②E

E1+E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘+’E2.addr);}③E

E1*E2{E.addr=newtemp();

gen(E.addr‘=’E1.addr‘*’E2.addr);}④E

E1{E.addr=newtemp();

gen(E.addr‘=’‘uminus’E1.addr);}⑤E

(E1){E.addr=E1.addr;}⑥E

id{E.addr=lookup(id.lexeme);

if

E.addr==nilthen

error;

}例賦值語句的基本文法

S

id

=E;|L=E;

E

E1

+E2

|

E1

|(E1)|

id

|L

L

id

[E]|L1

[E]將數(shù)組引用翻譯成三地址碼時(shí)要解決的主要問題是確定數(shù)組元素的存放地址，也就是數(shù)組元素的尋址6.2.2數(shù)組引用的翻譯一維數(shù)組假設(shè)每個(gè)數(shù)組元素的寬度是w，則數(shù)組元素a[i]的相對(duì)地址是：base+i

w

其中，base是數(shù)組的基地址，i

w是偏移地址二維數(shù)組假設(shè)一行的寬度是w1，同一行中每個(gè)數(shù)組元素的寬度是w2，則數(shù)組元素a[i1][i2]的相對(duì)地址是：

base+i1

w1+i2

w2k維數(shù)組數(shù)組元素a[i1][i2]…[ik]的相對(duì)地址是：

base+i1

w1+i2

w2+…+ik

wkw1→a[i1]的寬度w2→a[i1][i2]的寬度…wk→a[i1][i2]…[ik]的寬度偏移地址偏移地址數(shù)組元素尋址(AddressingArrayElements)例假設(shè)type(a)=array(3,array(5,array(8,int)))，

一個(gè)整型變量占用4個(gè)字節(jié)，

則addr(a[i1][i2][i3])=base+i1*w1+i2*w2

+i3*w3=base+i1*160+i2*32+i3*4a[i1]的寬度a[i1][i2]的寬度a[i1][i2][i3]的寬度例1假設(shè)type(a)=array(n,int)，源程序片段c=a[i];三地址碼t1=i*4t2=a[t1]c=t2addr(a[i])=base+i*4帶有數(shù)組引用的賦值語句的翻譯例2假設(shè)type(a)=array(3,array(5,int))，源程序片段

c=a[i1][i2];三地址碼t1=i1*20t2=i2*4t3=t1+t2

t4=a[t3]c

=t4addr(a[i1][i2])=base+i1*20

+i2*4帶有數(shù)組引用的賦值語句的翻譯t1t2賦值語句的基本文法

S

id

=E;|L=E;

E

E1+E2|

E1|(E1)|

id

|L

L

id

[E]|L1

[E]base+i1

w1+i2

w2+…+ik

wkL的綜合屬性L.type：L生成的數(shù)組元素的類型L.offset：指示一個(gè)臨時(shí)變量，該臨時(shí)變量用于累加公式中的ij×wj項(xiàng)，從而計(jì)算數(shù)組引用的偏移量L.array：數(shù)組名在符號(hào)表的入口地址假設(shè)type(a)=array(3,array(5,array(8,int)))，翻譯語句片段“a[i1][i2][i3]”offset=i1

160type=array(5,array(8,int))type=array(

8,int)type=intoffset=i1

160+i2

32offset=i1

160+i2

32+i3

4array=aarray=aarray=aLid(a)id(i1)[E]Lid(i2)[E]Lid(i3)[E]數(shù)組引用的SDT數(shù)組引用的SDT假設(shè)type(a)=array(3,array(5,array(8,int)))，

翻譯語句片段“a[i1][i2][i3]”offset=t1type=array(5,array(8,int))type=array(

8,int)type=intoffset=t3offset=t5addr=t6array=aarray=aarray=aELLid(i2)id(a)id(i1)Lid(i3)[E][E][E]addr=i1addr=i2addr=i3三地址碼t1=i1*160t2=i2*32t3=t1+t2t4=i3*4t5=t3+t4t6=a[t5]addr(a[i1][i2][i3])=base+i1

w1+i2

w2+i3

w3t1t2t4S

id=E；

|L=E;{gen(L.array‘[’L.offset‘]’‘=’E.addr);}E

E1+E2

|

E1|(E1)|id |L

{E.addr=newtemp();gen(E.addr‘=’L.array

‘[’L.offset‘]’);}L

id

[E]{L.array=lookup(id.lexeme);ifL.array==nilthen

error;

L.type=L.array.type.elem;

L.offset=newtemp();

gen(L.offset‘=’E.addr‘*’L.type.width);}

|L1[E]{L.array=L1.array;

L.type=L1.type.elem;

t=newtemp();

gen(t‘=’E.addr‘*’L.type.width);

L.offset=newtemp();

gen(L.offset‘=’L1.offset‘+’t);}6.1聲明語句的翻譯6.2賦值語句的翻譯6.3控制流語句的翻譯6.4回填6.5開關(guān)語句的翻譯6.6過程調(diào)用語句的翻譯提綱控制流語句的基本文法P

SS

S1

S2S

id

=E;|L=E; S

ifBthenS1 |ifBthenS1elseS2 |whileBdoS16.3控制流語句的翻譯例S

if

B

then

S1

else

S2布爾表達(dá)式B被翻譯成由跳轉(zhuǎn)指令構(gòu)成的跳轉(zhuǎn)代碼繼承屬性S.next：是一個(gè)地址，該地址中存放了緊跟在S代碼之后的指令(S的后繼指令)的標(biāo)號(hào)B.true：是一個(gè)地址，該地址中存放了當(dāng)B為真時(shí)控制流轉(zhuǎn)向的指令的標(biāo)號(hào)B.false：是一個(gè)地址，該地址中存放了當(dāng)B為假時(shí)控制流轉(zhuǎn)向的指令的標(biāo)號(hào)用指令的標(biāo)號(hào)標(biāo)識(shí)一條三地址指令S1.nextS2.nextS.nextifB.trueB.falsethengotoS.nextelseB.codeS1.codeS2.codeS.code控制流語句的代碼結(jié)構(gòu)P

{S.next=newlabel();}S{label(S.next);}S

{S1.next=newlabel();}S1

{label(S1.next);S2.next=S.next;}S2

S

id

=E;|L=E; S

if

B

then

S1 |if

B

then

S1

else

S2 |while

B

do

S1label(L):將下一條三地址指令的標(biāo)號(hào)賦給Lnewlabel():生成一個(gè)用于存放標(biāo)號(hào)的新的臨時(shí)變量L，返回變量地址控制流語句的SDTS

if

B

then

S1

else

S2S

if

{B.true=newlabel();B.false=newlabel();}B

then

{label(B.true);S1.next=S.next;}S1

{gen(‘goto’S.next)}

else

{label(B.false);S2.next=S.next;}S2

ifB.trueB.falseS.nextthengotoS.nextelseS1.nextS2.nextB.codeS1.codeS2.codeS.codeif-then-else語句的SDTS

if

B

then

S1S

if

{B.true=newlabel();B.false=S.next;}B

then

{label(B.true);S1.next=S.next;}S1ifB.trueB.falseS.nextthenS1.nextB.codeS1.codeS.codeif-then語句的SDTS

while

B

do

S1

S

while

{S.begin=newlabel();

label(S.begin);

B.true=newlabel();

B.false=S.next;}B

do

{label(B.true);S1.next=S.begin;}S1

{gen(‘goto’S.begin);}whileB.trueB.falseS.begindogotoS.beginS1.nextB.codeS1.codeS.nextS.codewhile-do語句的SDT

B→BorB

|BandB

|notB

|(B) |E

relop

E

|true |false優(yōu)先級(jí)：not

>and>

orrelop（關(guān)系運(yùn)算符）：<,<=,=,!=,>,>=關(guān)系表達(dá)式布爾表達(dá)式的基本文法在跳轉(zhuǎn)代碼中，邏輯運(yùn)算符&&、||和!被翻譯成跳轉(zhuǎn)指令。運(yùn)算符本身不出現(xiàn)在代碼中，布爾表達(dá)式的值是通過代碼序列中的位置來表示的例語句三地址代碼 if

x<100goto

L2 goto

L3L3

: if

x>200gotoL4 goto

L1

L4

: if

x!=y

goto

L2 goto

L1

L2

:

x=0L1

:if(x<100||x>200&&x!=y) x=0;布爾表達(dá)式的基本文法B→E1relopE2{gen('if'

E1.addr

relop

E2.addr'goto'

B.true)；

gen('goto'B.false);}B→true{gen('goto'

B.true);}

B→false{gen('goto'

B.false);}

B→({B1.true=B.

true;B1.false=B.false;}B1)B→not{B1.true=B.false;B1.false=B.true;}B1

布爾表達(dá)式的SDTB→B1orB2的SDTB→B1orB2

B→{B1.true=B.true;B1.false=newlabel();}B1

or{label(B1.false);B2.true=B.true;B2.false=B.false;}B2B.falseB1.falseB2.falseB1.trueB2.trueB.trueorB1.codeB2.codeB.codeB→B1

and

B2

B→{B1.true=newlabel();B1.false=B.false;}B1

and

{label(B1.true);B2.true=B.true;B2.false=B.false;}B2B.falseB1.falseB2.falseB1.trueB2.trueB.trueandB1.codeB2.codeB.codeB→B1andB2的SDTP

{a}S{a}S

{a}S1{a}S2S

id=E;{a}|L=E;{a}

E

E1+E2{a}|

E1{a}|

(E1){a}|

id{a}|L{a}L

id[E]{a}|L1[E]{a}S

if{a}Bthen{a}S1|if{a}Bthen{a}S1else{a}S2|while{a}Bdo{a}S1{a}B→{a}Bor{a}B|{a}Band{a}B|not{a}B|({a}B)|E

relop

E{a}|true{a}|false{a}控制流語句的SDT例while

a<b

do

ifc<d

thenx=y+z;

else

x=y–z;S1S3S2BB1dothenS3elseSPB1c<dS1x=y+zifa<bBwhileS2x=y-z例P

{S.next=newlabel();}S{label(S.next);}dothenS3elseSB1c<dS1x=y+zPS.n=L1whileifa<bBS2x=y-z例S

while{S.begin=newlabel();

label(S.begin);

B.true=newlabel();

B.false=S.next;}B

do{label(B.true);

S1.next=S.begin;}S1

{gen(‘goto’S.begin);}S3.n=L2S.begin=L2=1B→E1

relopE2

{gen(‘if’E1.addr

relop

E2.addr‘goto’B.true);gen('goto'B.false);}dowhilethenS3elseSB1c<dS1x=y+zP

1:if

a<b

goto

L32:goto

L1

goto

L2S.n=L1S2x=y-zifa<bB.t=L3B.f=L1=3B例S

if{B.true=newlabel();B.false=newlabel();}B

then

{label(B.true);S1.next=S.next;}S1

{gen(‘goto’S.next);}

else

{label(B.false);

S2.next=S.next;}S2B1.t=L4B1.f=L5S1.n=L2S2.n=L2=5=8S3.n=L2S.n=L1doifthenS3elseSBa<bB1c<dS1x=y+zS2x=y-zP

1:if

a<b

goto

L32:goto

L13:if

c<d

goto

L44:goto

L55:t1=y+z6:x=t17:goto

L28:t2

=y-z9:x=t210:11:goto

L2=11whileB.t=L3B.f=L1=33115811S.begin=L2=1

1:if

a<b

goto32:goto113:if

c<d

goto54:goto85:t1=y+z6:x=t17:goto18:t2

=y-z9:x=t210:goto111:

1:(j<,a,b,3

)2:

(j,-,-,11)3:

(j<,c,d,5)4:

(j,-,-,8)5:

(+,y,z,t1)6:

(=,t1,-,x)7:

(j,-,-,1)8:

(-,y,z,t2)9:

(=,t2,-,x)10:

(j,-,-,1)11:

語句“whilea<bdoifc<dthenx=y+zelsex=y-z”的三地址代碼6.1中間語言6.2聲明語句的翻譯6.3賦值語句的翻譯6.4控制語句的翻譯6.5回填6.6開關(guān)語句的翻譯6.7過程調(diào)用語句的翻譯提綱基本思想生成一個(gè)跳轉(zhuǎn)指令時(shí)，暫時(shí)不指定該跳轉(zhuǎn)指令的目標(biāo)標(biāo)號(hào)。這樣的指令都被放入由跳轉(zhuǎn)指令組成的列表中。同一個(gè)列表中的所有跳轉(zhuǎn)指令具有相同的目標(biāo)標(biāo)號(hào)。等到能夠確定正確的目標(biāo)標(biāo)號(hào)時(shí)，才去填充這些指令的目標(biāo)標(biāo)號(hào)回填(Backpatching)B.truelist：指向一個(gè)包含跳轉(zhuǎn)指令的列表，這些指令最終獲得的目標(biāo)標(biāo)號(hào)就是當(dāng)B為真時(shí)控制流應(yīng)該轉(zhuǎn)向的指令的標(biāo)號(hào)B.falselist：指向一個(gè)包含跳轉(zhuǎn)指令的列表，這些指令最終獲得的目標(biāo)標(biāo)號(hào)就是當(dāng)B為假時(shí)控制流應(yīng)該轉(zhuǎn)向的指令的標(biāo)號(hào)非終結(jié)符B的綜合屬性makelist(i)創(chuàng)建一個(gè)只包含i的列表，i是跳轉(zhuǎn)指令的標(biāo)號(hào)，函數(shù)返回指向新創(chuàng)建的列表的指針merge(p1,p2)將p1

和

p2指向的列表進(jìn)行合并，返回指向合并后的列表的指針backpatch(p,i)將

i作為目標(biāo)標(biāo)號(hào)插入到p所指列表中的各指令中函數(shù)B

E1

relopE2{

B.truelist=makelist(nextquad);

B.falselist=makelist(nextquad+1);

gen(‘if’E1.addr

relop

E2.addr‘goto_’);

gen(‘goto_’);}布爾表達(dá)式的回填B

true{

B.truelist=makelist(nextquad);

gen(‘goto_’);}B

E1

relopE2布爾表達(dá)式的回填B

false{

B.falselist

=makelist(nextquad);

gen(‘goto_’);}B

trueB

E1

relopE2布爾表達(dá)式的回填B

(B1){

B.truelist=B1.truelist;

B.falselist=B1.falselist;}B

falseB

trueB

E1

relopE2布爾表達(dá)式的回填B

notB1{

B.truelist=B1.falselist;

B.falselist=B1.truelist;}B

(B1)B

falseB

trueB

E1

relopE2布爾表達(dá)式的回填B

B1orMB2{

backpatch(B1.falselist,M.quad);

B.truelist=merge(B1.truelist,B2.truelist

);

B.falselist=B2.falselist;}M

ε{ M.quad=nextquad;}M.quadB.falselistB1.falselistB2.falselistB1.truelistB2.truelistB.truelistorB1.codeB2.codeB

B1orB2B

B1

andMB2{

backpatch(B1.truelist,M.quad);

B.truelist=B2.truelist;

B.falselist=merge(B1.falselist,B2.falselist);}M.quadB.falselistB1.falselistB2.falselistB1.truelistB2.truelistB.truelistandB1.codeB2.codeB

B1andB2t={100}f={101}<abor<cd<ef100:ifa<bgoto_101:goto_B

E1

relopE2{ B.truelist=makelist(nextquad);

B.falselist=makelist(nextquad+1);

gen(‘if’E1.addr

relop

E2.addr‘goto_’);

gen(‘goto_’);}andB例q=102t={102}f={103}102:ifc<d

goto_103:goto_MBB

B1orMB2{

backpatch(B1.falselist,M.quad);

B.truelist=merge(B1.truelist,B2.truelist);

B.falselist=B2.falselist;}M

ε{ M.quad=nextquad;}t={100}f={101}<abor<cd<ef100:ifa<bgoto_101:goto_andB例t={104}f={103,105}t={104}f={105}q=104104:if

e<f

goto_105:goto_MB104B

B1andMB2{

backpatch(B1.truelist,M.quad);

B.truelist=B2.truelist;

B.falselist=merge(B1.falselist,B2.falselist);}Bq=102t={102}f={103}MBt={100}f={101}<abor<cd<efandB102:ifc<d

goto_103:goto_100:ifa<bgoto_101:goto_例t={100,104}f={103,105}B102tfB

B1

or

MB2{

backpatch(B1.falselist,M.quad);

B.truelist=merge(B1.truelist,B2.truelist);

B.falselist=B2.falselist;}104t={104}f={103,105}t={104}f={105}q=104MBBq=102t={102}f={103}MBt={100}f={101}<abor<cd<efandB104:if

e<f

goto_105:goto_102:ifc<d

goto_103:goto_100:ifa<bgoto_101:goto_例文法S

S1

S2S

id

=E;|L=E; S

if

B

then

S1 |if

B

then

S1

else

S2 |while

B

do

S1綜合屬性S.next1ist：指向一個(gè)包含跳轉(zhuǎn)指令的列表，這些指令最終獲得的目標(biāo)標(biāo)號(hào)就是按照運(yùn)行順序緊跟在S代碼之后的指令的標(biāo)號(hào)控制流語句的回填S

ifB

thenMS1{ backpatch(B.truelist,M.quad); S.nextlist=merge(B.falselist,S1.nextlist);}M.quadifB.truelistB.falselistS.nextlistS1.nextlistthenB.codeS1.codeS

if

B

then

S1S

if

B

then

S1elseS2S

ifB

then

M1S1

N

else

M2S2{

backpatch(B.truelist,M1.quad);

backpatch(B.falselist,M2.quad);

S.nextlist=merge(merge(S1.nextlist,N.nextlist),S2.nextlist);}N

ε

{N.nextlist=makelist(nextquad);gen(‘goto_’);}M1.quadM2.quadN.nextlistifB.truelistB.falselistS.nextlistS1.nextlistthenS2.nextlistelseB.codegoto-S1.codeS2.codeS

while

B

do

S1S

whil