第六章中间代码江西师范大学

1、.第六章第六章 中间代码中间代码l中间代码的形式中间代码的形式l表达式的翻译表达式的翻译l简单赋值语句的翻译简单赋值语句的翻译l布尔表达式的翻译布尔表达式的翻译l控制语句的翻译控制语句的翻译. 何谓中间代码何谓中间代码： 语法制导翻译。语法制导翻译。.优点优点 形式简单、语义明确、便于翻译形式简单、语义明确、便于翻译 独立于目标语言独立于目标语言 要掌握几种常见的中间语言的基本结构：要掌握几种常见的中间语言的基本结构：图表示法：抽象语法树图表示法：抽象语法树逆波兰表示法逆波兰表示法( (也称后缀式也称后缀式) )三地址代码三地址代码四元式四元式三元式、间接三元式三元式、间接三元式几种常见的中间

2、语言几种常见的中间语言4图表示法：抽象语法树图表示法：抽象语法树 语法制导翻译以语法树作基础语法制导翻译以语法树作基础, 实际上实际上, 语法树可以作语法树可以作为一种合适的中间语言形式。为一种合适的中间语言形式。 现在对语法树进行改造，去掉那些对翻译不必要的信现在对语法树进行改造，去掉那些对翻译不必要的信息，将语法树进行抽象息，将语法树进行抽象 - 抽象语法树抽象语法树。 在抽象语法树中，每个叶结点都表示诸如常量或变量在抽象语法树中，每个叶结点都表示诸如常量或变量这样的运算对象，而其它内部结点则表示运算符。这样的运算对象，而其它内部结点则表示运算符。 语法制导翻译既可以基于语法分析树也可以基

3、于抽象语法制导翻译既可以基于语法分析树也可以基于抽象语法树进行，语法树进行，采用的基本方法是一样的。采用的基本方法是一样的。5 为下面文法的句子为下面文法的句子 x = a-4x = a-4* *c c 建立抽象语法树：建立抽象语法树： SV=E Vid E E+E | E-E | E*E | (E) | id | num 为每个运算量或运算符号都建立一个结点。为每个运算量或运算符号都建立一个结点。 可以可以根据表达式的运算顺序自下而上的构造根据表达式的运算顺序自下而上的构造 - 手工手工构造。构造。抽象语法树抽象语法树运算符作内运算符作内部结点部结点语法树语法树 比较：抽象语法树的特点是结构

4、比较：抽象语法树的特点是结构紧凑，容易构造，结点较少。紧凑，容易构造，结点较少。c*4a-xassign 表示赋值表示赋值id(c)E E * EE - Enum(4)id(a )S V = id(x )6l构造赋值语句：构造赋值语句： x=ab*(c-d)-e/f 的抽象语法树，根据表达的抽象语法树，根据表达式的运算顺序自下而上的式的运算顺序自下而上的构造。构造。l可以设计属性文法构造抽可以设计属性文法构造抽象语法树。象语法树。 手工构造抽象语法树手工构造抽象语法树 -a+xassign *b -cd/ef.逆波兰表示法 逆波兰表示法逆波兰表示法又称又称后缀式后缀式表示法。逆波兰表表示法。逆

5、波兰表示法是波兰逻辑学家卢卡西维奇发明的一种示法是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法表示表达式的方法。这种方法是，把运算量。这种方法是，把运算量( (操作数操作数) )写在运算符的前面，把运算符写在写在运算符的前面，把运算符写在运算量的后面运算量的后面( (后缀后缀) )。 例：a+b ab+ a*(b+c) abc+* (a+b)*(c+d) ab+cd+*. 表达式的逆波兰表示表达式的逆波兰表示 一个一个表达式的后缀式表达式的后缀式可以如下递归定义：可以如下递归定义：1. 如果如果E是一个变量或常量，则是一个变量或常量，则E的后缀式是的后缀式是E自身。自身。2. 如果如果E是

6、是 E1 op E2 形式的表达式，这里形式的表达式，这里op是是任何二元操作符，则任何二元操作符，则E的后缀式为的后缀式为 E1 E2 op,这里这里E1 和和E2分别为分别为E1和和E2的后缀式。的后缀式。3. 如果如果E是是(E1)形式的表达式，则形式的表达式，则E1的后缀式的后缀式就是就是E的后缀式。的后缀式。. 后缀式与抽象语法树的关系 后缀式是抽象语后缀式是抽象语法树的线性表示法树的线性表示形式。形式。是树的后是树的后序遍历序遍历(左，右，左，右，根根)的一个序列。的一个序列。 例如例如: a = b * - c+b * -c的抽象语法树。的抽象语法树。assigna+*bc-*-

