最新【考研计算机专业课】天津大学 编译原理讲义 中间代码表示法5.2(共33张PPT课件).pptx

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

1、5.2 中间代码表示法中间代码表示法5.2.1 逆波兰逆波兰(b ln)表示法表示法 逆波兰表示法逆波兰表示法是一种在不使用括号的情况是一种在不使用括号的情况(qngkung)下无二义的说下无二义的说明算术表达式的一种方法。明算术表达式的一种方法。 这种表示法是把运算量这种表示法是把运算量 (操作数操作数) 写在前面写在前面(qin mian)，把算符写在后面，把算符写在后面(后缀后缀)。 例例，把，把a+b写成写成ab+ 把把a+(b*c)写成写成abc*+ 扩展扩展: 一般而言，若一般而言，若是一个是一个k ( 1 ) 目算符，它对运算量目算符，它对运算量 e1, e2, , ek 作用的

2、结果将被表示成作用的结果将被表示成e1e2ek。 第一页，共三十三页。这种表示表达式的方法称为这种表示表达式的方法称为(chn wi)后缀式后缀式。 ab+ 把双目运算符放在两个把双目运算符放在两个(lin )运算量的中间的运算量的中间的中缀表示法中缀表示法。 a+b 把运算符放在其运算量前面把运算符放在其运算量前面(qin mian)的的前缀表示法前缀表示法。 +ab共同的特点是共同的特点是:1. 操作符的个数不变操作符的个数不变 2. 操作数的次序和个数不变操作数的次序和个数不变 逆波兰表示法还具有两个明显的优点逆波兰表示法还具有两个明显的优点: 1. 无括号，形式简洁清楚无括号，形式简洁

3、清楚 2. 操作符的顺序与运算的次序完全相同操作符的顺序与运算的次序完全相同 第二页，共三十三页。1. 一般表达式一般表达式 (中缀式中缀式) 转化成逆波兰转化成逆波兰(b ln)式式(后缀式后缀式)(1) 从整体到局部从整体到局部(jb)的方法的方法 设设e是给定表达式，是给定表达式，是相应的逆波兰式是相应的逆波兰式 则则 = = = a 其中其中: 运算量运算量 a 变量变量 (暂只考虑简单变量，常数暂只考虑简单变量，常数) 第三页，共三十三页。例例， = = *= *= a*cd*= ab*+*cd*= 例例， = = *= ab*cd*= a+*cd*= abcd*+*cd*第四页，共

4、三十三页。(2) 自左向右扫描自左向右扫描(somio)(somio)的方法的方法 将表达式中的所有将表达式中的所有(suyu)(suyu)变量按原顺序排列。变量按原顺序排列。 设有子表达式设有子表达式e1e2，则称，则称e2的后继符为的后继符为(运算符运算符) 的分界符，把每的分界符，把每个运算符移到相应的分界符处，并去掉括号个运算符移到相应的分界符处，并去掉括号；若一个符号是多个运算符的若一个符号是多个运算符的分界符，则按分界符，则按“后者先移后者先移”的原则的原则(yunz)(yunz)进行。进行。 例例: : a * ( (b+c) ) 逆波兰式逆波兰式 abc+ abc+* 例例:

5、: a * (b * c d ) e 逆波兰式逆波兰式 abc abc*d-d-*e-e- 第五页，共三十三页。从左向右扫描从左向右扫描，先遇到，先遇到+双目运算双目运算，完成完成a+b运算，再遇到运算，再遇到*双目运算，完成双目运算，完成(a+b)*c运算运算，从而从而(cng r)(cng r)得到分解得到分解 (a+b)*c 。 例例，ab+c* =分解分解(fnji)(fnji)= (a+b)*c 从右向左扫描从右向左扫描(somio)(somio)，先遇到，先遇到*双目运算双目运算，它的左侧应有两个运算量，它的左侧应有两个运算量，首先是首先是c是一个简单变量，它是参加运算的第二个运算

