【精品】【考研计算机专业课】天津大学 编译原理讲义 中间代码表示法5.2（可编辑.ppt

《【精品】【考研计算机专业课】天津大学 编译原理讲义 中间代码表示法5.2（可编辑.ppt》由会员分享，可在线阅读，更多相关《【精品】【考研计算机专业课】天津大学 编译原理讲义 中间代码表示法5.2（可编辑.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【考研计算机专业课】天津大学 编译原理讲义 中间代码表示法5.2这种表示表达式的方法称为这种表示表达式的方法称为后缀式后缀式。ab+把双目运算符放在两个运算量的中间的把双目运算符放在两个运算量的中间的中缀表示法中缀表示法。a+b 把运算符放在其运算量前面的把运算符放在其运算量前面的前缀表示法前缀表示法。+ab共同的特点是共同的特点是:1.操作符的个数不变操作符的个数不变 2.操作数的次序和个数不变操作数的次序和个数不变 逆波兰表示法还具有两个明显的优点逆波兰表示法还具有两个明显的优点:1.无括号，形式简洁清楚无括号，形式简洁清楚 2.操作符的顺序与运算的次序完全相同操作符的顺序与运算的次序完全

2、相同 1.一般表达式一般表达式(中缀式中缀式)转化成逆波兰式转化成逆波兰式(后缀式后缀式)(1)从整体到局部的方法从整体到局部的方法设设e是给定表达式，是给定表达式，是相应的逆波兰式是相应的逆波兰式则则=a 其中其中:运算量运算量 a变量变量(暂只考虑简单变量，常数暂只考虑简单变量，常数)例例，=*=*=a*cd*=ab*+*cd*=例例，=*=ab*cd*=a+*cd*=abcd*+*cd*(2)自左向右扫描的方法自左向右扫描的方法 将表达式中的所有变量按原顺序排列。将表达式中的所有变量按原顺序排列。设有子表达式设有子表达式e1e2，则称，则称e2的后继符为的后继符为(运算符运算符)的分界的

3、分界符，把每个运算符移到相应的分界符处，并去掉括号符，把每个运算符移到相应的分界符处，并去掉括号；若一个若一个符号是多个运算符的分界符，则按符号是多个运算符的分界符，则按“后者先移后者先移”的原则进行。的原则进行。例例:a*(b+c)逆波兰式逆波兰式 abc+abc+*例例:a*(b*cd)e逆波兰式逆波兰式 abc abc*d-d-*e-e-栈栈当前输入符当前输入符后缀式后缀式空空aab+c*ab bb+c*ab+c*E1 cc*E1c*E23.后缀式的推广后缀式的推广我们可以将后缀式简单的推广到比表达式更大的范围。我们可以将后缀式简单的推广到比表达式更大的范围。例例，如下的条件算术表达式，

4、如下的条件算术表达式:e?x:y表示若表示若e0，则此式值为，则此式值为x；否则，为否则，为y。若把若把e?x:y表示成表示成一个三目运算一个三目运算exy，这种方式出现的，这种方式出现的问题问题是是:任何情况下，第二目任何情况下，第二目x和第三目和第三目y均得计算一次，会造成时均得计算一次，会造成时间的浪费。间的浪费。克服它的一种可行办法是克服它的一种可行办法是引进标号引进标号,条件转移和无条件转移算符条件转移和无条件转移算符。令后缀式存放在令后缀式存放在一维数组一维数组POST1:n中，每个数组元素存中，每个数组元素存放一个运算量或运算符或标号。放一个运算量或运算符或标号。所引进的标号是一

5、个下标，指向数组的某元素。所引进的标号是一个下标，指向数组的某元素。无条件转移无条件转移 j，如如pj表示表示:转移到转移到POSTp(单目算符单目算符)。条件转移条件转移 j(小于转移算符小于转移算符)，如，如 e1e2pj表示表示:若若e1小于小于e2，则转移到则转移到POSTp(三目算符三目算符)。jez(0转移算符转移算符)，如，如 epjez表示表示:若若e等于等于false，则转移到则转移到POSTp(双目算符双目算符)。jnz(非非0转移算符转移算符)，如，如 epjnz表示表示:若若e不不等于等于false，则转移到则转移到POSTp(双目算符双目算符)。用后缀式来表示各种语句

6、。用后缀式来表示各种语句。(1)赋值语句的逆波兰式赋值语句的逆波兰式赋值语句赋值语句x:=e逆波兰式逆波兰式:=(2)转移语句的逆波兰式转移语句的逆波兰式 转移语句转移语句gotoL，其中其中L是标号。是标号。逆波兰式逆波兰式Lj，其中其中j是单目算符，转向标号处。是单目算符，转向标号处。(3)条件语句的逆波兰式条件语句的逆波兰式条件语句条件语句:ifethenxelsey逆波兰式逆波兰式:ep1jezxp2jp1:yp2:其中，后跟冒号的标号并不真正出现在后缀式中，它们仅其中，后跟冒号的标号并不真正出现在后缀式中，它们仅仅在书面上指明有关式子的开始位置。仅在书面上指明有关式子的开始位置。在在

