第7章语义分析和中间代码产生

1、第七章语义分析和中间代码产生第七章语义分析和中间代码产生优化器优化器语法分析器语法分析器静态检查器静态检查器中间代码产生器中间代码产生器中间代码中间代码 一般情况下，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么，由语法分析程序直接调用相应的语义子程序进行语义处理；要么，首先生成语法树或该结构的某种表示，再进行语义处理。1语义处理分两步：语义处理分两步： 1 1、审查每个语法结构的静态语义（静态语义分析、审查每个语法结构的静态语义（静态语义分析/ /静态审查），即验证语法结构合法的程序是否真正有意义。静态审查），即验证语法结构合法的程序是否真正有意义。 2 2、若静态语义正确

2、，语义处理则要执行真正的翻译。、若静态语义正确，语义处理则要执行真正的翻译。即即要么要么生成程序的一种中间表示形式（中间代码），生成程序的一种中间表示形式（中间代码），要么要么生生成实际的目标代码。成实际的目标代码。静态语义检查包括：静态语义检查包括： （1 1）类型检查；）类型检查； （2 2）控制流检查；）控制流检查； （3 3）一致性检查；）一致性检查； （4 4）相关名字检查。）相关名字检查。2中间代码：中间代码：即中间语言，独立于机器的，复杂性介于源即中间语言，独立于机器的，复杂性介于源语言和机器语言之间的一种表示形式。语言和机器语言之间的一种表示形式。采用中间语言的好处：采用中间语

3、言的好处：（1 1）便于进行与机器无关的代码优化工作；）便于进行与机器无关的代码优化工作；（2 2）使编译程序改变目标机更容易；）使编译程序改变目标机更容易；（3 3）使编译程序的结构在逻辑上更为简单明确。）使编译程序的结构在逻辑上更为简单明确。3 7.1 7.1 中间语言中间语言 7.2 7.2 说明语句说明语句 7.3 7.3 赋值语句的翻译赋值语句的翻译 7.4 7.4 布尔表达式的翻译布尔表达式的翻译 7.5 7.5 控制语句的翻译控制语句的翻译 7.6 7.6 过程调用的处理（略）过程调用的处理（略） 7.7 7.7 类型检查类型检查 （略）（略）47. 7.中间语言中间语言中间语言

4、形式：中间语言形式：后缀式三地址代码图表示法三元式三元式 四元式四元式 间接三元式间接三元式DAGDAG抽象语法树抽象语法树5一、后缀式一、后缀式( (逆波兰式逆波兰式) )7. 7.中间语言中间语言规则规则：E E 常量变量常量变量 (2)E (2)E E E1 1 op E op E2 2(3)E (3)E (E(E1 1) ) (4)E (4)E op Eop E1 1例子：例子：a a* *(b+c) (b+c) (a+b)(a+b)* *(c+d)(c+d)x+yza0(8+z)3x+yza0(8+z)3后缀式为：后缀式为：E E本身本身后缀式为：后缀式为：E E1 1 E E2 2

5、 opop后缀式为：后缀式为：E E1 1 后缀式为：后缀式为：E E1 1 opop后缀式为：后缀式为：abc+abc+* *后缀式为：后缀式为：ab+cd+ab+cd+* *后缀式为：后缀式为：xy+za08z+3xy+za08z+36后缀式的特点：后缀式的特点：（1）运算对象出现的顺序与原有顺序呢（从左到右）相同；）运算对象出现的顺序与原有顺序呢（从左到右）相同；（2）运算符按实际运算顺序（从左到右）出现；）运算符按实际运算顺序（从左到右）出现；（3）运算符紧跟在运算对象的后面出现，且没有括号。）运算符紧跟在运算对象的后面出现，且没有括号。产生式语义规则EE1 OP E2E(E1 )Ei

6、dE.code:= E1.code| E2.code|opE.code:= E1.codeE.code:= id属性文法：属性文法：7例： 给出串a*(b+c)的翻译过程：aEEE()EEE+*bc.code=a.code=b.code=c.code=bc+.code=bc+.code=abc+*87. 7.中间语言中间语言二、图表示法二、图表示法1 1、DAG(DAG(无循环有向图无循环有向图) )与抽象语法树对比，其相同点在于，对表达式中与抽象语法树对比，其相同点在于，对表达式中的每个子表达式，它们都有一个结点，一个内部的每个子表达式，它们都有一个结点，一个内部结点代表一个操作符，它的孩子

