Microsoft PowerPoint - ch7 [Compatibility Mode]

记号流 第七章 分析器 静态检查器 中间代码生成 中间代码生成器 中间代码 代码生成器 本章内容 介绍几种常用的中间表示 (intermediate representation): 后缀表示 图形表示和三地址代码 用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式 7.1.1 后缀表示 E E ope uope (E) id num 表达式 E 的后缀表示可以如下归纳定义 : 表达式 E 后缀式 E id num E 1 ope 2 uope (E) id num E 1 E 2 op E uop E 后缀表示不需要括号 (8 5) + 2 的后缀表示是 8 5 2 + 后缀表示的最大优点是便于计算机处理表达 式 计算栈输入串 8 5 2 + 8 5 2 + 8 5 2 + 3 2 + 3 2 + 5 后缀表示不需要括号 (8 5) + 2 的后缀表示是 8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 后缀表示也可以拓广到表示赋值语句和控制语句, 但很难用栈来描述控制语句的计算 7.1.2 图形表示 语法树是一种图形化的中间表示 有向无环图也是一种中间表示 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 S.nptr = mknode( assign, mkleaf (id, id.entry), E.nptr) E E 1 +E 2 E.nptr = mknode( +, E 1.nptr, E 2.nptr) E E 1 E 2 E.nptr = mknode(, E 1.nptr, E 2.nptr) E E 1 E.nptr = mkunode( uminus, E 1.nptr) E (E 1 ) E.nptr = E 1.nptr F id E.nptr = mkleaf (id, id.entry) 1

7.1.3 三地址代码 (three-address code) 一般形式 :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 7.1.4 静态单赋值形式 (static single-assignment form) 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值三地址代码静态单赋值形式 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 1 7.1.4 静态单赋值形式 一种便于某些代码优化的中间表示 和三地址代码的主要区别 所有赋值指令都是对不同名字的变量的赋值 一个变量在不同路径上都定值的解决办法 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

本节介绍 为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息 7.2.1 过程中的声明 计算被声明名字的类型和相对地址 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} 7.2.2 作用域信息的保存 所讨论语言的文法 P D; S D D ; D id : T proc id ; D ; S sort var a: ; x: ; readarray var i: ; exchange quicksort var k, v: ; partition var i, j: ; 图 6.14 的程序参数被略去 sort readarray exchange quicksort partition readarray 表头 i sort 空表头 a x readarray exchange quicksort exchange 表头 符号表实例 指向 readarray 指向 exchange quicksort 表头 k v partition partition 3