7、POST中出现的后缀式将是中出现的后缀式将是:ep1jezxp2jyp1p2例例:ifabthenx:=a+belsey:=a-b逆波兰式表示为逆波兰式表示为:abi+jthenk:=k-1；goto10beginendelsek:=i*i-j*j；i:=0；j:=0；beginend逆波兰表示为逆波兰表示为:(2)k100:=(3)kij+jez(0转转)(4)kk1-:=(6)kii*jj*-:=(7)i0:=(1)block(9)blockend(8)j0:=(3)kij+6jez(0转转)(5)3j(4)循环语句的逆波兰表示循环语句的逆波兰表示循环语句循环语句:for(i=a;ib;i

8、+)s，先将其变成等价的条，先将其变成等价的条件语句件语句:i:=a；10:ifi=bthenbegins；i:=i+1；goto10end然后按条件语句形式转换。然后按条件语句形式转换。例例，循环语句，循环语句for(i=1;i=100;i+)s=s+i;先展成等价的条件语句先展成等价的条件语句:i:=1；10:ifi=100thenbegins:=s+i；i:=i+1；goto10end然后转换成逆波兰式然后转换成逆波兰式:(1)i1:=(4)i100=21jez(9)ssi+:=(14)ii1+:=(19)4j(21)4.语法制导生成后缀式语法制导生成后缀式原理性描述如下原理性描述如下:

9、产生式产生式语义动作语义动作(1)EE（1）opE（2）E.CODE=E（1）.CODEE（2）.CODEop(2)E(E（1）)E.CODE=E（1）.CODE(3)EiE.CODE=i其中其中:E.CODE后缀式符号串后缀式符号串“捻接捻接”操作操作i标识符标识符(如如a或或b或或c)第第(1)产生式语义动作的意思是，产生式语义动作的意思是，E的后缀式等于的后缀式等于E（1）和和E（2）两后缀式的捻接，而后再接上算符两后缀式的捻接，而后再接上算符op。第第(2)产生式的语义动作指出，把括号无条件地去掉。产生式的语义动作指出，把括号无条件地去掉。第第(3)产生式的语义动作说明，标识符的语义值

10、是那个标识符自产生式的语义动作说明，标识符的语义值是那个标识符自身。身。符号串的捻接符号串的捻接(并置并置)运算，对于机器实现来说，这种运算的代价运算，对于机器实现来说，这种运算的代价是极高的，如果安排一个数组存放后缀式，那么语义动作可以不是极高的，如果安排一个数组存放后缀式，那么语义动作可以不涉及捻接运算。涉及捻接运算。令数组为令数组为POST，K为下标，初值为为下标，初值为1，则上述语义动作，则上述语义动作可改写为可改写为:产生式产生式程序段程序段(1)EE（1）opE（2）POSTk=op；k=k+1(2)E(E（1）)(3)EiPOSTk=i；k=k+1例例，(a+b)*c其规约过程如

11、下其规约过程如下:(a+b)*c (E+b)*c (E+E)*c (E)*c E*c E*E E其后缀式的形成过程如下其后缀式的形成过程如下:POST数组数组E(a+b)*cak=1(E+b)*cabk=2(E+E)*cab+k=3(E)*cab+k=3E*cab+ck=4E*Eab+c*k=55.2.2三元式表示法三元式表示法表达式及各种语句也可以表示成一组三元式。每个三元式包表达式及各种语句也可以表示成一组三元式。每个三元式包括三个组成部分括三个组成部分:OP,ARG1,ARG2,表示形式为三元组表示形式为三元组(OP,ARG1,ARG2)。其中其中:OP算符。算符。ARG1，ARG2运算