7、代表操作数；其不结点代表一个操作符，它的孩子代表操作数；其不同点在于，在一个同点在于，在一个DAGDAG中代表公共子表达式的结点中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。达式被表示为重复的子树。1 1、DAGDAG2 2、抽象语法树、抽象语法树97. 7.中间语言中间语言例：例：如图所示，为如图所示，为a+aa+a* *(b-c)+(b-c)(b-c)+(b-c)* *d d的的DAGDAGa+*bc-*d+107. 7.中间语言中间语言2 2、抽象语法树、抽象语法树例：例：(1) a:=b*-c+b

8、*-c的图表示法的图表示法assign a+ * * b uminus b uminus c c语法树语法树assign a+ * b uminus cDAGDAG117. 7.中间语言中间语言(2)a:=b*-c+b*-c的抽象语法树的两种表示法的抽象语法树的两种表示法assignida + *idbuminusidc *uminusidcidbidbIdcuminus1*02idbidcuminus5*46+37idaassign9801234567891011 7. 7.中间语言中间语言三、三地址代码三、三地址代码1 1、三地址代码：、三地址代码：是由下面一般形式的语句构成的序列是由下面

9、一般形式的语句构成的序列x:=y op zx:=y op z 如：如：T T1 1:=y:=y* *z z，T T2 2:=x+T:=x+T1 1 x,y,z x,y,z：名字：名字, ,常数常数, ,编译时产生的临时变量编译时产生的临时变量 opop：运算符号：运算符号( (如定点运算符、浮点运算如定点运算符、浮点运算/ /逻辑运算符等逻辑运算符等) )称为三地址代码的原因：称为三地址代码的原因： 每条语句通常包含三个地址，两个用来表示操作数，每条语句通常包含三个地址，两个用来表示操作数，一个用来存放结果。一个用来存放结果。具体实现：具体实现：用记录表示，其中包含运算符和操作数的域。用记录表

10、示，其中包含运算符和操作数的域。13P170 三地址语句种类14产生式语义规则Sid:=EEE1+ E2 EE1* E2E-E1E(E1)EidS.code:=E.code|gen(id.place:=E.place)E.place:=newtemp;E.code:=E1.code|E2.code| gen(E.place:=E1.place+E2.place)E.place:=newtemp;E.code:=E1.code|E2.code| gen(E.place:=E1.place*E2.place)E.place:=id.place;E.code:=;15例：给出串d:=a*(b+c)的

11、翻译过程：aEEE()EEE+*bc.place=a.code=.place=b.code=.place=c.code=.place=T1.code= T1:=b+c.place=T1.code= T1:=b+c.place=T2.code= T1:=b+c T2:=a*T1Sd:=S.code= T1:=b+c T2:=a*T1 d:=T2162、三地址代码的三种实现方式：（1）四元式（2）三元式（3）间接三元式7. 7.中间语言中间语言177. 7.中间语言中间语言（1 1）四元式：）四元式：带有四个域的记录结构带有四个域的记录结构 (op(op，arg1arg1，arg2arg2，res

12、ult)result)内容均是指针，指向有关名字的符号表入口内容均是指针，指向有关名字的符号表入口T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5oparg1arg2result(0)(1)(2)(3)(4)(5)uminus c T1 * b T1 T2uminus c T3 * b T3 T4 + T2 T4 T5 := T5 a7. 7.中间语言中间语言（2 2）三元式：）三元式：为了避免把临时变量填入符号表，可通过为了避免把临时变量填入符号表，可通过 计算该临时变量值的语句的位置来引用该临计算该临时变量值的语句的位置来引用该临 时变量。时变量。（op

13、op，arg1arg1，arg2arg2）或是指向符号表的指针或是指向符号表的指针对程序中的名字或常量而言对程序中的名字或常量而言或是指向三元式表的指针或是指向三元式表的指针对临时变量而言对临时变量而言19T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5Oparg1arg2(0)(1)(2)(3)(4)(5)uminus c * b （0）uminus c * b （2） + （1） （3） := a （4） 207. 7.中间语言中间语言（3 3）间接三元式：）间接三元式：便于代码优化处理便于代码优化处理方法：间接码表方法：间接码表 + + 三元式表三元式