7、cb后缀式后缀式: : a b c - * b c - * + assign.无环有向图（无环有向图（DAG） DAG指出了表达式中公共子表达式。指出了表达式中公共子表达式。 结点结点N（一个公共子表达式），可能有多个（一个公共子表达式），可能有多个父结点。父结点。.a+a*(b-c)+(b-c)*d+ba-*+dc.DAG的值编码方法的值编码方法=10i+idnum10+12=13到到i对应对应 的条目的条目12345.=a+*bc-给出给出a = b * - c+b * -c的的DAG及其值编码。及其值编码。.三地址代码三地址代码 三地址代码是由下面一般形式的语句构成的三地址代码是由下面一

8、般形式的语句构成的序列序列: x = y op z 其中，其中，x、y、z为名字、常数或编译时产生为名字、常数或编译时产生的临时变量；的临时变量；op代表运算符号。代表运算符号。 每个三地址语句的右边只能有一个运算符。每个三地址语句的右边只能有一个运算符。 例例, 表达式表达式 x+y*z 翻译为三地址代码翻译为三地址代码: t1 = y*z t2 = x+t1 t1, t2是编译时产生的临时变量。是编译时产生的临时变量。.三地址代码：说明三地址代码：说明 1. 之所以称为三地址代码，是因为三地址代码之所以称为三地址代码，是因为三地址代码语句类似与汇编指令语句类似与汇编指令, 涉及三个地址涉及

9、三个地址 x、y和和z，其中其中y、z表示操作数，表示操作数，x存放结果。存放结果。地址常用地址常用属性属性place(addr)表示。表示。 名字名字.place：指向符号表名字入口的指针：指向符号表名字入口的指针 临时变量临时变量.place：临时变量值存放的单元地址：临时变量值存放的单元地址 常数常数.place：指向常数表中常数入口的指针：指向常数表中常数入口的指针 2.在三地址代码中，一条指令的右侧最多有一在三地址代码中，一条指令的右侧最多有一个运算符。个运算符。 3. 三地址代码是抽象语法树的线性化表示三地址代码是抽象语法树的线性化表示 - 树的每个内部结点对应一个三地址语句。树的

10、每个内部结点对应一个三地址语句。. 按树自下而上的顺序写出每个内部结点对应的三按树自下而上的顺序写出每个内部结点对应的三地址代码。地址代码。 注：注： 临时变量的名字对应抽象语法树的内部结点临时变量的名字对应抽象语法树的内部结点(算符结点算符结点), 表达式中的每个运算都要引入一个新表达式中的每个运算都要引入一个新的临时变量存放计算结果的临时变量存放计算结果, 要多少引入多少。要多少引入多少。+ba-*+dcT1=b-cT2=a*T1T3=a+T2T4=T1*dT5=T3+T4. 画出赋值语句画出赋值语句 x=a-b*c 的抽象语法树的抽象语法树 。给。给出其三地址表示。出其三地址表示。=x-

11、a*bc T1 b* c T2 a-T1 x T2 .n(1) 赋值语句赋值语句 x y op z ; op是二元算术或逻辑运算符是二元算术或逻辑运算符n(2) 赋值语句赋值语句 x op y ; op是一元算符，如取负运算符是一元算符，如取负运算符minus、逻辑非运算符、逻辑非运算符not、移位运算符及类型转换运算符。、移位运算符及类型转换运算符。n(3) 复制语句复制语句 x y;n(4) 无条件转移语句无条件转移语句 goto L; L是语句标号。是语句标号。 n(5) 条件转移语句条件转移语句 if x goto L ; if False x goto L ; X为真或为假时转移到为

