编译原理与技术PPT课件

1、第第7 7章章 中间代码生成中间代码生成编译原理与技术编译原理与技术 介绍几种常用的中间表示： 后缀表示、图形表示和三地址代码 用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式 7 7 中间代码生成中间代码生成内容提要内容提要分析器静态检查器中间代码生成器中间代码记号流代码生成器7.1 7.1 中间语言中间语言第第7 7章章 中间代码生成中间代码生成7.1.1 后缀表示 E E op E | uop E | (E) | id | num表达式E的后缀表示可以如下归纳定义：表达式E后缀式EididnumnumE1 op E2E1 E2 opuop EE uop(E)E7.1 7

2、.1 中间语言中间语言 后缀表示不需要括号(8 - 5) + 2 的后缀表示是8 5 - 2 + 后缀表示的最大优点是便于计算机处理表达式计算栈输入串8 5 - 2 +85 - 2 +8 5- 2 +32 +3 2+5 后缀表示也可以拓广到表示赋值语句和控制语句，但很难用栈来描述控制语句的计算7.1 7.1 中间语言中间语言7.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图也是一种中间表示7.1 7.1 中间语言中间语言assigna+bcduminus(b) DAGDirected Acyclical Graphsassigna+bcdcduminus(a) 语法树 a = (

3、- b + c d ) + c d 的图形表示构造赋值语句语法树的语法制导定义修改构造结点的函数可生成有向无环图7.1 7.1 中间语言中间语言产 生 式 语 义 规 则S id = E S.nptr = mkNode( assign, mkLeaf (id, id.entry), E.nptr) E E1 + E2 E.nptr = mkNode( +, E1.nptr, E2.nptr) E E1 E2E.nptr = mkNode( , E1.nptr, E2.nptr) E - E1E.nptr = mkUNode( uminus, E1.nptr) E (E1) E.nptr = E

4、1.nptr F id E.nptr = mkLeaf (id, id.entry) 7.1.3 三地址代码一般形式：x = y op z 例 表达式x + y z翻译成的三地址语句序列是t1 = y z t2 = x + t1 7.1 7.1 中间语言中间语言 三地址代码是语法树或DAG的一种线性表示 例a = ( - b + c d ) + c d语法树的代码t1 = - bt2 = c dt3 = t1 + t2t4 = c dt5 = t3 + t4a = t57.1 7.1 中间语言中间语言assigna+bcdcduminusDAG的代码t1 = - bt2 = c dt3 = t

5、1 + t2t4 = t3 + t2a = t4assigna+bcduminus本书常用的三地址语句 赋值语句 x = y op z， x = op y， x = y 无条件转移 goto L 条件转移 if x relop y goto L 过程调用 param x 和 call p , n 过程返回 return y 索引赋值 x = yi 和 xi = y 地址和指针赋值 x = &y，x = y 和 x = y7.1 7.1 中间语言中间语言7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值三地址代码静态

6、单赋值形式p = a +bp1 = a +b q = p - cq1 = p1 - c p = q dp2 = q1 d p = e - pp3 = e - p2 q = p + q q2 = p3 + q17.1 7.1 中间语言中间语言 一个变量在不同路径上都定值的解决办法if (flag) x = 1; else x = 1;y = x a;改成if (flag) x1 = 1; else x2 = 1;x3 = (x1, x2);/由flag的值决定用x1还是x2y = x x3;7.1 7.1 中间语言中间语言7.2 7.2 声明语句声明语句第第7 7章章 中间代码生成中间代码生成本

7、节介绍 为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息7.2 7.2 声明声明语句语句7.2.1 过程中的声明计算被声明名字的类型和相对地址P offset = 0 D; SD D ; D D id : T enter ( id.lexeme, T.type, offset);offset = offset + T.width T integer T.type = integer; T.width = 4 T real T.type = real; T.width = 8 T array num of T1T.type = array (

8、num.val, T1.type);T.width = num.val T1.widthT T1 T.type = pointer (T1.type); T.width = 4 7.2 7.2 声明声明语句语句7.2.2 作用域信息的保存 所讨论语言的文法P D; SD D ; D | id : T | proc id ; D ; S 7.2 7.2 声明声明语句语句sort var a:; x:; readarray var i:; exchange quicksort var k, v:; partition var i, j:;图6.14的程序参数被略去7.2 7.2 声明声明语句语句e

