中間代碼生成

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

[3]array(3,int)int

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

若T

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

笛卡爾乘積構造符

若T1

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

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

笛卡爾乘積構造符

函數構造符→若T1、T2、…、Tn和R是類型表達式，則T1

T2

…

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

笛卡爾乘積構造符

函數構造符→記錄構造符record若有標識符N1

、N2

、…、Nn與類型表達式T1、T2

、…、Tn，則record((N1

T1

)

(N2

T2

)

…

(Nn

Tn))

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

record((name

array(8,char))

(score

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

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

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

int

score;};stype[50]table;stype*p;對于聲明語句，語義分析的主要任務就是收集標識符的類型等屬性信息，并為每一個名字分配一個相對地址從類型表達式可以知道該類型在運行時刻所需的存儲單元數量，稱為類型的寬度(width)在編譯時刻，可以使用類型的寬度為每一個名字分配一個相對地址局部變量的存儲分配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):在符號表中為名字name創建記錄，將name的類型設置為type，相對地址設置為offset

變量作用offset下一個可用的相對地址t,w將類型和寬度信息從語法分析樹中的B結點傳遞到對應于產生式C→ε的結點符號綜合屬性Btype,widthCtype,widthTtype,width變量聲明語句的SDT

例：“realx;inti;”的語法制導翻譯①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)例：數組類型表達式“int[2][3]”的語法制導翻譯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開關語句的翻譯6.6過程調用語句的翻譯提綱6.2賦值語句的翻譯166.2.1簡單賦值語句的翻譯6.2.2數組引用的翻譯6.2.1簡單賦值語句的翻譯17賦值語句的基本文法①S

id=E；②E

E1

+E2③E

E1

*E2④E

E1

⑤E

(E1)⑥E

id賦值語句翻譯的主要任務生成對表達式求值的三地址碼例源程序片段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)：查詢符號表返回name

對應的記錄newtemp()：生成一個新的臨時變量t，返回t的地址gen(code)：生成三地址指令code符號綜合屬性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()不僅要構造出一個新的三地址指令，還要將它添加到至今為止已生成的指令序列之后①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]將數組引用翻譯成三地址碼時要解決的主要問題是確定數組元素的存放地址，也就是數組元素的尋址6.2.2數組引用的翻譯一維數組假設每個數組元素的寬度是w，則數組元素a[i]的相對地址是：base+i

w

其中，base是數組的基地址，i

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

base+i1

w1+i2

w2k維數組數組元素a[i1][i2]…[ik]的相對地址是：

base+i1

w1+i2

w2+…+ik

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

一個整型變量占用4個字節，

則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假設type(a)=array(n,int)，源程序片段c=a[i];三地址碼t1=i*4t2=a[t1]c=t2addr(a[i])=base+i*4帶有數組引用的賦值語句的翻譯例2假設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帶有數組引用的賦值語句的翻譯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生成的數組元素的類型L.offset：指示一個臨時變量，該臨時變量用于累加公式中的ij×wj項，從而計算數組引用的偏移量L.array：數組名在符號表的入口地址假設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]數組引用的SDT數組引用的SDT假設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開關語句的翻譯6.6過程調用語句的翻譯提綱控制流語句的基本文法P

SS

S1

S2S

id

=E;|L=E; S

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

if

B

then

S1

else

S2布爾表達式B被翻譯成由跳轉指令構成的跳轉代碼繼承屬性S.next：是一個地址，該地址中存放了緊跟在S代碼之后的指令(S的后繼指令)的標號B.true：是一個地址，該地址中存放了當B為真時控制流轉向的指令的標號B.false：是一個地址，該地址中存放了當B為假時控制流轉向的指令的標號用指令的標號標識一條三地址指令S1.nextS2.nextS.nextifB.trueB.falsethengotoS.nextelseB.codeS1.codeS2.codeS.code控制流語句的代碼結構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):將下一條三地址指令的標號賦給Lnewlabel():生成一個用于存放標號的新的臨時變量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優先級：not

>and>

orrelop（關系運算符）：<,<=,=,!=,>,>=關系表達式布爾表達式的基本文法在跳轉代碼中，邏輯運算符&&、||和!被翻譯成跳轉指令。運算符本身不出現在代碼中，布爾表達式的值是通過代碼序列中的位置來表示的例語句三地址代碼 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;布爾表達式的基本文法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

布爾表達式的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開關語句的翻譯6.7過程調用語句的翻譯提綱基本思想生成一個跳轉指令時，暫時不指定該跳轉指令的目標標號。這樣的指令都被放入由跳轉指令組成的列表中。同一個列表中的所有跳轉指令具有相同的目標標號。等到能夠確定正確的目標標號時，才去填充這些指令的目標標號回填(Backpatching)B.truelist：指向一個包含跳轉指令的列表，這些指令最終獲得的目標標號就是當B為真時控制流應該轉向的指令的標號B.falselist：指向一個包含跳轉指令的列表，這些指令最終獲得的目標標號就是當B為假時控制流應該轉向的指令的標號非終結符B的綜合屬性makelist(i)創建一個只包含i的列表，i是跳轉指令的標號，函數返回指向新創建的列表的指針merge(p1,p2)將p1

和

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

i作為目標標號插入到p所指列表中的各指令中函數B

E1

relopE2{

B.truelist=makelist(nextquad);

B.falselist=makelist(nextquad+1);

gen(‘if’E1.addr

relop

E2.addr‘goto_’);

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

true{

B.truelist=makelist(nextquad);

gen(‘goto_’);}B

E1

relopE2布爾表達式的回填B

false{

B.falselist

=makelist(nextquad);

gen(‘goto_’);}B

trueB

E1

relopE2布爾表達式的回填B

(B1){

B.truelist=B1.truelist;

B.falselist=B1.falselist;}B

falseB

trueB

E1

relopE2布爾表達式的回填B

notB1{

B.truelist=B1.falselist;

B.falselist=B1.truelist;}B

(B1)B

falseB

trueB

E1

relopE2布爾表達式的回填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：指向一個包含跳轉指令的列表，這些指令最終獲得的目標標號就是按照運行順序緊跟在S代碼之后的指令的標號控制流語句的回填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