Microsoft PowerPoint - ch6 [Compatibility Mode]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ch6 [Compatibility Mode]"

轸郝
5 years ago
Views:

1 第 6 章中间代码生成记号流分析器本章内容静态检查器中间代码生成器中间代码代码生成器介绍几种常用的中间表示 : 后缀表示图形表示和三地址代码用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式后缀表示表达式 E 的后缀表示可以如下归纳定义如果 E 是变量或常数, 那么 E 的后缀表示就是 E 本身如果 E 是形式为 E 1 ope 2 的表达式, 那么 E 的后缀表示是 E 1 E 2 op, 其中 E 1 和 E 2 分别是 E 1 和 E 2 的后缀表示如果 E 是形式为 (E 1 ) 的表达式, 那么 E 1 的后缀表示也是 E 的后缀表示后缀表示不需要括号 (8 5) + 2 的后缀表示是后缀表示的最大优点是便于计算机处理表达式计算栈输入串后缀表示不需要括号 (8 5) + 2 的后缀表示是后缀表示的最大优点是便于计算机处理表达式后缀表示很容易拓广到含一元算符的表达式后缀表示也可以拓广到表示赋值语句和控制语句, 但很难用栈来描述它的计算图形表示语法树是一种图形化的中间表示有向无环图 (DAG) 也是一种中间表示 assign a + assign a uminus uminus c d c d c d b b (a) 语法树 (b) DAG a = ( b + c d) + c d 的图形表示构造赋值语句语法树的翻译方案修改构造结点的函数可生成有向无环图产生式语义动作 S id =E E E 1 +E 2 E E 1 E 2 E E 1 E (E 1 ) E id {S.nptr = mknode( assign, mkleaf (id, id.entry), E.nptr);} {E.nptr = mknode( +, E 1.nptr, E 2.nptr);} {E.nptr = mknode(, E 1.nptr, E 2.nptr);} {E.nptr = mkunode( uminus, E 1.nptr);} {E.nptr = E 1.nptr;} {E.nptr = mkleaf (id, id.entry);} 1

2 6.1.3 三地址代码一般形式 :x = y op z 例表达式 x + y z 翻译成的三地址语句序列是 = y z t 2 = x + 三地址代码是语法树或 DAG 的一种线性表示例 a=( b+c d )+c d 语法树 = b t 2 = c d t 3 = + t 2 t 4 = c d uminus t 5 = t 3 + t 4 a = t 5 三地址代码是语法树或 DAG 的一种线性表示例 a=( b+c d )+c d 语法树 DAG = b = b assign t 2 = c d t 2 = c d a + t 3 = + t 2 t 3 = + t 2 + t 4 = c d t 4 = t 3 + t 2 uminus t 5 = t 3 + t 4 a = t c d 4 b a = t 5 本书常用的三地址语句赋值语句 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 = y[i] 和 x[i] = y 地址和指针赋值 x = &y,x = y 和 x = y 静态单赋值形式 (SSA) 一种便于某些代码优化的中间表示和三地址代码的主要区别所有赋值指令都是对不同名字的变量进行赋值三地址代码静态单赋值形式 p = a +b p 1 = a +b q = p c q 1 = p 1 c p = q d p 2 = q 1 d p = e p p 3 = e p 2 q = p + q q 2 = p 3 + q 静态单赋值形式 (SSA) 一种便于某些代码优化的中间表示和三地址代码的主要区别所有赋值指令都是对不同名字的变量进行赋值一个变量在不同路径上都被定值的解决办法 if (flag) x = 1; else x = 1; y = x a; 的条件语句改成 if (flag) x 1 = 1; else x 2 = 1; x 3 = (x 1, x 2 ); // 由 flag 的值决定用 x 1 还是 x 2 2