9、xchangereadarrayxa表 头空sortquicksort指向readarraypartitionvk表 头quicksortreadarrayi表 头exchange表 头指向exchangepartitionsort readarray exchange quicksort partition 符号表的特点 各过程有各自的符号表 符号表之间有双向链 构造符号表时需要符号表栈 构造符号表需要偏移记录栈 语义动作用到的函数mkTable(previous) /创立新表enter(table, name, type, offset) /增加新的id条目addWidth(table,

10、width) /将表大小写入表中enterProc(table, name, newtable) /添加新的表条目7.2 7.2 声明声明语句语句P M D ; S addWidth (top (tblptr), top (offset); pop(tblptr); pop (offset) M t = mkTable (nil);push(t, tblprt); push (0, offset) D D1 ; D2D proc id ; N D1; S t = top(tblptr);addWidth(t, top(offset) ); pop(tblptr); pop(offset);en

11、terProc(top(tblptr), id.lexeme, t) D id : T enter(top(tblptr), id.lexeme, T.type, top(offset);top(offset) = top(offset) + T.width N t = mkTable(top(tblptr) );push(t, tblptr); push(0, offset) 7.2 7.2 声明声明语句语句7.2.3 记录的域名T record D end记录类型单独建符号表，作为类型表达式的主要部分，域的相对地址从0开始T record L D endT.type = record (t

12、op(tblptr) ); T.width = top(offset); pop(tblptr); pop(offset) L t = mkTable(nil); push(t, tblprt); push(0, offset) 7.2 7.2 声明声明语句语句record a : ; r : record i : ; . . . end; k : ;end7.3 7.3 赋值语句赋值语句第第7 7章章 中间代码生成中间代码生成7.3.1 符号表中的名字S id := E p = lookup(id.lexeme);if p != nil thenemit ( p, = , E.place)e

13、lse error E E1 + E2 E.place = newTemp();emit (E.place, = , E1.place, + , E2.place) E - E1 E.place = newTemp();emit (E.place, = , uminus , E1.place) E (E1) E.place = E1.place E id p = lookup(id.lexeme);if p != nil then E.place = p else error 7.3 7.3 赋值语句赋值语句7.3.2 数组元素的地址计算一维数组A的第i个元素的地址计算base + ( i -

14、 low ) w 变换成i w + (base - low w)减少了运行时的计算7.3 7.3 赋值语句赋值语句二维数组A: array1.2, 1.3 of T 列为主A1, 1, A2, 1, A1, 2, A2, 2, A1, 3, A2, 3 行为主A1, 1, A1, 2, A1, 3, A2, 1, A2, 2, A2, 3Ai1, i2的地址：base + (i1-low1)n2 + (i2-low2 )w (其中n2=high2-low2+1)变换成 (i1n2 )+i2)w + base-(low1n2)+low2)w7.3 7.3 赋值语句赋值语句A1, 1 A1, 2

15、A1, 3A2, 1 A2, 2 A2, 3i1i2A1, 1 A1, 2 A2, 1 A2, 2 多维数组下标变量Ai1, i2, ., ik的地址表达式( ( ( (i1n2+i2)n3+i3) )nk+ik)w + base(low1n2+low2)n3+low3) )nk+lowk)w7.3 7.3 赋值语句赋值语句7.3.3 数组元素地址计算的翻译方案 下标变量访问的产生式L id Elist | idElist Elist, E | E不便于在处理下标表达式时到符号表取信息 为便于写语义动作，改成等价的L Elist | idElist Elist, E | id E7.3 7.3