符号表的特点 各过程有各自的符号表 符号表之间有双向链 构造符号表时需要符号表栈 构造符号表需要活动记录栈 语义动作用到的函数 mktable(previous) enter(table, name, type, offset) addwidth(table, width) enterproc(table, name, newtable) sort var a: ; x: ; readarray var i: ; exchange quicksort var k, v: ; partition var i, j: ; 图 6.14 的程序参数被略去 P MD; S {addwidth (top (tblptr), top (offset)); pop(tblptr); pop (offset) } M {t = mktable (nil); push(t, tblptr); push (0, offset)} D D 1 ; D 2 D proc id ; ND 1 ; S {t = top(tblptr); addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(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) } P MD; S {addwidth (top (tblptr), top (offset)); pop(tblptr); pop (offset) } M {t = mktable (nil); push(t, tblptr); push (0, offset)} D D 1 ; D 2 D proc id ; ND 1 ; S {t = top(tblptr); addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(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) } P MD; S {addwidth (top (tblptr), top (offset)); pop(tblptr); pop (offset) } M {t = mktable (nil); push(t, tblptr); push (0, offset)} D D 1 ; D 2 D proc id ; ND 1 ; S {t = top(tblptr); addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(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.3 记录的域名 T record D 记录类型单独建符号表, 作为类型表达式的 主要部分, 域的相对地址从 0 开始 T record LD {T.type = record (top(tblptr)); T.width = top(offset); pop(tblptr); pop(offset)} L {t = mktable(nil); push(t, tblptr);push(0,offset)} record a : ; r : record i : ;... ; k : ; 7.3.1 符号表中的名字 S id := E {p = lookup(id.lexeme); if p!= nil then emit ( p, =,E.place) else error } E E 1 + E 2 {E.place = newtemp(); emit (E.place, =,E 1.place, +,E 2.place)} 4

7.3.1 符号表中的名字 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 then E.place = p else error } 7.3.2 数组元素的地址计算一维数组 A 的第 i 个元素的地址计算 base +(i low ) w 变换成 i w +(base low w) 减少了运行时的计算 二维数组 A[1,1] A[1,2] A[1,3] A: array[1..2, 1..3] of T A[2,1] A[2,2] A[2,3] 列为主 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] 二维数组 A[1,1] A[1,2] A: array[1..2, 1..3] of T A[2,1] A[2,2] 列为主 i 1 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) i 2 多维数组下标变量 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 7.3.3 数组元素地址计算的翻译方案 下标变量访问的产生式 L id [ Elist ] id Elist Elist, E E 不便于在处理下标表达式时到符号表取信息 为便于写语义动作, 改成等价的 L Elist ] id Elist Elist, E id[e 5

所有产生式 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, =,base(elist.array),, invariant (Elist.array)); L.offset = newtemp(); emit (L.offset, =,Elist.place,,width(Elist.array))} E L{if L.offset == null then / L 是简单变量 / E.place = L.place else begin 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 then / 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 [ A[10, 20] x = t 4 S := t 4 = t 2 [t 3 ] E.place =t 4 t 2 = c t 3 = 4 L.place =t 2 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 ] 的注释分析树 注 :c =A 84 E.place =z L.place =z L.offset = null z ] 7.3.4 类型转换 例 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 then begin emit (E.place, =,E 1.place, int+, E 2.place); E.type = integer else if E 1.type == integer && E 2.type == real then begin u = newtemp(); emit (u, =, inttoreal,e 1.place); emit (E.place, =,u, real+, E 2.place); E.type = real 6