14、表按运算的先后顺序列出有关三元式在三元表中的位置按运算的先后顺序列出有关三元式在三元表中的位置oparg1arg2例例, ,语句语句X:=(A+B)X:=(A+B)* *C C；Y:=D(A+B)Y:=D(A+B)的间接三元式表示如下所示的间接三元式表示如下所示: :间接码表表三元式表(1)(2)(3)(1)(4)(5)(1) + A B(2) * (1) C(3) := X (2)(4) D (1)(5) := Y (4)217. 7.中间语言中间语言(4)(4)比较三元式、四元式、间接三元式比较三元式、四元式、间接三元式227.2 7.2 说明语句说明语句编译过程中，对编译过程中，对“说明

15、语句说明语句”要做的工作要做的工作: :对一个过程或分程序的一系列说明语句考察时，对一个过程或分程序的一系列说明语句考察时，需要为局部于该过程的名字分配存储空间；对每个需要为局部于该过程的名字分配存储空间；对每个局部名字，都需在符号表中建立相应的表项，并填局部名字，都需在符号表中建立相应的表项，并填入有关的信息如类型、在存储器中的相对地址等。入有关的信息如类型、在存储器中的相对地址等。 237.2 7.2 说明语句说明语句一、过程中的说明语句一、过程中的说明语句1 1、产生、产生“说明语句说明语句”的文法：的文法：P PMDMDMM offset:=0offset:=0D DD;DD;DD D

16、id:Tid:Tenter(,T.type,offset);enter(,T.type,offset);offset:=offset+T.widthoffset:=offset+T.widthT TintegerintegerT.type:=integer; T.width:=4T.type:=integer; T.width:=4T TrealrealT.type:=real; T.width:=8T.type:=real; T.width:=8T Tarraynum of Tarraynum of T1 1T.type:=array(num.val,TT.typ

17、e:=array(num.val,T1 1.type);.type); T.width:=num.val T.width:=num.valT T1 1.width.widthT TTT1 1T.type:=pointer(TT.type:=pointer(T1 1.type); T.width:=4.type); T.width:=4247.2 7.2 说明语句说明语句说明说明: :(1)Offset(1)Offset：全程变量，代表变量在过程数据区中的相对地全程变量，代表变量在过程数据区中的相对地 址，用来跟踪下一个可用的相对地址的位置。址，用来跟踪下一个可用的相对地址的位置。(2)ente

18、r(name,type,offset)(2)enter(name,type,offset)：把名字把名字namename符号表，并给符号表，并给 出此名字的类型出此名字的类型typetype及在过程数据区中的相对地及在过程数据区中的相对地 址址offsetoffset。(3)(3)综合属性：综合属性：T.typeT.type名字的类型；名字的类型； T.width T.width名字的域宽名字的域宽( (即该类型名字所占即该类型名字所占 用的存储单元个数用的存储单元个数) )。25例：给出下面串的翻译过程： a: integer; b:array10 of realPDDD;T:aintege