6、量。再向左遇是一个简单变量，它是参加运算的第二个运算量。再向左遇到到+双目运算，说明参加双目运算，说明参加* 运算的第一个运算量应是运算的第一个运算量应是+运算运算的结果，然后再对的结果，然后再对+运算实施分解。运算实施分解。 使用后缀式，可以根据运算量和运算符出现的先后位置，以及每个算符的目使用后缀式，可以根据运算量和运算符出现的先后位置，以及每个算符的目数就完全决定了一个表达式的数就完全决定了一个表达式的分解分解。 第六页，共三十三页。2. 后缀后缀(huzhu)(huzhu)式的计值式的计值 表达式的后缀表示表达式的后缀表示，可以，可以使用使用(shyng)(shyng)一个栈一个栈 来

7、计算它的值。来计算它的值。 计算过程计算过程: : 自左向右扫描后缀自左向右扫描后缀(huzhu)(huzhu)式，每逢遇到运算量就令其式，每逢遇到运算量就令其入栈；入栈； 遇到遇到K目运算符，则将它作用于栈顶的目运算符，则将它作用于栈顶的K个项，并用运算结个项，并用运算结果代替这果代替这K个项。个项。 例例，ab+c* 的计值过程如下的计值过程如下: :1. 遇遇a，a入栈。入栈。 2. 遇遇b， b入栈。入栈。 3. 遇遇+，将栈顶两项相加将栈顶两项相加，移走，移走b、a，把和把和E1置于栈顶。置于栈顶。 4. 遇遇c， c入栈。入栈。 5. 遇遇*，将栈顶两项相乘将栈顶两项相乘，移走移走

8、c、E1，把积把积E2置于栈顶置于栈顶。第七页，共三十三页。栈栈当前输入符当前输入符后缀式后缀式空空aab+c*ab bb+c*ab+ +c*E1 cc*E1c*E2第八页，共三十三页。3. 后缀后缀(huzhu)(huzhu)式的推广式的推广 我们可以将后缀式简单我们可以将后缀式简单(jindn)(jindn)的推广到比表达式更大的范围。的推广到比表达式更大的范围。 例例，如下的条件算术表达式，如下的条件算术表达式:e ? x : y表示若表示若e0，则此式值为，则此式值为x；否则，为否则，为y。 若把若把e ? x : y表示成表示成一个三目运算一个三目运算exy，这种方式出现的，这种方式

9、出现的问题问题是是: : 任何任何情况下，第二目情况下，第二目x和第三目和第三目y均得计算一次，会造成时间均得计算一次，会造成时间(shjin)(shjin)的浪费。的浪费。 克服它的一种可行办法是克服它的一种可行办法是引进标号引进标号, 条件转移和无条件转移算符条件转移和无条件转移算符。 第九页，共三十三页。令后缀式存放在令后缀式存放在一维数组一维数组 POST1:n 中，每个数组元素中，每个数组元素(yun s)(yun s)存存放一个运算量或运算符或标号。放一个运算量或运算符或标号。 所引进的标号是一个所引进的标号是一个(y )(y )下标，指向数组的某元素。下标，指向数组的某元素。 无

10、条件转移无条件转移(zhuny)(zhuny) j，如如 p j 表示表示: : 转移到转移到 POSTp (单目算符单目算符) 。 条件转移条件转移 j( (小于转移算符小于转移算符) )，如，如 e1 e2 p j表示表示: 若若e1小于小于e2，则转移，则转移到到POSTp (三目算符三目算符)。 jez( (0转移算符转移算符) )，如，如 e p jez表示表示: : 若若e等于等于false，则转移到则转移到 POSTp (双双目算符目算符)。 jnz( (非非0转移算符转移算符) )，如，如 e p jnz表示表示: : 若若e不不等于等于false，则转移到则转移到 POSTp