12、量指示器，指向有关符号表的某一位运算量指示器，指向有关符号表的某一位置置(通常用标识符表示通常用标识符表示)，或指向三元式表自身的某一项。，或指向三元式表自身的某一项。例例，表达式表达式:A+B*C三元式表示三元式表示:(1)(*,B,C)(2)(+,A,(1)对单目运算符对单目运算符，只使用只使用ARG1Op可以是可以是:+，*，j，jzjez双目，等于双目，等于0转移转移jnz双目，非双目，非0转移转移j三目，大于转三目，大于转j单目，无条件转移单目，无条件转移1 1、表达式和赋值语句的三元式、表达式和赋值语句的三元式例例，布尔表达式：布尔表达式：ABxy+1(x0B)D其中其中:A,B,

13、D为布尔量；为布尔量；x,y为算术量为算术量用三元式表示用三元式表示:(1)(,y,1)(5)(,x,0)(2)(,x,(1)(3)(,B,(2)(4)(,A,(3)(6)(,(5),B)(7)(,(6),D)(8)(,(4),(7)例例，赋值语句赋值语句:x:=a*b+c/d用三元式表示用三元式表示:(1)(*,a,b)(2)(/,c,d)(3)(+,(1),(2)(4)(:=,*,(3)2 2、转移语句和条件语句的三元式转移语句和条件语句的三元式例例，条件语句条件语句ifxythenz:=xelsez:=y+1用三元式表示用三元式表示:(1)(,x,y)(2)(jez,(1),)(jez为

14、单目运算，等于为单目运算，等于0转转)(3)(:=,z,x)(4)(j,)(j为无条件转至为无条件转至(7)，单目运算，单目运算)(5)(+,y,1)(6)(:=,z,(5)(7)真真假假(2)(jez,(1),(5)(jez为单目运算，等于为单目运算，等于0转转)(4)(j,(7),)(j为无条件转至为无条件转至(7)，单目运算，单目运算)例例，程序段，程序段:begink:=100；10:ifki+jthenbegink:=k1；goto10endelsek:=i*ij*j；i:=0；j:=0；end用三元式表示用三元式表示:(1)(block,)(2)(:=,k,100)(3)(+,i,

15、j)(4)(,k,(3)(5)(jez,(4),)(6)(-,K,1)(7)(:=,K,(6)(8)(j,(3),)(9)(*,i,i)(10)(*,j,j)(11)(-,(9),(10)(12)(:=,k,(11)(13)(:=,i,0)(14)(:=,j,0)(15)(blockend,)(5)(jez,(4),(9)3 3、循环语句的三元式、循环语句的三元式例例，循环语句循环语句:fori:=1to100dos:=s+i首先将其展开为首先将其展开为:i:=1；10:ifi=100thenbegins:=s+i；i:=i+1；goto10end再转化成三元式再转化成三元式:(1)(:=,i

16、,1)(2)(=,i,100)(3)(jf,(2),)(4)(+,s,i)(5)(:=,s,(4)(6)(+,i,1)(7)(:=,i,(6)(8)(j,(2),)(9)(3)(jf,(2),(9)4 4.三元式的语法制导翻译三元式的语法制导翻译产生式产生式语义动作语义动作(1)EE(1)opE(2)E.VAL=TRIP(op,E(1).VAL,E(2).VAL)(2)E(E(1)E.VAL=E(1).VAL(3)E-E(1)E.VAL=TRIP(,E(1).VAL,)(4)EiE.VAL=ENTRY(i)E.VAL指示器，指向有关符号表的某一项或指向三元式表中指示器，指向有关符号表的某一项或

17、指向三元式表中的某一项。的某一项。TRIP(op,ARG1,ARG2)语义过程，产生新三元式。此过语义过程，产生新三元式。此过程将回送新产生的三元式放在三元式表中的位置。程将回送新产生的三元式放在三元式表中的位置。单目运算单目运算“负负”。ENTRY(i)语义过程，查找并取得与语义过程，查找并取得与i相对应的标识符在符号表相对应的标识符在符号表中的位置中的位置(入口入口)。5.2.3树结构表示法树结构表示法在语法树的基础上进行简化，形成抽象的树型数据结构，在语法树的基础上进行简化，形成抽象的树型数据结构，常用来表示中间代码。这种树中，常用来表示中间代码。这种树中，非叶结点非叶结点和和叶结点叶结

18、点(端末端末结结)分别代表分别代表运算符运算符和和运算量运算量。如右图如右图:e1、e2为表达式，为表达式，T1表示表示为为e1的树，的树，T2表表示示为为e2的树，则的树，则T1+T2表示表示e1+e2的树的树T1 T2+e1+e2T1*T2表示表示e1*e2的树的树T1 T2*e1*e2-T1表示表示-e1的树的树T1 -e1双目运算对应二叉子树，多目运算对应多叉子树。双目运算对应二叉子树，多目运算对应多叉子树。多叉子树可以通过引进新结而表示成二叉子树。多叉子树可以通过引进新结而表示成二叉子树。将一个表达式翻译成树结构表示将一个表达式翻译成树结构表示:产生式产生式语义动作语义动作(1)EE

19、(1)opE(2)E.VAL=NODE(op,E(1).VAL,E(2).VAL)(2)E(E(1)E.VAL=E(1).VAL(3)E-E(1)E.VAL=UNARY(,E(1).VAL)(4)EiE.VAL=LEAF(i)E.VAL指示器，指向树的一个结。指示器，指向树的一个结。NODE(op,LEFT,RIGHT)函数过程，建立二叉树，回函数过程，建立二叉树，回送的值是一个指示器，指向这新树根。送的值是一个指示器，指向这新树根。UNARY(OP,CHILD)与与NODE类似，只有一个枝。类似，只有一个枝。LEAF(i)建立以建立以i.LEXVAL指示的结并回送此结的地址，此指示的结并回送此结的地址，此结为端末结。结为端末结。例例，A*B+C*D可表示成可表示成:输入输入栈栈树结构树结构A*B+C*D*B+C*DiB+C*DE*+C*DE*iC*DE+*DE+iDE+E*B+C*DEA+C*DE*EB*DE+ECE+E*iE+E*ED+C*DE*(1)*(2)E+E+E表示成三元式表表示成三元式表:OPARG1ARG2(1)*AB(2)*CD(3)+(1)(2)由此表可见，它与树结构表示相对应，每个三元式对由此表可见，它与树结构表示相对应，每个三元式对应一棵二叉树。应一棵二叉树。