19、rT:bTarray10 ofTreal.type=integer.width=4Moffset= 0name type offset符号表符号表 a integer 0 4.type=real.width=8.type=pointer(real).width=4.type=array(10,pointer(real).width=40 b array(10,pointer(real) 4 4426练习：给出下面串的翻译结果 a:real; b:integer; c:array 3 of integer; d:integername typeoffset符号表符号表 a real 0 b po

20、inter(integer) 8 c array(3, integer) 12 d integer 24 277.2 7.2 说明语句说明语句2 2、处理方式：、处理方式：处理第一条说明语句之前，先置处理第一条说明语句之前，先置offsetoffset为为0 0，以后，以后每次遇到一个新的名字，便将该每次遇到一个新的名字，便将该名字、类型、相对地址名字、类型、相对地址填入符号表中并置相对地址为当前填入符号表中并置相对地址为当前offset offset 之值，然后使之值，然后使offset offset 加上该名字所表示的数据对象的域宽。加上该名字所表示的数据对象的域宽。28P PMDMDMM

21、 D DD;DD;DD Did:Tid:TT TintegerintegerT TrealrealT Tarraynum of Tarraynum of T1 1T TTT1 1297.2 7.2 说明语句说明语句二、保留作用域信息二、保留作用域信息1 1、嵌套过程中的说明语句、嵌套过程中的说明语句(1)(1)相应的文法相应的文法: P: PD D D DD;D|id;T|proc id;D;SD;D|id;T|proc id;D;S(2)(2)程序举例程序举例: : 307.2 7.2 说明语句说明语句2 2、含嵌套说明的翻译模式：、含嵌套说明的翻译模式： P PMMD D317.2 7.2

22、 说明语句说明语句 (1)语义规则中的操作：mktable(previous)mktable(previous)：创建一张新符号表，并返回指向新表的一个指针；enter(table,name,type,offset)enter(table,name,type,offset)：在指针table指示的符号表中为名字name建立一个新顶，并把类型type、 相对地址offset填入到该项中；addwidth(table,width)addwidth(table,width)：在指针table指示的符号表表头中记录下该表中所有名字占用的总宽度；enterproc(table,name,newtable

23、)enterproc(table,name,newtable)：在指针table指示的符号表中为名字name的过程建立一个新项。参数 newtable指向过程name的符号表。327.2 7.2 说明语句说明语句(2)栈 tblptrtblptr：存放指向符号表的指针，栈顶为指向当前正在处理过程的符号表指针； offsetoffset：存放变量在数据区中的相对地址，栈顶为当前正在处理过程的下一个变量的相对地址。(3) top(top() )：取当前栈顶元素； push(a,B)push(a,B)：将a推进B栈栈顶； pop(A)pop(A)：将A栈栈顶元素出栈。33PDDD;T:aintege

24、rMDD;DD;；AprocSDNDD;34sort a array(11,integer) 0 x integer 44 nil tblptr offset sort 0 44 48 readarraysort readarray 0 i integer 0 4 4 exchangesort 0 readarray exchange 0 exchange quicksortpartition k int 0 v int 4 partion i int 0 j int 4quicksort quicksort 0 4 8 8 partition 0 4 8 8 487.3 7.3 赋值语句的翻

25、译赋值语句的翻译一、简单算术表达式及赋值语句一、简单算术表达式及赋值语句1 1、产生、产生“赋值语句赋值语句”三地址代码的翻译模式三地址代码的翻译模式: :S Sid:=Eid:=Ep:=lookup();p:=lookup();if pnil then emit(p:=E.place) else errorif pnil then emit(p:=E.place) else errorE EE E1 1+E+E2 2E.place:=newtemp;E.place:=newtemp;emit(E.place:= Eemit(E.place:= E1 1.place

26、+ E.place+ E2 2.place).place)E EE E1 1* *E E2 2 E.place:=newtemp;E.place:=newtemp; emit(E.place:= E emit(E.place:= E1 1.place.place* * E E2 2.place).place)E E-E-E1 1 E.place:=newtemp;E.place:=newtemp;emit(E.place:= uminus Eemit(E.place:= uminus E1 1.place).place)E E(E(E1 1) ) E.place:=EE.place:=E1 1

27、.place.placeE Eid idp:=lookup();p:=lookup();if pnil then if pnil then E.place:=p else errorE.place:=p else error367.3 7.3 赋值语句的翻译赋值语句的翻译 2 2、说明、说明: :idid所代表的名字本身所代表的名字本身lookup()lookup()检查符号表中是否存在相应此检查符号表中是否存在相应此名字的入口名字的入口 nil：返回一个该表项的指针：返回一个该表项的指针 = nil：未找到：

28、未找到emit(emit() )将生成的三地址语句发送到输出文件中将生成的三地址语句发送到输出文件中E.placeE.place存放存放E E值的名字值的名字newtempnewtemp产生产生“临时变量临时变量”37例：给出d:=a*(b+c)的翻译结果输出的四元式： (+,b,c,T1) (*,a,T1,T2) (:=,T2, ,d)aEEE()EEE+*bc.place=a.place=b.place=c.place=T1.place=T2Sd:=.place=T138状态状态已归约串已归约串PLACEPLACE输入串输入串语义动作语义动作# #X:=-BX:=-B* *(C+D)#(C

29、+D)#X#XX X:=-B:=-B* *(C+D)# (C+D)# # X:=# X:=X_X_-B-B* *(C+D)#(C+D)# X:=-# X:=-X_X_B B* *(C+D)#(C+D)# X:=-B# X:=-BX_BX_B * *(C+D)#(C+D)# X:=-E# X:=-EX_BX_B * *(C+D)#(C+D)#E.place:=p=E.place:=p=# X:=E# X:=EX_TX_T1 1* *(C+D)#(C+D)#E.place:=newtemp=TE.place:=newtemp=T1 1生成四元式生成四元式(1)(1)# X:=E# X:=E* *(

30、C(CX_TX_T1 1_C_C+D)#+D)# X:=E# X:=E* *(E1(E1X_TX_T1 1_C_C+D)#+D)#EE1 1.place:=p=.place:=p=# X:=E# X:=E* *(E1+D(E1+D X_TX_T1 1_C_D_C_D)#)# X:=E# X:=E* *(E1+E2(E1+E2 X_TX_T1 1_C_D_C_D)#)#EE2 2.place:=p=.place:=p=# X:=E# X:=E* *(E(EX_TX_T1 1_T_T2 2)#)#EE1 1.place:=newtemp=T.place:=newtemp=T2 2; ;生成四元式生

31、成四元式(2)(2)# X:=E# X:=E* *(E)(E)X_TX_T1 1_T_T2 2_ _# # X:=E# X:=E* *EEX_TX_T1 1_T_T2 2# # E.place=E.place=T E.place=E.place=T2 2 # X:=E# X:=EX_TX_T3 3# #E.place=TE.place=T3 3; ;生成四元式生成四元式(3)(3)# S# S # p:=lookup(X.name) # p:=lookup(X.name)生成四元式生成四元式(4)(4)7.3 7.3 赋值语句的翻译赋值语句的翻译3 3、例题：、例题：写出下列代码段中表达式的翻

32、译制导过写出下列代码段中表达式的翻译制导过 程及其所产生的四元式程及其所产生的四元式beginbeginB B、C C、D D、X X ：Integer;Integer;X:=-BX:=-B* *(C+D);(C+D);endendOparg1arg2result(1)(2)(3)(4)+*:=T1 1T3 3T2 2T1 1T2 2T3 3nametypeoffset04812四元式四元式 符号表符号表407.3 7.3 赋值语句的翻译赋值语句的翻译二、数组元素的引用二、数组元素的引用1 1、数组元素在存储器中的存放：、数组元素在存储器中的存放：( (行序为主序）行序为主序）一维：一维：Ai

33、 Ai base+(i-low) base+(i-low)* *ww= = (base-low(base-low* *w) w) +i+i* *ww二维：二维：Ai1,i2Ai1,i2 base+(i1-low1) base+(i1-low1)* *n2+(i2-low2)n2+(i2-low2)* *w=w= base-(low1base-(low1* *n2+low2)n2+low2)* *w w +(i1+(i1* *n2+i2)n2+i2)* *wwk k维：维：AiAi1 1,i ,i2 2, ,i ,ik k 41三维三维:Ai1,i2, i3:Ai1,i2, i3base+(i1

34、-low1)base+(i1-low1)* *n2n2* *n3+(i2-n3+(i2-low2)low2)* *n3+(i3-low3)n3+(i3-low3)* *w=w= base-base-(low1(low1* *n2+low2)n2+low2)* *n3+low3)n3+low3)* *w w +(i1+(i1* *n2+i2)n2+i2)* *n3+i3)n3+i3)* *wwA1,1,1A1,1,2A1,2,1A1,2,2A1,3,1A1,3,2A2,1,1A2,1,2A2,2,1A2,2,2A2,3,1A2,3,2i=1i=2j=1j=2j=3j=1j=2j=342k维：维：