7.4.1 布尔表达式 布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式 本节所用的布尔表达式文法 B B or B B and B notb (B ) E relop E true false 7.4.1 布尔表达式 布尔表达式的完全计算 值的表示数值化 其计算类似于算术表达式的计算 布尔表达式的 短路 计算 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 用控制流来实现计算, 即用程序中的位置来表示值, 因为布尔表达式通常用来决定控制流走向 两种不同计算方式会导致程序的结果不一样 7.4.2 控制流语句的翻译 S if B then S 1 if B then S 1 else S 2 while B do S 1 S 1 ; S 2 B.true, B.false, S.begin, S.next 继承属性 为便于翻译, 给指令加标号, 可通过调用 newlabel() 产生新标号 (a) if-then S.begin: goto S.begin (c) while-do goto S.next B.false: (b) if-then-else S 1.next: (d) S 1 ; S 2 (b) 中若 后用 goto S 1.next, S 1.next 为指令 goto S.next, 则 产生冗余跳转指令 B.false: goto S.next B.false: (a) if-then S.begin: (b) if-then-else S 1.next: (c) while-do goto S.begin (d) S 1 ; S 2 S if { B.true = newlabel(); B.false = S.next;} B then {S 1.next = S.next;} (a) if-then S 1 {S.code = gen(b.true, : ) S 1 7

能否仅使用综合属性? 解决办法 回填技术 1 从概念上说 把跳转到同一个标号的指令放到同一张指令表中 等目的标号确定时再把目的 (a) if-then 标号填写到该表中的各条指令中 2 从写翻译方案的角度 非终结符 B 的综合属性 truelist 和 falselist 用来管理布尔表达式的跳转代码 等跳转的目的标号确定时通过过程调用来回填 S if { B.true = newlabel(); B.false = S.next;} B then {S 1.next = S.next;} (a) if-then S 1 {S.code = gen(b.true, : ) S 1 S if B then MS 1 { backpatch(b.truelist, M.instr); // 回填 S.nextlist = merge(b.falselist, S 1.nextlist); } M { M.instr = nextinstr;} S if {B.true = newlabel(); B.false = newlabel();} B then { S 1.next = S.next;} goto S.next B.false: (b) if-then-else S 1 else { S 2.next = S.next;}S 2 { S.code = gen(b.true, : ) S 1.code gen( goto, S.next) gen(b.false, : ) S 2.code} 采用回填的翻译方案 goto S.next B.false: (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_ );} S {S.begin = newlabel(); } while { B.true = newlabel(); B.false = S.next;} B do { S 1.next = S.begin;}S 1 S.begin: goto S.begin (c) while-do { S.code = gen(s.begin, : ) gen(b.true, : ) S 1.code gen( goto, S.begin)} 采用回填的翻译方案 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;} 8

S {S 1.next = newlabel(); } S 1 ; { S 2.next = S.next;}S 2 { S.code = S 1.code gen(s 1.next, : ) S 2 S 采用回填的翻译方案 1.next: S S 1 ; MS 2 { backpatch(s 1.nextlist, M.instr); S.nextlist = S 2.nextlist;} M { M.instr = nextinstr;} (d) S 1 ; S 2 7.4.3 布尔表达式的控制流翻译 如果 B 是 a < b 的形式, 那么代码是 : if a < b goto B.true goto B.false 例表达式 a < b or c < d and e < f 是 : if a < b goto L true goto L 1 L 1 : if c < d goto L 2 goto L false L 2 : if e < f goto L true goto L false B { B 1.true = B.true; B 1.false = newlabel(); } B 1 or {B 2.true = B.true; B 2.false = B.false;} B 2 { = B 1.code gen(b 1.false, : ) B 2 B { B 1.true = B.false; B 1.false = B.true;} not B 1 { = B 1 B { B 1.true = newlabel(); B 1.false = B.false;} B 1 and { B 2.true = B.true; B 2.false = B.false;}B 2 { = B 1.code gen(b 1.true, : ) B 2 B { B 1.true = B.true; B 1.false = B.false;} (B 1 ) { = B 1 B E 1 relop E 2 { = E 1.code E 2.code gen( if, E 1.place, relop.op, E 2.place, goto, B.true) gen( goto, B.false)} B true { = gen( goto, B.true)} B false { = gen( goto, B.false)} 9

布尔表达式的回填 B B 1 or MB 2 { backpatch(b 1.falselist, M.instr); B.falselist = B 2.falselist; B.truelist = merge(b1.truelist, B2.truelist);} M { M.instr = nextinstr;} 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 _ ); } 7.4.4 开关语句的翻译 switch E begin case V 1 : S 1 case V 2 : S 2 case V n -1 : S n 1 default: S n 分支数较少时 t=e L n-2 :ift!=v n-1 goto L n-1 if t!= V 1 goto L 1 S n -1 S 1 goto next goto next L n-1 : S n L 1 : if t!=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: if t == 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: 一个生成 ( 两种优化 ): 用二分查找确定该执行的分支 建立入口地址表, 直接找到该执行的分支的例子见第 244 页习题 8.8 10

7.4.5 过程调用的翻译 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.place, 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 例题 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) 11

例题 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) final 为最大整数时, succ(final) 会导致越界错误 例题 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 )do begin 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, 产生一连串的值传送指令 12

例题 4 下面的翻译方案使用了变量 offset, 请重写该翻译方案, 它完成同样的事情, 但只使用文法符号的属性, 而不使用变量 offset P {offset = 0} D 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 } 例题 4 P {D.offset1 = 0} D { P.offset = D.offset2} D {D1.offset1 = D.offset1 } D1 ; {D2.offset1 = D1.offset2 }D2 {D.offset2 = D2.offset2 } D id :T{enter ( id.lexeme, T.type, D.offset1); D.offset2 = D.offset1 + T.width } T integer {T.type = integer; T.width = 4 } T real {T.type = real; T.width = 8 } 13