3 本节介绍为局部名字建立符号表条目为局部名字分配存储单元符号表中包含名字的类型和分配给它的存储单元的相对地址等信息过程中的声明计算被声明名字的类型和相对地址 P {offset =0} D; S D 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 T 1 {T.type = array (num.val, T 1.type); T.width = num.val T 1.width;} T T 1 {T.type = pointer (T 1.type); T.width =4;} 计算被声明名字的类型和相对地址 P {offset =0} D; S D 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 T 1 {T.type = array (num.val, T 1.type); T.width = num.val T 1.width;} T T 1 {T.type = pointer (T 1.type); T.width =4;} 作用域信息的保存所讨论语言的文法 P D; S D D ; D id : T proc id ; D ; S 语义动作用到的函数 mktable(previous) enter(table, name, type, offset) addwidth(table, width) enterproc(table, name, newtable) P MD; S {addwidth (top (tblstack), top (offsetstack)); M pop(tblstack); pop (offsetstack); } {t = mktable (nil); push(t, tblstack); push (0, offsetstack); } D D 1 ; D 2 D proc id ; ND 1 ; S {t = top(tblstack); addwidth(t, top(offsetstack)); pop(tblstack); pop(offsetstack); enterproc(top(tblstack), id.lexeme, t); } D id :T {enter(top(tblstack), id.lexeme, T.type, top(offsetstack)); top(offsetstack)=top(offsetstack)+t.width;} N {t = mktable(top(tblstack)); push(t, tblstack); push(0, offsetstack); } 3

4 P MD; S {addwidth (top (tblstack), top (offsetstack)); M pop(tblstack); pop (offsetstack); } {t = mktable (nil); push(t, tblstack); push (0, offsetstack); } D D 1 ; D 2 D proc id ; ND 1 ; S {t = top(tblstack); addwidth(t, top(offsetstack)); pop(tblstack); pop(offsetstack); enterproc(top(tblstack), id.lexeme, t); } D id :T {enter(top(tblstack), id.lexeme, T.type, top(offsetstack)); top(offsetstack)=top(offsetstack)+t.width;} N {t = mktable(top(tblstack)); push(t, tblstack); push(0, offsetstack); } P MD; S {addwidth (top (tblstack), top (offsetstack)); M pop(tblstack); pop (offsetstack); } {t = mktable (nil); push(t, tblstack); push (0, offsetstack); } D D 1 ; D 2 D proc id ; ND 1 ; S {t = top(tblstack); addwidth(t, top(offsetstack)); pop(tblstack); pop(offsetstack); enterproc(top(tblstack), id.lexeme, t); } D id :T {enter(top(tblstack), id.lexeme, T.type, top(offsetstack)); top(offsetstack)=top(offsetstack)+t.width;} N {t = mktable(top(tblstack)); push(t, tblstack); push(0, offsetstack); } 符号表实例图 5.14 的 Pascal 程序 readarray 表头 i sort 空表头 a x readarray exchange quicksort exchange 表头指向 readarray 指向 exchange quicksort 表头 k v partition partition 记录的域名 T record D end 记录类型单独建符号表, 作为类型表达式的主要部分, 域的相对地址从 0 开始 T record LD end {T.type = record (top(tblstack)); T.width = top(offsetstack); pop(tblstack); pop(offsetstack); } L {t = mktable(nil); push(t, tblstack); push(0, offsetstack); } 符号表的中名字 S id := E { p = lookup(id.lexeme); if (p!= nil ) emit ( p, =,E.place); else error; } E E 1 + E 2 { E.place = newtemp(); emit (E.place, =,E 1.place, +,E 2.place); } 符号表的中名字 E E 1 { E.place = newtemp(); emit (E.place, =, uminus,e 1.place); } E (E 1 ){E.place = E 1.place;} E id { p = lookup(id.lexeme); if (p!= nil ) E.place = p;elseerror; } 4