35、Ai1,i2,ikbase-(low1*n2+low2)*n3+low3)*nk+lowk)*w +(i1*n2+i2)*n3+i3).)*nk+ik)*wCe1=i1e e2 2=e=e1 1* *n n2 2+i+i2 2e e3 3=e=e2 2* *n n3 3+i+i3 3. . . .e em m=e=em-1m-1* *n nm m+i+im m437.3 7.3 赋值语句的翻译赋值语句的翻译改写产生式的原因：改写产生式的原因： 使我们在整个下标表达式串使我们在整个下标表达式串ElistElist的翻译过程的翻译过程中随时都能知道符号表中相应于数组名字中随时都能知道符号表中相应于

36、数组名字idid的符的符号表入口，从而随时能了解登记在符号表中的有关号表入口，从而随时能了解登记在符号表中的有关数组数组idid的全部信息。的全部信息。 2 2、产生数组元素的产生式：、产生数组元素的产生式：L LidElist|ididElist|idL LElist|idElist|idElistElistElist,E|EElist,E|EElistElistElist,E|idEElist,E|idE44 3 3、数组元素的翻译模式：、数组元素的翻译模式：A A、文法、文法: (1)S: (1)SL:=EL:=E (5)L (5)LElistElist (2)E (2)EE+EE+E