11、 (双目算符双目算符)。 第十页，共三十三页。用后缀式来表示各种用后缀式来表示各种( zhn)( zhn)语句。语句。 (1) 赋值语句赋值语句(yj)(yj)的逆波兰式的逆波兰式 赋值语句赋值语句(yj)(yj) x := e 逆波兰式逆波兰式 := (2) 转移语句的逆波兰式转移语句的逆波兰式 转移语句转移语句 goto L，其中其中L是标号。是标号。 逆波兰式逆波兰式 L j，其中其中 j是单目算符，转向标号处。是单目算符，转向标号处。 第十一页，共三十三页。(3) 条件条件(tiojin)(tiojin)语句的逆波兰式语句的逆波兰式 条件条件(tiojin)(tiojin)语句语句:

12、if e then x else y 逆波兰逆波兰(b ln)(b ln)式式: e p1 jez x p2 j p1: y p2: 其中，后跟冒号的标号并不真正出现在后缀式中，它们仅仅在书面上其中，后跟冒号的标号并不真正出现在后缀式中，它们仅仅在书面上指明有关式子的开始位置。指明有关式子的开始位置。 在在POST中出现的后缀式将是中出现的后缀式将是: : ep1jezxp2jyp1p2第十二页，共三十三页。例例: if ab then x:=a+b else y:=a-b 逆波兰式表示为逆波兰式表示为: abi+j then k:=k- -1；goto 10 beginendelse k:=

13、i*i - - j*j； i:=0；j:=0；beginend逆波兰逆波兰(b ln)(b ln)表示为表示为: :(2) k 100 := (3) k i j + jez (0转转) (4) k k 1 - - := (6) k i i * j j * - - := (7) i 0 := (1) block (9) blockend (8) j 0 := (3) k i j + 6 jez (0转转) (5) 3 j第十三页，共三十三页。(4) 循环语句的逆波兰循环语句的逆波兰(b ln)(b ln)表示表示 循环语句循环语句(yj)(yj): :for (i=a;ib;i+) s ，先将其

14、变成等价的条，先将其变成等价的条件语句件语句: : i:=a；10: if i=b thenbegins；i:=i+1；goto 10 end然后然后(rnhu)(rnhu)按条件语句形式转换。按条件语句形式转换。 第十四页，共三十三页。例例，循环，循环(xnhun)(xnhun)语句语句 for (i=1;i=100;i+) s=s+i; 先展成等价的条件语句先展成等价的条件语句: : i:=1；10: if i=100 then begins:=s+i；i:=i+1；goto 10 end然后转换成逆波兰式然后转换成逆波兰式: : (1) i 1 := (4) i 100 = 21 jez

15、 (9) s s i + := (14) i i 1 + := (19) 4 j (21)第十五页，共三十三页。4. 语法语法(yf)(yf)制导生成后缀式制导生成后缀式 原理性描述原理性描述(mio sh)如下如下: 产生产生(chnshng)式式 语义动作语义动作 (1) EE（1）op E（2） E.CODE = E（1）.CODEE（2）.CODEop (2) E( E（1）) E.CODE = E（1）.CODE (3) E i E.CODE = i 其中其中: : E.CODE后缀式符号串后缀式符号串 “捻接捻接”操作操作 i 标识符标识符 (如如a 或或b或或c ) 第十六页，共

16、三十三页。第第(1)产生产生(chnshng)(chnshng)式语义动作的意思是，式语义动作的意思是，E 的后缀式等于的后缀式等于E（1） 和和 E（2） 两后缀式的捻接，而后再接上算符两后缀式的捻接，而后再接上算符op。 第第(2)产生产生(chnshng)(chnshng)式的语义动作指出，把括号无条件地去掉。式的语义动作指出，把括号无条件地去掉。 第第(3)产生式的语义动作说明，标识符的语义值是那个产生式的语义动作说明，标识符的语义值是那个(n ge)(n ge)标识符自身。标识符自身。 符号串的捻接符号串的捻接 (并置并置) 运算，对于机器实现来说，这种运算的代价是极高的，运算，对于