12、真或为假时转移到L三地址语句的种类三地址语句的种类.n（6）条件转移语句条件转移语句 if x relop y goto L，关系运算，关系运算符号符号relop( ，=，= 等等）等等）;n(7) 过程调用语句过程调用语句 param x1; xi 是实参数是实参数 param x2; param xn; call p, n ; p过程名过程名, n实参个数实参个数 y=call p,n； p 函数名函数名 返回语句返回语句 return y; y返回值返回值, 可有可无可有可无三地址语句的种类三地址语句的种类. (8) 变址赋值语句变址赋值语句 x = yi; = 变址取数变址取数 xi

13、= y ; = 变址存数变址存数 (9) 地址和指针赋值语句地址和指针赋值语句 x y; x * y; * x y;. 四元式四元式 ( op, arg1, arg2, result ) 用了四个域用了四个域 三元式三元式 ( op, arg1, arg2 ) 只用三个域只用三个域 间接三元式间接三元式 间接码表间接码表+三元式表，三元式表， 便于进行优化便于进行优化三地址代码的具体实现三地址代码的具体实现算符算符 操作数操作数1(指针指针)操作数操作数2(指针指针)结果结果(临变临变)n三地址代码的具体实现三地址代码的具体实现: 用记录结构用记录结构, 含四个域含四个域 . 四元式需要较多的

14、临时单元。四元式之间四元式需要较多的临时单元。四元式之间 的联系通过临时变量实现的联系通过临时变量实现, 三元式之间的联三元式之间的联系通过指针实现。系通过指针实现。 中间代码优化处理时，四元式比三元式方中间代码优化处理时，四元式比三元式方便得多便得多, 间接三元式与四元式同样方便，四间接三元式与四元式同样方便，四元式和三元式两种实现方式需要的存储空元式和三元式两种实现方式需要的存储空间大体相同。间大体相同。. 三地址语句三地址语句 四元式表示四元式表示 x = y op z ( op, y, z, x ) x = -y ( minus, y, _ , x ) x = y ( =, y, _,

15、 x ) par x1 ( param, x1, _, _ ) call P (call, _, _, P ) goto L ( j, _, _, L ) 无条件转移无条件转移 if a goto L ( jnz, a, _, L ) 条件转移条件转移 a是逻辑量，是逻辑量，a非非0, 即即a为真时转移为真时转移 if x rop y goto L ( jrop, x, y, L ) 条件转移条件转移 rop是关系运算符是关系运算符, x和和y为算术量，为算术量，x rop y 为真时转移为真时转移常用的三地址语句对应的四元式常用的三地址语句对应的四元式.n例：赋值语句例：赋值语句a=ba=b

16、* *-c+b-c+b* *-c -c 的四元式：的四元式：(0)(1)(2)(3)(4)(5)minus*minus*+Assign(=)cbcbT2T5arg1T1T3T4arg2resultT1T2T3T4T5aop三地址代码实现：四元式表示三地址代码实现：四元式表示n注：注：四元式出现的顺序与表达式计值的顺序四元式出现的顺序与表达式计值的顺序一致；四元式之间的联系通过临时变量实现。一致；四元式之间的联系通过临时变量实现。.(0)(1)(2)(3)(4)(5)minus*minus*+assigncbcb(1)aarg1(0)(2)(3)(4)arg2opn例：赋值语句例：赋值语句a=b

17、a=b* *-c+b-c+b* *-c -c 的三元式：的三元式：.n注：注：三元式中使用了指向三元式语句的指针三元式中使用了指向三元式语句的指针( (序号序号) )，序号也表示该三元式计算的结果值；，序号也表示该三元式计算的结果值； 三元式之间的联系通过指针实现。三元式之间的联系通过指针实现。三地址代码实现：三元式表示三地址代码实现：三元式表示.n例：赋值语句例：赋值语句a=ba=b* *-c+b-c+b* *-c -c的的间接三元式间接三元式：(0)(1)(2)(3)minus*+assigncb(1)aarg1(0)(1)(2)arg2op三元式表三元式表(0)(1)(0)(1)(2)(

18、3)间接码表间接码表n间接码表按运算的次序列出三元式序号，三元式表只间接码表按运算的次序列出三元式序号，三元式表只列出不同的三元式。列出不同的三元式。 三元式表中没有了重复的三元式，三元式表中没有了重复的三元式，语句的移动仅改变左边的间接码表。语句的移动仅改变左边的间接码表。三地址代码实现：间接三元式三地址代码实现：间接三元式. 写出赋值语句写出赋值语句：A=B*(C-D)-E/FG 的逆波兰表示、三元式表示、四元式表示。的逆波兰表示、三元式表示、四元式表示。n解解: 四元式表示四元式表示：( - , C , D , T1 ) (* , B , T1, T2 ) ( , F , G , T3

19、) ( / , E , T3, T4 ) ( - , T2, T4, T5 ) ( = , T5, _ , A )n解解: 三元式表示三元式表示：( - , C , D )(* , B , )( , F , G ) ( / , E , ) ( - , , ) ( = , , A )n解：解：逆波兰表示逆波兰表示： ABCD -*EFG/ - =.给出给出a := ( b + c d ) + c d的抽象语法树和的抽象语法树和DAG所对应的三地址代码。所对应的三地址代码。assigna+ bcdcd minus(a)抽象语法树抽象语法树assigna+ bcd minus(b)DAG(b)DAG

20、 .(1)E.addr表示存放E值的名字。语法制导翻译生成三地址代码 几个用到的量：(2)newtemp是个函数，对它的调用将产生一个新的临时变量。Sid:=EEE1+E2E-E1E(E1)Eid.gen(id.addr:=E.addr)产生式语义规则EE1+E2Sid:=EE.addr:=newtemp; gen(E.addr:=E1.addr +E2.addr)E-E1E.addr:=newtemp;gen(E.addr:=minusE1.addr)Entry(id).产生式语义规则E.addr:=E1.addr; E(E1) 产生赋值语句三地址代码的语法制导定义产生赋值语句三地址代码的语

21、法制导定义. .增加一条乘法的产生式及语义规则。增加一条乘法的产生式及语义规则。Eid E.addr:=id.addr; EE1*E2E.addr:=newtemp; gen(E.addr:=E1.addr *E2.addr).S.code:=E.codegen(id.addr:=E.addr)产生式语义规则EE1+E2Sid:=EE.addr:=newtemp; E.code:=E1.codeE2.codegen(E.addr:=E1.addr +E2.addr)p=lookup(); if(p=NULL) error(); else gen(p:=E.addr).EE1*E2

22、E.place:=newtemp; E.code:=E1.codeE2.code gen(E.addr:=E1.addr *E2.addr)语义规则产生式E-E1E.addr:=newtemp;E.code:=E1.codegen(E.addr:=minusE1.addr).产生式语义规则E.addr:=E1.addr; E.code:=E1.code E(E1) Eid E.addr:=id.addr; E.code:=p=lookup(); if(p!=NULL) E.addr=p; else error();.三地址语句序列是语法树的线性表示，三地址语句序列是语法树的线性表

23、示，用临时变量代替语法树中的结点。用临时变量代替语法树中的结点。实际实现中，三地址语句序列往往是被实际实现中，三地址语句序列往往是被存放到一个输出文件中，而不是将三地存放到一个输出文件中，而不是将三地址语句序列置入址语句序列置入codecode属性之中。属性之中。.思考题思考题简单算术表达式和赋值语句到四元式的翻译？简单算术表达式和赋值语句到四元式的翻译？Gen(OP, ARG1 ,ARG2 ,Result): 过程，产生四元式过程，产生四元式(1) S id := E GEN(:=,E.addr,-,id.addr)Entry(id)(2) EE1+E2 E.addr:= NewTemp;

24、Gen(+, E1.addr,E2.addr,E.addr) (3) EE1*E2 E.addr:= NewTemp; Gen(*, E1.addr,E2.addr,E.addr).(4) E - E1 E.addr:=NewTemp; Gen(minus, E1.addr, _ ,E.addr) (5) E( E1) E.addr:= E1.addr (6) Ei E.addr:=id.addr.n分析赋值语句：分析赋值语句： X= -B*(C+D) 的语法制导翻译的语法制导翻译过程。过程。n四元式序列四元式序列: (6)查表查表 (6)查表查表(6)查表查表(4)生成生成(2)生成生成(3

25、)生成生成(1)查表查表, 生成生成 (minus, B, _, T1) ( +, C, D, T2) ( *, T1, T2, T3) ( =, T3, _, X) i(X) = E.addrAE.addr * E.addr i(B )E.addr + E.addr E. addri(D )i(C)( E. addr )(5).考虑表达式的类型考虑表达式的类型 在前面关于算术表达式和赋值语句的翻译中，我在前面关于算术表达式和赋值语句的翻译中，我们假定所有的们假定所有的 i 都是同一类型的。实际上，在表都是同一类型的。实际上，在表达式中可能出现各种类型的变量或常量。达式中可能出现各种类型的变量

26、或常量。 编译程序必须做到：或者拒绝接受某种混合运算，编译程序必须做到：或者拒绝接受某种混合运算，或者产生有关类型转换的指令。或者产生有关类型转换的指令。 这种表达式和赋值语句的语义规则简单说明如下这种表达式和赋值语句的语义规则简单说明如下: (1) 引入引入语义变量语义变量 E.type 表示表达式表示表达式 E 的类型的类型 (2) 增加类型转换的三地址语句增加类型转换的三地址语句: x=inttoreal y (3) 对对EE(1)+E(2) | E(1)*E(2)的语义动作进行修改的语义动作进行修改, 增加判断表达式类型并确定类型的操作增加判断表达式类型并确定类型的操作.E E1 +

27、E2E.addr := newtempif E1.type = integer and E2.type = integer then begin gen (E.addr, :=, E1.addr, int+, E2.addr);E.type = integerendelse if E1.type = integer and E2.type = real then beginu := newtemp;gen (u, :=, inttoreal, E1.addr);gen (E.addr, :=, u, real+, E2.addr);E.type := realelse if else .1、数

28、组元素地址的计算公式 数组元素的三地址代码是什么？ 数组元素的寻址数组元素的寻址每个数组元素的宽度数组首地址=bace-low*w + i*w如何生成数组元素的三地址代码?一维数组的数组元素计算公式VAR a:ARRAY low.high OF real;求 ai的地址：base（ilow ）* w. 对于一个二维数组，可以按行或按列存放。若按行存放，则可用如下公式计算：数组地址计算： 可在编译时计算出来常量部分+变量部分：base-low*w + i*w . base（i1 一一low1）* n2i2 一一low2）*w） 令令c= （low1 *n2）low2）*w 则常量部分则常量部分=

29、alow=alow1 1,low,low2 2-c-c A1,1 A1,2 A1,3 A2,1 A2,2 A2,3 A2,3按行存放AiAi1 1,i ,i2 2 的地址的地址： A1,2= base-(1*3+1)+(1*3+2)= base+1= base（low1 *n2）low2）*w （i1*n2）i2)* w.整理后：常量部分： c=(.(low1*n2+low2)*n3+low3).)*nk +lowk) * w 变量部分变量部分v= (.(i1*n2+i2)*n3+i3.)*nk+ik)*w 多维数组Ai1,i2,.,ik 的地址的计算(.(i1*n2+i2)*n3+i3.)*