37、(6)L (6)Lidid (3)E (3)E(E)(E) (7)Elist (7)ElistElist,EElist,E (4)E (4)EL L (8)Elist (8)ElistidEidE7.3 7.3 赋值语句的翻译赋值语句的翻译457.3 7.3 赋值语句的翻译赋值语句的翻译B B、说明、说明: : id.placeid.placeid id的符号表入口的符号表入口 E.placeE.place存放存放E E的名字的名字/ /值值 L.offsetL.offset L L仅为简单名字，则为仅为简单名字，则为nullnull null null，则，则L L为数组元素引用，存放临时变

38、量的为数组元素引用，存放临时变量的值值( (常量部分的值常量部分的值) ) L.place L.placeL L简单名字，则指向符号表中相应此名字表简单名字，则指向符号表中相应此名字表项的指针，即此名字的符号表入口项的指针，即此名字的符号表入口 L L数组引用，则数组引用，则L.placeL.place存放临时变量的值存放临时变量的值( (常常量部分的值量部分的值) ) Elist.array Elist.array用来记录指向符号表中相应数组名字表项用来记录指向符号表中相应数组名字表项的指针的指针数组变量的入口数组变量的入口 Elist.placeElist.place表示临时变量，用来临时

39、存放由表示临时变量，用来临时存放由ElistElist中的下中的下标表达式计算出的值标表达式计算出的值 Elist.ndimElist.ndim记录记录ElistElist中的下标表达式的个数中的下标表达式的个数, ,即维数即维数 Limit(array,j)Limit(array,j)返回返回nj nj，即由，即由arrayarray所指示的数组的第所指示的数组的第j j维长度维长度7.3 7.3 赋值语句的翻译赋值语句的翻译4 4、举例、举例已知：A为1020的数组，即n1=10，n2=20，设w=4，x:=Ay,zx:=Ay,z其相应的三地址语句序列如下:(1)T1:=y*20(2)T1

40、:=T1+z(3)T2:=A-84(4)T3:=4*T1(5)T4:=T2T3(6)x:=T447ElistE.place=x.offset=nullSx:=LELElistAELyLz.place=y.offset=null.place=y.place=y.ndim=1.array=A .place=z.offset=null.place=z.array=A.place=T1.ndim=2t=T1m=2输出的四元式：T1:=y*20T1:=T1+zT2:=A-84T3:=4*T1T4:=T2T3x:=T4.place=T2.offset=T3.place=T448，7.3 7.3 赋值语句的

41、翻译赋值语句的翻译练习：练习： 假设有赋值语句假设有赋值语句Ax,y:=Bx,y,z+t。其中：。其中：A是是10*20的数组，的数组，B是是10*20*30的数组，数组下界都是的数组，数组下界都是0。请给出该。请给出该数组的翻译结果。数组的翻译结果。输出的四元式：T1:=x*20T1:=T1+yT2:=AT3:=4*T1T4:=x*20T4:=T4+y T5:=T4*30 T5:=T5+z T6:=B T7:=4*T5 T8:=T6T7 T9:=T8+t T2T3:=T9497.4 7.4 布尔表达式的翻译布尔表达式的翻译前言前言: : 1 1、布尔表达式的两个基本作用、布尔表达式的两个基本

