编译原理 6 中间代码生成学习课件

中间代码生成

哈尔滨工业大学陈鄞第六章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