30、nk+ik)*w+base-(.(low1*n2+low2)*n3+low3.)*nk+lowk)*w ai1,i2,in的地址 =base-c+v.x:=ai1,.,in的三地址代码结构： t1: =vt2:=base-ct3:=t2t1 x:=t3. 令令a表示表示2*3的整数数组，的整数数组，c,i,j都是整数。那都是整数。那么么a的类型就是的类型就是array(2,array(3,integer)。假定整数的宽度为假定整数的宽度为4，那么，那么a类型的宽度就类型的宽度就是是24。ai的类型是的类型是array(3,integer)，宽度，宽度为为12.要求给出要求给出c+aij的三地址

31、代码。的三地址代码。t1=i*12t2=j*4t3=t1+t2t4=at3t5=c+t4.数组引用的翻译数组引用的翻译 L id E | LE .翻译翻译ai1j+bi2 其中其中a表示表示2*3的整数数组的整数数组,b为一为一维数组，整数的宽度为维数组，整数的宽度为4。翻译翻译x=aij+bi翻译翻译xk=aij+bi增加产生式及语义规则。增加产生式及语义规则。 E E1+E2E L. 试写出下列赋值语句的三地址中间代码，试写出下列赋值语句的三地址中间代码，其中数组类型为整型其中数组类型为整型(大小为大小为1)，数组的下，数组的下界为界为1，上界为，上界为10。 AAi：=i+1 t1=i-

32、1 t2=t1*1 t3=at2 t4=t3-1 t5=t4*1 t6=i+1 at5 =t6.布尔表达式的翻译 布尔表达式是用布尔运算符号布尔表达式是用布尔运算符号not (!)、and(&)、or (|)作用到布尔变量或关系表达作用到布尔变量或关系表达式上而组成的。式上而组成的。 关系表达式形式如关系表达式形式如 E1 rel E2，其中，其中E1 和和E2是是算术表达式，算术表达式， rel代表代表6个关系运算符个关系运算符: 、=、=、!= 。 程序设计语言中程序设计语言中布尔表达式有两个基本作用布尔表达式有两个基本作用： 一个是用作计算逻辑值一个是用作计算逻辑值(真真1，假，

33、假0)。 另一个是用另一个是用作控制流语句如作控制流语句如 if-else和和 while等中的条件表达式。等中的条件表达式。 无论作用如何，都必须先计算布尔表达式的值。无论作用如何，都必须先计算布尔表达式的值。 .布尔表达式的文法布尔表达式的文法 考虑由下列文法考虑由下列文法GB产生的布尔表达式：产生的布尔表达式： BB | B|B& B| ! B|E rel E|true|falsen假定使用假定使用 rel 的的 属性属性rel.op 来确定来确定 rel所指的所指的6种关系运算中的哪一个。种关系运算中的哪一个。n假定按惯例确定算术运算符，关系运算符及假定按惯例确定算术运算符，关

34、系运算符及布尔运算符布尔运算符!、&、|的优先级和结合性。的优先级和结合性。.布尔表达式的语义布尔表达式的语义 布尔式的语义布尔式的语义是指明计算一个逻辑值的规则是指明计算一个逻辑值的规则, 有两种计算规则有两种计算规则: 1. 用数值用数值(1/0)表示真和假表示真和假, 同计算算术表同计算算术表达式一样达式一样, 一步不差地按顺序计算出整个一步不差地按顺序计算出整个布尔式的值。布尔式的值。 例如例如: 计算计算 1 | (!0 & 0) | 0 =1 2. 优化优化(短路短路)方法，不一定一步不差的计方法，不一定一步不差的计算，可以由某个子布尔式的值确定整个布算，可以由某个

35、子布尔式的值确定整个布尔式的值。尔式的值。规则规则2 2用于翻译控制流语句中用于翻译控制流语句中的布尔表达式尤其方便。的布尔表达式尤其方便。.对于像对于像ab这样的关系表达式，可看成等价的这样的关系表达式，可看成等价的条件语句条件语句if ab then 1 else 0，它翻译成的，它翻译成的三地址代码为：三地址代码为：（1）ifab goto （4）（2）t =0（3）goto （5）（4）t =1（5） 其中用临时变量其中用临时变量t存放布尔表达式存放布尔表达式ab的值，的值，(5)为后续的三地址序号。为后续的三地址序号。数值表示法数值表示法.考虑由下列文法考虑由下列文法GB产生的布尔表

36、达式：产生的布尔表达式： BB | B|B& B| ! B|E rel E|true|false的语法制导翻译。的语法制导翻译。 nextstat是一个计数器，指向下一个三地址是一个计数器，指向下一个三地址语句在输出序列中的索引序号语句在输出序列中的索引序号,也就是即将也就是即将生成的三地址语句序号。生成的三地址语句序号。 地址常用属性地址常用属性place(addr)表示。表示。.BB1 | B2 B.addr =newtemp； gen（B.addr = B1.addr| B2.addr）BB1 & B2 B.addr =newtemp； gen （B.addr = B1.

37、addr & B2.addr）B!B1 B.addr =newtemp：；：； gen （B.addr =! B1.addr）B（B1） B.addr =B1.addrBE1 rel E2B.addr =newtemp； gen （if E1.addr rel E2.addr goto nextstat+3）；）； gen （B.addr =0 ）；）； gen （goto nextstat+2）；）； gen （B.addr =1）Btrue B.addr =newtemp； gen （B.addr =1）Bfalse B.addr =newtemp； gen （B.addr =0）

38、 .给出布尔表达式给出布尔表达式 ab & cd & efab & cd & ef三三地址代码。地址代码。100: if ab goto 103 101: t1=0102: goto 104103: t1=1104: if cd goto 107 105: t2=0106: goto 108107: t2=1108: t3=t1 & t2 109: if ef goto 112 110: t4=0111: goto 113112: t4=1113: t5=t3 & t4.布尔式的优化计值规则布尔式的优化计值规则解释为解释为: if B1 then

39、 true else B2 B1真则真则 B 真，不须计算真，不须计算 B2 解释为解释为: if B1 then B2 else false B1 假则假则 B 假，不须计算假，不须计算B2(a) 计算计算 B B1 B2 | = 真真真真真真假假假假假假B B1 B2 & = 真真真真真真假假假假假假(b) 计算计算 .理解布尔表达式的真、假出口 出现在条件语句：if B then S1 else S2 假出口假出口 真出口真出口 无条件转移无条件转移跳过跳过S2分支分支 中的布尔表达式中的布尔表达式 B，它的作用仅在于控制对，它的作用仅在于控制对 S1 和和 S2的选择。只要能完

40、成这一使命，的选择。只要能完成这一使命，B 的值就无需最终保的值就无需最终保留在某个临时单元中。留在某个临时单元中。n因此，作为转移条件的布尔式因此，作为转移条件的布尔式 B，可以赋予它两种，可以赋予它两种“出口出口”。 一个是一个是“真真”出口出口，为真时出向，为真时出向S1；一个；一个是是“假假”出口出口，为假时出向，为假时出向S2。.if B then S1 else S2 的代码结构 语义值语义值B.code 表示表示 布尔式布尔式B的中间代码的中间代码 语义值语义值S.code 表示表示 语句语句S的中间代码的中间代码n语义值语义值B.true, 真出口真出口，B为为真真时控制流转向

41、的标时控制流转向的标号号n语义值语义值B.false, 假出口假出口，B为为假假时控制流转向的时控制流转向的标号标号n语义值语义值S.next, 一个标号一个标号, 表示紧随表示紧随S代码之后的地址代码之后的地址B.codeS1.codeGoto S.nextS2.codeB.ture:B.false:S.next:To B.tureTo B.false.S if B then S1 | if B then S1 else S2 | while B do S1 | S1; S2 控制流语句的翻译控制流语句的翻译.B.codeS1.codeB.true:. . .指向指向B.true指向指向B.

42、false(a) if-thenB.codeS1.codeB.true:. . .指向指向B.true指向指向B.falseB.false:goto S.nextS2.code(b) if-then-elseB.codeS1.codeB.true:. . .指向指向B.true指向指向B.falsegoto S.beginS.begin:(c) while-doS1.codeS2.codeS1.next:. . .(d) S1; S2.S if B then S1B.true := newlabel; B.false := S.next; S1.next := S.next; S.code :

43、= B.code | gen(B.true, :) | S1.code B.codeS1.codeB.true:. . .指向指向B.true指向指向B.false(a) if-then.S if B then S1 else S2B.true := newlabel; B.false := newlabel; S1.next := S.next; S2.next := S.next; S.code := B.code | gen(B.true, :) | S1.code | gen(goto, S.next) | gen(B.false, :) |S2.code B.codeS1.codeB

44、.true:. . .指向指向B.true指向指向B.falseB.false:goto S.nextS2.code(b) if-then-else.S while B do S1 S.begin:= newlabel; B.true := newlabel; B.false := S.next; S1.next := S.begin; S.code := gen(S.begin, :) | B.code | gen(B.true, :) | S1.code | gen(goto, S.begin) B.codeS1.codeB.true:. . .指向指向B.true指向指向B.falseg

45、oto S.beginS.begin:(c) while-do.S S1; S2S.code := S1.code | gen(S1.next, :) | S2.code S1.codeS2.codeS1.next:. . .(d) S1; S2.布尔表达式的翻译布尔表达式的翻译如果如果B是是a b的形式，的形式，那么代码是：那么代码是：if a b goto B.truegoto B.false.表达式表达式a b & c d & e f的代码是：的代码是：if a b goto L1goto LfalseL1:if c d goto L2goto LfalseL2:if e

46、 f goto Ltruegoto Lfalse.B B1 | B2B1.true := B.true; B1.false := newlabel; B2.true := B.true; B2.false := B.false; B.code := B1.code | gen(B1.false, :) | B2.code B ！ B1B1.true := B.false; B1.false := B.true; B.code := B1.code .B B1 & B2B1.true := newlabel; B1.false := B.false; B2.true := B.true;

47、 B2.false := B.false; B.code := B1.code | gen(B1.true, :) | B2.code B (B1 ) B1.true := B.true; B1.false := B.false; B.code := B1.code .B id1 relop id2B.code := gen(if, id1.addr, relop.op, id2.addr, goto, B.true) | gen(goto, B.false) B trueB.code := gen(goto, B.true)B falseB.code := gen(goto, B.false

48、). 给出给出x200&x!=y的三地址翻译。的三地址翻译。If x200 goto L2 goto LfalseL2: if x!=y goto Ltrue goto LfalseLtrue:Lfalse:. 考虑如下语句：考虑如下语句： while ab do if cd then x：= yz else x：y-z 根据前面所述，生成根据前面所述，生成代码代码. L1 ： if ab goto L2 goto Lnext L2 ： if cd goto L3 goto L4 L3 ： t1 ：= yz x：t1 goto L1 L4 ： t2:=yz x：t2 goto L1 L

49、next： .回填 先产生暂时没有填写目标标号的转移指令。先产生暂时没有填写目标标号的转移指令。 对于每一条这样的指令作适当的记录，对于每一条这样的指令作适当的记录， 一旦目标标号被确定下来，再将它一旦目标标号被确定下来，再将它“回填回填”到相应的指令中。到相应的指令中。.使用回填翻译控制语句中的布尔表达式 （1）BB1 | B2 （把文法翻译成什么形式） （2） | B1 & B2 B1.code B2.codeB1.false:to B1.trueto B1.falseto B2.trueto B2.false B1.code B2.codeB1.true:to B1.trueto

50、 B1.falseto B2.trueto B2.falseto B.trueto B.falseto B.trueto B.false.使用回填翻译控制语句中的布尔表达式 （3） | ! B1 （4） | (B1) B1.codeto B1.trueto B1.falseB.codeto B.falseto B.true B1.codeto B1.trueto B1.falseB.codeto B.trueto B.false.使用回填翻译控制语句中的布尔表达式 （5） | id1 rel id2 （6） | true （7） | false B.code if id1 relop id2

51、then goto B.true goto B.false to B.falseto B.trueB.code goto B.true to B.trueB.code goto B.false to B.false.使用回填翻译控制语句中的布尔表达式 （1）BB1 | M B2 （2） | B1 & M B2 （3） | ! B1 （4） | (B1) （5） | id1 rel id2 （6） | true （7） | false （8）M插入非终结符号M是为了引入一个语义动作，以便在适当的时候获得即将产生的下一个(三地址代码）四元式的索引。.翻译模式用到如下三个函数：翻译模式用到如

52、下三个函数： 1makelist(i)：创建一个仅包含创建一个仅包含i的新表，的新表，i 是三地址代码数组的一个索引（下标），是三地址代码数组的一个索引（下标），或说或说 i是三地址代码序列的一个标号。是三地址代码序列的一个标号。 2merge(p1，p2)：连接由指针连接由指针p1和和p2指向的指向的两个表并且返回一个指向连接后的表的指针。两个表并且返回一个指向连接后的表的指针。 3backpatch（p，i）：）：把把i作为目标标号回作为目标标号回填到填到p所指向的表中的每一个转移指令中去。所指向的表中的每一个转移指令中去。此处的此处的“表表”都是为都是为“反填反填”所拉的链所拉的链.BB

53、1 | MB2 backpatch(B1.false,M.next); B.true:=merge(B1.true,B2.true); B.false:=B2.false BB1 & MB2 backpatch(B1.true,M.next); B.true:=B2.true; B.false:=merge(B1.false,B2.false);.B! B1 B.true:=B1.false; B.false:=B1.true B ( B1 ) B.true:= B1.true; B.false:=B1.false B id1 rel id2 B.true:=nextstat; B.f

54、alse:= nextstat+1; gen(ifid1.addr rel.op id2.addrgoto); gen(goto); .B true B.true:= nextstat; gen(goto); B false B.false:= nextstat; gen(goto); M M.next:=nextstat .例 重新考虑表达式ab | cd & ef 一棵作了注释的分析树如下图所示B.t=100,104B.f=103,105B.t=100B.f=101B.t=104B.f=103,105or M.q=102a bB.t=102B.f=103B.t=104B.f=105

55、andM.q=104cefd. 依次分析，得到如下三地址： 100 ： if ab goto- 101 ： goto- 102 ：if cd goto- 103 ： goto- 104 ： if ef goto- 105 ： goto- 经过回填得到： 100 ： if ab goto L1 101 ： goto l02 102 ： if cd goto l04 103 ： goto - 104 ： if ef goto L1 105 ： goto - 当知道了条件为真时和条件为假时分别应做哪些事时就可以进行回填。.控制流语句的翻译模式：控制流语句的翻译模式：1. Sif B then M1

56、S1B.codeS1.codeB.true:.B.false:to B.trueto B.falseM1处反填B.true backpatch( B.true,M.next); S.next := merge(B.false ,S1.next) .控制流语句的翻译模式：控制流语句的翻译模式：2. Sif B then M1 S1 N else M2 S2 B.codeS1.codeB.true:S2.codeB.false:goto S.next.S.next:to B.trueto B.falseM1处反填B.trueM2处反填B.falseN出生成 goto S.next . backpa

57、tch( B.true,M1.next); backpatch(B.false,M2.next); S.next := merge(S1.next,N.next,S2.next) N N.next := nextstat; emit(goto ) .控制流语句的翻译模式：控制流语句的翻译模式：2. Swhile M1 B do M2 S1B.codeS1.codeB.true:B.false:goto S.begin.S.begin:to B.falseto B.trueM1处反填S1.next生成标号S.beginM2处反填B.true. backpatch(B.true,M2.next); backpatch(S1.next,M1.next); S.next := B.false; emit(gotoM1.next) S begin L end S.next := L.next S A S.next := makelist() LL1;M S backpatch(L1.next,M.next); L.next := S.next LS L.next:=S.next . 先记录要回填的转移指令地址，在适当的时候进行回填，以便赋值和布尔表达式的求值得到合适的连接，以完成程序