42、作用(1)(1)用来计算逻辑值用来计算逻辑值(2)(2)用作控制流语句的条件表达式用作控制流语句的条件表达式 2 2、布尔表达式的组成及形式、布尔表达式的组成及形式组成：布尔运算符号、布尔变量、关系表达式组成：布尔运算符号、布尔变量、关系表达式形式：形式：and,or,notand,or,not E E1 relop E relop E2(, (, )507.4 7.4 布尔表达式的翻译布尔表达式的翻译3 3、产生布尔表达式的文法、产生布尔表达式的文法: :E EE or EE or EE EE and EE and EE Enot Enot EE E(E)(E)E Eid relop idi

43、d relop idE Eid id517.4 7.4 布尔表达式的翻译布尔表达式的翻译一、数值表示法一、数值表示法1 1、计算布尔表达式值的两种方法：、计算布尔表达式值的两种方法：(1)(1)逐步计算逐步计算( (与算术表达式计算类似与算术表达式计算类似) ) 例：例： 1 or (not 0 and 0) or 01 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 or 0 =1 or 0 =1 or 0 =1 =1(2)(2)采取某种优化措施采取某种优化措施 A or

44、 BA or Bif A then True else Bif A then True else B A and B A and Bif A then B else Falseif A then B else False not A not Aif A then False else Trueif A then False else True527.4 7.4 布尔表达式的翻译布尔表达式的翻译 2 2、采取、采取“逐步计算法逐步计算法”计算布尔表达式计算布尔表达式分析：分析：(1)(1)布尔式布尔式a or b and not ca or b and not c T T1 1:=not c:=

45、not c T T2 2:=b and T:=b and T1 1 T T3 3:=a or T:=a or T2 2 (2) (2)关系式关系式 a b a b if ab then 1 else 0 if ab then 1 else 0 100: if ab goto 103 100: if ab goto 103 101: T:=0 101: T:=0 102: goto 104 102: goto 104 103: T:=1 103: T:=1 104: 104: 537.4 7.4 布尔表达式的翻译布尔表达式的翻译 3 3、布尔表达式、布尔表达式“逐步计算法逐步计算法”的翻译模式：

46、的翻译模式：Emit(Emit() )：过程，将产生的三地址代码送到输出过程，将产生的三地址代码送到输出 文件中文件中NextstatNextstat：给出输出序列中下一条三地址语句的地给出输出序列中下一条三地址语句的地 址索引，每产生一条三地址语句后，过址索引，每产生一条三地址语句后，过 程程emitemit将将nextstatnextstat加加1 154关于布尔表达式的数值表示法的翻译模式关于布尔表达式的数值表示法的翻译模式:EE1 or E2E.place:=newtemp; emit(E.place := E1.place or E2.place)EE1 and E2E.place:

47、=newtemp; emit(E.place := E1.place and E2.place)Enot E1E.place:=newtemp; emit(E.place := not E1.place)E(E)E.place:=E1.placeEid1 relop id2E.place:=newtemp; emit( if id1.place relop.op id2.place goto nextstat+3); emit(E.place := 0); emit(goto nextstat+2); emit(E.place := 1);EidE.place:=id.place7.4 7.4

48、 布尔表达式的翻译布尔表达式的翻译4 4、举例：、举例：ab or cd and efab or cd and ef 100: if ab goto 103 101: T1:=0 102: goto 104 103: T1:=1 104: if cd goto 107 105: T2:=0 106: goto 108 107: T2:=1 108: if ef goto 111 109: T3:=0 110: goto 112 111: T3:=1 112: T4:=T2 and T3 113: T5:=T1 or T4567.4 7.4 布尔表达式的翻译布尔表达式的翻译二、作为条件控制的布尔

49、式的翻译二、作为条件控制的布尔式的翻译1 1、以布尔式为条件控制的语句、以布尔式为条件控制的语句 S Sif E then Sif E then S1 1| |if E then Sif E then S1 1 else S else S2 2| |while E do Swhile E do S1 1相应的代码结构相应的代码结构:E E的代码的代码S S1 1的代码的代码E.TrueE.True E.falseE.falseGoto S.nextGoto S.nextS S2 2的代码的代码E E的代码的代码S S1 1的代码的代码E.TrueE.True E.falseE.falseS.n

50、extS.next beginbeginGoto beginGoto beginE E的代码的代码S S1 1的代码的代码E.TrueE.True E.false E.false 577.4 布尔表达式的翻译注注: :这里的布尔式作用仅在于控制对这里的布尔式作用仅在于控制对S S1 1和和S S2 2的选的选 择，无须将择，无须将E E的值最终保留某个临时单元之中。的值最终保留某个临时单元之中。设置两种出口：真出口设置两种出口：真出口E.trueE.true，假出口，假出口E.falseE.false587.4 7.4 布尔表达式的翻译布尔表达式的翻译 2 2、初步分析、初步分析EEEE1 1

51、 or E or E2 2 E E1 1.true .true E.trueE.true E E2 2.true .true E.trueE.true E E2 2.false.false E.falseE.falseEEEE1 1 and E and E2 2 E E1 1.false .false E.falseE.false E E2 2.true .true E.trueE.true E E2 2.false.false E.falseE.false597.4 7.4 布尔表达式的翻译布尔表达式的翻译 3 3、翻译模式、翻译模式说明说明: : (1)E.truelist / E.fal

52、selist (1)E.truelist / E.falselist(2)(2)四元式四元式(jnz,a,(jnz,a,p) if a goto p,p) if a goto p (jrop,x,y,p) if x rop y goto p (jrop,x,y,p) if x rop y goto p (j, (j, ,p),p) goto p goto p(3)(3)链链: :607.4 7.4 布尔表达式的翻译布尔表达式的翻译变量和过程变量和过程:变量变量nextquadnextquad指向下一条将要产生但尚未形成的四元式指向下一条将要产生但尚未形成的四元式的地址，初值为的地址，初值为1

53、1，执行一次，执行一次emitemit后自动加后自动加1 1函数函数makelist(i)makelist(i)函数函数merge(pmerge(p1 1,p ,p2 2) )把链首为把链首为p p1 1和和p p2 2的两条链合并为一，作的两条链合并为一，作为函数值为函数值, ,回送合并后的链首回送合并后的链首过程过程backpatch(p,t)backpatch(p,t)功能是完成功能是完成“回填回填”，把，把p p所链接的所链接的每个四元式的第四个区段都填为每个四元式的第四个区段都填为t t61EE1 or M E2EE1 or M E2 backpatch(E1.falselist,

54、M.quad) backpatch(E1.falselist, M.quad)E.truelist:=merge(E1.truelist,E2.truelsit)E.truelist:=merge(E1.truelist,E2.truelsit)E.falselist:=E2.falselist E.falselist:=E2.falselist EE1 and M E2EE1 and M E2 backpatch(E1.truelist, M.quad) backpatch(E1.truelist, M.quad)E.truelist:=E2.truelsitE.truelist:=E2.t

55、ruelsitE.falselist:=merge(E1.falselist,E2.falselist )E.falselist:=merge(E1.falselist,E2.falselist )62Enot E1Enot E1E(E1)E(E1)MME.truelist:=E1.falselistE.truelist:=E1.falselistE.falselist:=E1.truelistE.falselist:=E1.truelist E.truelist:=E1.truelist E.truelist:=E1.truelist E.falselist:=E1.falselist E.

56、falselist:=E1.falselist M.quad:=nextquad M.quad:=nextquad63Eid1 relop id2Eid1 relop id2EidEid E.truelist:=makelist(nextquad); E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); E.falselist:=makelist(nextquad+1);emit(emit(j j relop.op relop.op , , id1.place id1.place , , id2.place id2

57、.place , , 0 0) ) emit( emit(j, -, -, 0j, -, -, 0) ) E.truelist:=makelist(nextquad); E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); E.falselist:=makelist(nextquad+1); emit( emit(jnzjnz , , id.place id.place , , - - , , 0 0); ); emit( emit(j, -, -, 0j, -, -, 0) ) 647.4 7.4 布尔表达式的翻

58、译布尔表达式的翻译5、例题：、例题：ab or cd and efM.tl=100.fl=101EEorEMEandEba dcfe100 (j,a,b,0）101 (j, - , -, 0 )102 (j,c,d, 0 ）103 (j, - , -, 0).quad=102.tl=102.fl=103.quad=104.tl=104.fl=105104 (jb)and(cd)or(eb)and(cd)or(ef)667.57.5控制语句的翻译控制语句的翻译 一、控制流语句一、控制流语句 S Sif E then Sif E then S1 1|if E then S|if E then S1

59、 1 else S else S2 2|while E do S|while E do S1 1677.5 7.5 控制语句的翻译控制语句的翻译 E.true:E.false:E.codeS1.codeSif E then S1E.true:=newlableE.false:=S.nextS1.next:=S.nextS.code:=E.code|gen(E.true:) |S1.code687.5 7.5 控制语句的翻译控制语句的翻译Sif E then S1 else S2E.true:=newlableE.false:=newlableS1.next:=S.nextS2.next:=S.nextS.code:=E.code| gen(E.true:) |S1.code|gen(goto S.next)|gen(E.false:)|S2.codeE.codeS1.codegoto S.nextS2.codeE.true:E.false:S.n