5 6.3.2 数组元素的地址计算一维数组 A 的第 i 个元素的地址计算 base +(i low ) w 变换成 i w +(base low w) 减少了运行时的计算二维数组 A: array[1..2, 1..3] of T 列为主 A[1, 1], A[2, 1], A[1, 2], A[2, 2], A[1, 3], A[2, 3] 行为主 A[1, 1], A[1, 2], A[1, 3], A[2, 1], A[2, 2], A[2, 3] base +((i 1 low 1 ) n 2 +(i 2 low 2 )) w (A[i 1, i 2 ] 的地址, 其中 n 2 = high 2 low 2 +1) 变换成 ((i 1 n 2 )+i 2 ) w + (base ((low 1 n 2 )+low 2 ) w) 多维数组下标变量 A[i 1, i 2,, i k ] 的地址表达式 (( ((i 1 n 2 + i 2 ) n 3 + i 3 ) ) n k + i k ) w + base (( ((low 1 n 2 + low 2 ) n 3 + low 3 ) ) n k + low k ) w (( ((i 1 n 2 + i 2 ) n 3 + i 3 ) ) n k + i k ) w + invariant(a) 数组元素地址计算的翻译方案下标变量访问的产生式 L id [ Elist ] id Elist Elist, E E 不便于在处理下标表达式时到符号表取信息为便于写语义动作, 改成等价的 L Elist ] id Elist Elist, E id[e 所有产生式 S L := E E E + E E (E ) E L L Elist ] L id Elist Elist, E Elist id [ E L id {L.place =id.place; L.offset = null; } Elist id [ E {Elist.place = E.place; Elist.ndim =1; Elist.array =id.place;} Elist Elis, E { t = newtemp();m = Elis.ndim +1; emit (t, =,Elis.place,, limit(elis.array, m) ); emit (t, =,t, +,E.place); Elist.array = Elis.array; Elist.place = t; Elist.ndim = m;} L Elist ] { L.place = newtemp(); emit (L.place, =,invariant (Elist.array)); L.offset = newtemp(); emit (L.offset, =,Elist.place,,width(Elist.array));} 5

6 E L{if (L.offset == null) / L 是简单变量 / E.place = L.place ; else { E.place = newtemp(); emit (E.place, =,L.place, [, L.offset, ] ); }} E E 1 + E 2 {E.place = newtemp(); emit (E.place, =,E 1.place, +,E 2.place); } E (E 1 ){ E.place = E 1.place ;} S L := E {if(l.offset == null) / L 是简单变量 / emit (L.place, =,E.place) else emit (L.place, [, L.offset, ], =, E.place); } L.place =x L.offset = null x = y * 20 = + z Elist.place =y Elist.ndim =1 Elist.array =A A [ x = t 4 S := t 4 = t 2 [t 3 ] E.place =t 4 t 2 =c //c=a 84 L.place =t 2 t 3 = * 4 L.offset =t 3 Elist.place = Elist.ndim =2 Elist.array =A E.place =y L.place =y L.offset = null, y x := A[ y, z ] 的注释分析树 E.place =z L.place =z L.offset = null z ] 类型转换例 x=y+i j (x 和 y 的类型是 real,i 和 j 的类型是 integer) 中间代码 =iint*j t 2 = inttoreal t 3 = y real+ t 2 x=t 3 E E 1 + E 2 E.place = newtemp(); if (E 1.type == integer && E 2.type == integer ) { emit (E.place, =,E 1.place, int+, E 2.place); E.type = integer; } else if (E 1.type == integer && E 2.type == real ) { u = newtemp(); emit (u, =, inttoreal,e 1.place); emit (E.place, =,u, real+, E 2.place); E.type = real; } 布尔表达式布尔表达式有两个基本目的计算逻辑值在控制流语句中用作条件表达式本节所用的布尔表达式文法 B B or B B and B notb (B ) E relop E true false 布尔表达式布尔表达式的完全计算值的表示数值化其计算类似于算术表达式的计算布尔表达式的短路计算 B 1 or B 2 定义成 if B 1 then true else B 2 B 1 and B 2 定义成 if B 1 then B 2 else false 用控制流来实现计算, 即用程序中的位置来表示值, 因为布尔表达式通常用来决定控制流走向两种不同计算方式可能导致程序结果不一样 6

7 例语句 if or x > 200 and x!= y then x := 0 的短路计算代码如下 if goto L 2 iffalse x > 200 goto L 1 iffalse x!= y goto L 1 L 2 : x = 0 L 1 : 控制流语句的中间代码结构 S if B then S 1 if B then S 1 else S 2 while B do S 1 S 1 ; S 2 (a) if-then S.begin: goto S.begin (c) while-do goto S.next B.false: S 2.code (b) if-then-else S 1.next: S 2.code (d) S 1 ; S 2 if-then 若改成下面形式, 会产生连续的跳转 B.false: (a) if-then S.begin: goto S.begin (c) while-do goto S.next B.false: S 2.code (b) if-then-else S 1.next: S 2.code (d) S 1 ; S 2 设计翻译方案的困难 B.true, B.false, S.begin 和 S.next 都是继承属性由于究竟有多少条指令需等 B 翻译结束才能知道, 故在翻译 B 的过程中 (a) if-then 难以知道 B.true 在三地址指令序列中的准确位置对于 B.false 来说, 情况更严重, 图中没有给出该标号的定义采用增加标记非终结符使用全局变量和改写文法等方式都无法解决这种继承属性带来的困难解决办法回填技术 1 从概念上说把跳转到同一个标号的指令放到同一张指令表中等目的标号确定时再把目的 (a) if-then 标号填写到该表中的各条指令中 2 从写翻译方案的角度非终结符 B 的综合属性 truelist 和 falselist 用来管理布尔表达式的跳转代码等跳转的目的标号确定时通过过程调用来回填 7

8 6.4.3 布尔表达式的回填 B B 1 or MB 2 { backpatch(b 1.falselist, M.instr); B.falselist = B 2.falselist; B.truelist = merge(b1.truelist, B2.truelist);} B B 1 and MB 2 { backpatch(b 1.truelist, M.instr); B.truelist = B 2.truelist; B.falselist=merge(B 1.falselist, B 2.falselist); } B not B 1 { B.truelist = B 1.falselist; B.falselist = B 1.truelist;} B ( B 1 ) {B.truelist = B 1.truelist; B.falselist = B 1.falselist;} 布尔表达式的回填 B E 1 relop E 2 { B.truelist = makelist(nextinstr); B.falselist = makelist(nextinstr+1); emit( if, E 1.place, relop.op, E 2.place, goto _ ); emit( goto _ ); } B true { B.truelist = makelist(nextinstr); B.falselist = null; emit( goto _ ); } B false { B.falselist = makelist(nextinstr); B.truelist = null; emit( goto _ ); } M { M.instr = nextinstr;} x < 100 B.t = {102} and M.i = 104 B.f = {103} x > 200 x!= y B.t = {102} and M.i = : goto _ B.f = {103} x > 200 x!= y B.t = {102} and M.i = : goto _ B.f = {103} x > 200 x!= y B.t = {102} and M.i = : goto _ B.f = {103} x > : if x > 200 goto_ x!= y 103: goto _ 8

9 B.t = {102} and M.i = : goto _ B.f = {103} x > : if x > 200 goto_ x!= y 103: goto _ B.t = {102} and M.i = : goto _ B.f = {103} x > 200 x!= y 102: if x > 200 goto_ 104: if x!= y goto_ 103: goto _ 105: goto _ B.t = {102} and M.i = : goto _ B.f = {103} x > 200 x!= y 102: if x > 200 goto : if x!= y goto_ 103: goto _ 105: goto _ B.t = {102} and M.i = : goto 102 B.f = {103} x > 200 x!= y 102: if x > 200 goto : if x!= y goto_ 103: goto _ 105: goto _ 控制流语句的翻译 (a) if-then S if B then MS 1 { backpatch(b.truelist, M.instr); S.nextlist = merge(b.falselist, S 1.nextlist); } M { M.instr = nextinstr;} 控制流语句的翻译 goto S.next B.false: S 2.code (b) if-then-else S if B then M 1 S 1 N else M 2 S 2 { backpatch(b.truelist, M 1.instr); backpatch(b.falselist, M 2.instr); S.nextlist = merge(merge(s 1.nextlist, N.nextlist), S 2.nextlist); } M { M.instr = nextinstr;} N { N.nextlist=makeList(nextinstr); emit( goto_ );} 9

10 6.4.4 控制流语句的翻译 S.begin: goto S.begin (c) while-do S while M 1 B do M 2 S 1 { backpatch(s 1.nextlist, M 1.instr); backpatch(b.truelist, M 2.instr); S.nextlist = B.falselist; emit( goto, M 1.instr);} M { M.instr = nextinstr;} 控制流语句的翻译 S 1.next: S S 1 ; MS 2 { backpatch(s 1.nextlist, M.instr); S.nextlist = S 2.nextlist;} M { M.instr = nextinstr;} S 2.code (d) S 1 ; S 开关语句的翻译 switch E begin case V 1 : S 1 case V 2 : S 2 case V n -1 : S n 1 default: S n end 分支数较少时 t=e L n-2 :ift!=v n-1 goto L n-1 ift!=v 1 goto L 1 S n -1 S 1 goto next goto next L n-1 : S n L 1 : ift!=v 2 goto L 2 next: S 2 goto next L 2 : 分支较多时, 将分支测试代码集中在一起, 便于生成较好的分支测试代码 t=e L n : S n goto test goto next L 1 : S 1 test: ift==v 1 goto L 1 goto next if t == V 2 goto L 2 L 2 : S 2 goto next if t == V n-1 goto L n-1 gotol n L n-1 : S n -1 next: goto next 中间代码增加一种 case 语句, 便于代码生成器对它进行特别处理 test: case V 1 L 1 case V 2 L 2 case V n-1 L n-1 case t L n next: 10

11 6.4.6 过程调用的翻译 S call id (Elist) Elist Elist, E Elist E 过程调用 id(e 1, E 2,,E n ) 的中间代码结构 E 1.place = E 1 E 2.place = E 2 E n.place = E n param E 1.place param E 2.place param E n.place call id.place, n S call id (Elist) { 为长度为 n 的队列中的每个 E.place, 执行 emit( param, E.place); emit( call, id.plase, n); } Elist Elist, E { 把 E.place 放入队列末尾 } Elist E { 将队列初始化, 并让它仅含 E.place} 本章要点中间代码的几种形式, 它们之间的相互转换符号表的组织和作用域信息的保存数组元素定址的翻译方案, 布尔表达式的两种不同实现方式赋值语句和各种控制流语句的中间代码格式和生成中间代码的翻译方案过程调用的中间代码格式和生成中间代码的翻译方案例题 1 Pascal 语言的标准将 for 语句 for v := initial to final do stmt 定义成和下面序列有同样的含义 : begin := initial; t 2 := final; if <= t 2 then begin v:= ; stmt; while v <> t 2 do begin v := succ(v); stmt end end end 例题 1 Pascal 语言的标准将 for 语句 for v := initial to final do stmt 能否定义成和下面序列有同样的含义? begin := initial; t 2 := final; v:= ; while v <= t 2 do begin stmt; v := succ(v) end end 11

12 例题 1 Pascal 语言 for 语句 for v := initial to final do stmt 的中间代码结构如下 : =initial t 2 =final if >t 2 goto L1 v= L2: stmt if v == t 2 goto L1 v=v+1 goto L2 L1: 例题 2 C 语言的 for 语句有下列形式 for (e 1 ;e 2 ;e 3 ) stmt 它和 e 1 ; while (e 2 ){ stmt; e 3 ; } 有同样的语义例题 2 C 语言的 for 语句 for (e 1 ;e 2 ;e 3 ) stmt 的中间代码结构如下 e 1 L1: e 2 L2: e 3 goto L1 stmt goto L2 假转, 由外层语句决定真转例题 3 Pascal 语言 var a,b : array[1..100] of integer; a:=b -- 允许数组之间赋值若 a 和 b 是同一类型的记录, 也允许赋值 C 语言数组类型不行, 结构体类型可以为这种赋值选用或设计一种三地址语句, 它要便于生成目标代码例题 3 Pascal 语言 var a,b : array[1..100] of integer; a:=b -- 允许数组之间赋值若 a 和 b 是同一类型的记录, 也允许赋值仍然用中间代码复写语句 x=y, 在生成目标代码时, 必须根据它们类型对应的 size, 产生一连串的值传送指令习第一次 :6.1 第二次 :6.4, 6.9, 6.10 题 12

Microsoft PowerPoint - ch7 [Compatibility Mode]

Microsoft PowerPoint - ch7 [Compatibility Mode] 记号流第七章分析器静态检查器中间代码生成中间代码生成器中间代码代码生成器本章内容介绍几种常用的中间表示 (intermediate representation): 后缀表示图形表示和三地址代码用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式 7.1.1 后缀表示 E E ope uope (E) id num 表达式 E 的后缀表示可以如下归纳定义 : 表达式