17、机器实现来说，这种运算的代价是极高的，如果安排一个数组存放后缀式，那么语义动作可以不涉及捻接运算。如果安排一个数组存放后缀式，那么语义动作可以不涉及捻接运算。第十七页，共三十三页。令数组为令数组为POST，K为下标，初值为为下标，初值为1，则上述，则上述(shngsh)(shngsh)语义动语义动作可改写为作可改写为: : 产生产生(chnshng)(chnshng)式式 程序段程序段 (1) E E（1）op E（2） POSTk = op；k=k+1 (2) E ( E（1）) (3) E i POSTk = i；k=k+1 例例，(a+b) * c 其规约过程其规约过程(guchng)(

18、guchng)如下如下: : (a + b ) * c (E + b ) * c (E + E) * c (E) * c E * c E * E E第十八页，共三十三页。其后缀式的形成其后缀式的形成(xngchng)(xngchng)过程如过程如下下: :POST数组数组 E ( a + b ) * c a k=1 ( E+ b ) * c a b k=2 ( E+ E ) * c a b + k=3 ( E ) * c a b + k=3 E * c a b + c k=4 E * E a b + c * k=5 第十九页，共三十三页。5.2.2 三元三元(sn yun)式表示法式表示法 表

19、达式及各种语句也可以表示成一组三元式。每个三元式包括三个组表达式及各种语句也可以表示成一组三元式。每个三元式包括三个组成部分成部分: OP, ARG1, ARG2 , 表示形式表示形式(xngsh)(xngsh)为三元组为三元组 (OP, ARG1, ARG2 ) 。其中其中: OP算符。算符。 ARG1，ARG2运算量指示器，指向有关符号表的某一位置运算量指示器，指向有关符号表的某一位置 (通常用标识符表示通常用标识符表示(biosh)(biosh)，或指向三元式表自身的某一项。，或指向三元式表自身的某一项。 例例，表达式表达式: A + B * C 三元式表示三元式表示: :(1) ( *

20、 , B , C ) (2) ( + , A , (1) ) 对单目运算符对单目运算符，只使用只使用ARG1 Op可以是可以是: +，*，j，jz 第二十页，共三十三页。jez 双目，等于双目，等于(dngy)0转移转移jnz 双目，非双目，非0转移转移j 三目，大于转三目，大于转j 单目，无条件转移单目，无条件转移 第二十一页，共三十三页。1 1、表达式和赋值语句、表达式和赋值语句(yj)(yj)的三元式的三元式 例例，布尔表达式：布尔表达式：ABxy+1 ( (x0B) D 其中其中: A , B, D为布尔量；为布尔量；x, y为算术量为算术量用三元用三元(sn yun)(sn yun)

21、式表示式表示: : (1) (, y, 1 )(5) (, x, 0 )(2) (, x, (1) )(3) (, B, (2) )(4) (, A, (3) )(6) (, (5), B )(7) (, (6), D )(8) (, (4), (7) )第二十二页，共三十三页。例例， 赋值语句赋值语句(yj)(yj): x := a * b + c / d 用三元用三元(sn yun)(sn yun)式表示式表示: : (1) ( * , a , b )(2) ( / , c , d )(3) ( + , (1), (2)(4) ( := , * , (3)第二十三页，共三十三页。2 2、

22、转移语句转移语句(yj)(yj)和条件语句和条件语句(yj)(yj)的三元式的三元式 例例，条件条件(tiojin)(tiojin)语句语句 if xy then z := x else z := y+1 用三元用三元(sn yun)(sn yun)式表示式表示: :(1) ( , x , y )(2) (jez, (1), ) (jez为单目运算，等于为单目运算，等于0转转)(3) ( :=, z , x )(4) ( j , , ) (j为无条件转至为无条件转至(7)，单目运算，单目运算)(5) ( + , y , 1 )(6) ( :=, z , (5)(7) 真真假假(2) (jez,

23、 (1), (5) (jez为单目运算，等于为单目运算，等于0转转)(4) ( j , (7), ) (j为无条件转至为无条件转至(7)，单目运算，单目运算)第二十四页，共三十三页。例例，程序段，程序段:begink := 100；10: if k i+j thenbegink := k 1；goto 10endelse k := i * i j * j；i := 0；j := 0；end用三元用三元(sn yun)(sn yun)式表示式表示: : (1) ( block, , ) (2) ( := , k , 100 )(3) ( + , i , j )(4) ( , k , (3) )(

24、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、循环、循环(xnhun)(xnhun)语句的三元式语句的三元式 例例，循环循环(xnhun)(xnhun

25、)语句语句: : for i := 1 to 100 do s := s + i 首先将其展开为首先将其展开为: : i:=1；10: if i=100 then begins:=s+i；i:=i+1；goto 10 end再转化成三元再转化成三元(sn yun)(sn yun)式式: : (1) ( := , i , 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

26、 , (2), (9) )第二十六页，共三十三页。4 4. 三元式的语法制导三元式的语法制导(zhdo)(zhdo)翻译翻译 产生产生(chnshng)(chnshng)式式 语义动作语义动作 (1) E E(1) op E(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) E i E.VAL = ENTRY(i) E.VAL指示器，指向有关指示器，指向有关(yugun)(yugun)符号表的某一项或

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

28、用来表示来表示(biosh)中间代码。这种树中，中间代码。这种树中，非叶结点非叶结点和和叶结点叶结点(端末结端末结)分别代表分别代表运算符运算符和和运算量运算量。 如右图如右图: : e1、e2为表达式，为表达式，T1表示表示(biosh)为为e1的树，的树，T2表示表示为为e2的树，则的树，则T1+T2表示表示 e1+e2的树的树T1 T2+e1+e2T1*T2表示表示 e1*e2的树的树T1 T2*e1*e2- -T1表示表示 - -e1的树的树T1 - -e1第二十八页，共三十三页。双目运算对应二叉子双目运算对应二叉子(ch zi)(ch zi)树，多目运算对应多叉子树，多目运算对应多叉

29、子(ch zi)(ch zi)树。多叉子树。多叉子(ch zi)(ch zi)树可以通过引进新结而表示成二叉子树可以通过引进新结而表示成二叉子(ch (ch zi)zi)树。树。 第二十九页，共三十三页。将一个将一个(y )(y )表达式翻译成树结构表示表达式翻译成树结构表示:产生产生(chnshng)(chnshng)式式语义动作语义动作 (1) E E(1) op E(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).

30、VAL ) (4) E i E.VAL = LEAF(i) E.VAL指示器，指向指示器，指向(zh xin)(zh xin)树的一个结。树的一个结。 NODE ( op , LEFT, RIGHT )函数过程，建立二叉树，回送的值函数过程，建立二叉树，回送的值是一个指示器，指向这新树根。是一个指示器，指向这新树根。 UNARY (OP, CHILD )与与NODE类似，只有一个枝。类似，只有一个枝。 LEAF(i)建立以建立以i.LEXVAL指示的结并回送此结的地址，此结为指示的结并回送此结的地址，此结为端末结。端末结。 第三十页，共三十三页。例例，A * B + C * D可表示可表示(b

31、iosh)(biosh)成成: : 输入输入(shr)(shr) 栈栈 树结构树结构 A * B + C * D* B + C * D i B + C * D E * + C * D E * i C * D E + * D E + i D E + E * B + C * D E A+ C * D E * EB* D E + E C E + E * i E + E * ED+ C * D E *(1)*(2)E + E+E第三十一页，共三十三页。表示成三元式表表示成三元式表: : OPARG1ARG2(1)*AB(2)*CD(3)+(1)(2)由此表可见，它与树结构表示相对应，每个三元由此表可见，它与树结构表示相对应，每个三元(sn yun)(sn yun)式对式对应一棵二叉树。应一棵二叉树。 第三十二页，共三十三页。内容(nirng)总结5.2 中间代码表示法。例， 。= 。= *。= *。= ab*+*cd*。= 。= 。= *。= a+*cd*第三十三页，共三十三页。