16、 赋值语句赋值语句 所有产生式S L := EE E + EE (E )E LL Elist L idElist Elist, EElist id E7.3 7.3 赋值语句赋值语句L id L.place = id.place; L.offset = null; Elist id E Elist.place = E.place; Elist.ndim = 1;Elist.array = id.place; Elist Elist1, E t = newTemp(); m = Elist1.ndim + 1;emit (t, =, Elist1.place, , limit(Elist1.ar

17、ray, m); );emit (t, =, t, +, E.place); Elist.array = Elist1.array;Elist.place = t; Elist.ndim = m; L Elist L.place = newTemp();emit (L.place, =, base(Elist.array), -, invariant(Elist.array);L.offset = newTemp();emit (L.offset, =, Elist.place, , width(Elist.array); 7.3 7.3 赋值语句赋值语句E L if L.offset = n

18、ull then / L是简单变量 /E.place = L.place;else E.place = newTemp();emit (E.place, =, L.place, , L.offset, ); E E1 + E2 E.place = newTemp();emit (E.place, =, E1.place , +, E2.place); E ( E1 ) E.place = E1.place; S L := E if L.offset = null then / L是简单变量 /emit (L.place, =, E.place);else emit (L.place , , L

19、.offset, , =, E.place); 7.3 7.3 赋值语句赋值语句7.3 7.3 赋值语句赋值语句S:=L.place = xL.offset = nullxE.place = t4L.place = t2L.offset = t3Elist.place = t1Elist.ndim = 2Elist.array = A,Elist.place = yElist.ndim = 1Elist.array = AE.place = zL.place = zL.offset = nullE.place = yL.place = yL.offset = nullAzy x := A y,

20、 z 的注释分析树t1 = y 20 t1 = t1 + z t2 = c t3 = t1 4t4 = t2 t3 x = t4 注：c =A 84 A10, 20考虑C语言中数组double a1020，写出计算aij、ai+1和a+i的三地址中间代码 a: pointer(array(20,double) ai: pointer(double) aij: double7.3 7.3 赋值语句赋值语句例题例题aij: t1=i*20 t2=t1+j t3=t2*8 t4=at3ai+1: t1=i*20 t2=t1*8 t3=a+t2 t4=1*8 t5=t3+t4a+i: t1=a t2=

21、20*8 t3=t2*i t4=t1+t37.3.4 类型转换 例x = y + i j（x和y的类型是real，i和j的类型是integer）中间代码t1 = i int jt2 = inttoreal t1 t3 = y real+ t2 x = t37.3 7.3 赋值语句赋值语句E E1 + E2 E.place = newTemp();if E1.type = integer & E2.type = integer then emit (E.place, =, E1.place, int+, E2.place);E.type = integer; elseif E1.type

22、 = integer & E2.type = real then u = newTemp();emit (u, =, inttoreal, E1.place);emit (E.place, =, u, real+, E2.place);E.type = real; . . .7.3 7.3 赋值语句赋值语句7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句第第7 7章章 中间代码生成中间代码生成7.4.1 布尔表达式 布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式 本节所用的布尔表达式文法B B or B | B and B | not B | ( B )

23、| E relop E | true | false7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句 布尔表达式的完全计算 值的表示数值化 其计算类似于算术表达式的计算 布尔表达式的“短路”计算 B1 or B2定义成if B1 then true else B2 B1 and B2定义成if B1 then B2 else false 用控制流来实现计算，即用程序中的位置来表示值，因为布尔表达式通常用来决定控制流走向 两种不同计算方式会导致程序的结果不一样7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句7.4.2 控制流语句的翻译S if B then S1| if

24、B then S1 else S2| while B do S1| S1; S2 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句B.codeS1.codeB.true:. . .指向B.true指向B.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

25、:(c) while-doS1.codeS2.codeS1.next:. . .(d) S1; S2B.false:如果给如果给If-then添加添加false标号，当它嵌入其它语句时，标号，当它嵌入其它语句时，可能会可能会产生冗余跳转指令产生冗余跳转指令S if B then S1 B.true = newLabel(); B.false = S.next; S1.next = S.next; S.code = B.code | gen(B.true, :) | S1.code 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句B.codeS1.codeB.true:. . .指向

26、B.true指向B.false(a) if-thenS if B then S1 else S2 B.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 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句B.codeS1.codeB.true:. . .指向B.true指向B.falseB.false: g

27、oto S.nextS2.code(b) if-then-elseS 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) 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句B.codeS1.codeB.true:. . .指向B.true指向B.falsegoto S.beginS.begi

28、n:(c) while-doS S1; S2 S1.next = newLabel(); S2.next = S.next; S.code = S1.code | gen(S1.next, :) | S2.code 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句S1.codeS2.codeS1.next:. . .(d) S1; S27.4.3 布尔表达式的控制流翻译如果B是 a b 的形式，那么代码是：if a b goto B.truegoto B.false 例 表达式 a b or c d and e f 的代码是：if a b goto Ltruegoto L1L1:i

29、f c d goto L2goto LfalseL2:if e f goto Ltruegoto Lfalse7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句B B1 or B2 B1.true = B.true; B1.false = newLabel(); B2.true = B.true; B2.false = B.false; B.code = B1.code | gen(B1.false, :) | B2.code B not B1 B1.true = B.false; B1.false = B.true; B.code = B1.code 7.4 7.4 布尔表达式布尔

30、表达式和控制流语句和控制流语句B B1 and B2 B1.true = newLabel(); B1.false = B.false; B2.true = B.true; 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 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句B E1 relop E2 B.code = E1.code | E2.code |gen(if, E1.pla

31、ce, relop.op, E2.place, goto, B.true) |gen(goto, B.false) B true B.code = gen(goto, B.true)B false B.code = gen(goto, B.false)7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句7.4.4 开关语句的翻译switch Ebegincase V1: S1case V2: S2. . .case Vn-1: Sn-1default: Snend7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句 分支数较少时t = E的代码| Ln-2:if t != Vn

32、-1 goto Ln-1if t != V1 goto L1|Sn -1的代码S1的代码|goto nextgoto next| Ln-1:Sn的代码L1:if t != V2 goto L2| next:S2的代码|goto next|L2:. . .|. . . |7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句 分支较多时，将分支测试代码集中在一起，便于生成较好的分支测试代码t = E的代码| Ln:Sn的代码goto test|goto nextL1:S1的代码| test:if t = V1 goto L1goto next|if t = V2 goto L2L2:S2的

33、代码|. . .goto next|if t = Vn-1 goto Ln-1. . .|goto LnLn-1: Sn -1的代码| next:goto next|7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句 中间代码增加一种case语句，便于代码生成器对它进行特别处理 test: case V1L1case V2L2. . .case Vn-1Ln-1case tLn next: 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句一个生成： 用二分查找确定该执行的分支 直接找到该执行的分支的例子见第8章习题7.4.5 过程调用的翻译S call id (Elist

34、)Elist Elist, EElist E 过程调用id(E1, E2, , En)的中间代码结构E1.place = E1的代码E2.place = E2的代码. . .En.place = En的代码param E1.placeparam E2.place. . .param En.placecall id.place, n7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句S call id (Elist) 为长度为n的队列中的每个E.place， emit(param, E.place); emit(call, id.plase, n) Elist Elist, E 把E.p

35、lace放入队列末尾 Elist E 将队列初始化，并让它仅含E.place 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句Pascal语言的标准将for语句for v := initial to final do stmt定义成和下面的代码序列有同样的含义：begint1 := initial; t2 := final;if t1= t2 then beginv := t1; stmt;while v t2 do beginv := succ(v); stmtendendend7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句例题例题1 1for v := initial to final do stmt能否定义成和下面的代码序列有同样的含义？begint1 := initial; t2 := final;v := t1;while v t2 goto L1v = t1L2:stmtif v = t2 goto L1v = v + 1goto L2L1: 7.4 7.4 布尔表达式布尔表达式和控制流语句和控制流语句例题例题1 1C语言的for语句有下列形式for ( e1 ; e2 ; e3 ) stmt它和e1;while ( e2 ) do beginstmt;