第七章 中间代码生成 静态中间代码记号分析检查代码中间生成流器器生成代码器器本章内容 介绍几种常用的中间表示 (intermediate representation): 后缀表示 图形表示和三地址代码 用语法制导定义和翻译方案来说明源语言的各种 用语法制导定义和翻译方案来说明源语言的各种构造怎样被翻译成中间形式
7.1.1 后缀表示 7.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
7.1 中间语言 后缀表示不需要括号 (8 5) + 2 的后缀表示是 8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 计算栈输入串 8 5 2 + 8 5 2 + 8 5 2 + 3 2 + 32 + 5
7.1 中间语言 后缀表示不需要括号 (8 5) + 2 的后缀表示是 8 5 2 + 后缀表示的最大优点是便于计算机处理表达式 后缀表示也可以拓广到表示赋值语句和控制 后缀表示也可以拓广到表示赋值语句和控制语句, 但很难用栈来描述控制语句的计算
7.1.2 图形表示 7.1 中间语言 语法树是一种图形化的中间表示 有向无环图也是一种中间表示 assign assign a + a + + + uminus uminus c d c d c d b b (a) 语法树 (b) DAG a = ( b + c d) + c d 的图形表示
7.1 中间语言 构造赋值语句语法树的语法制导定义修改构造结点的函数可生成有向无环图 产生式语义规则 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 EE 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)
7.1 中间语言 7.1.3 三地址代码 (three-address code) 一般形式 :x = y op z 例表达式 x + y z 翻译成的三地址语句序列是 t 1 = y z t 2 = x + t 1
7.1 中间语言 三地址代码是语法树或 DAG 的一种线性表示 例 a=( b+c d)+c d 语法树的代码 t 1 = b t 2 = c d t 3 = t 1 + t 2 t 4 = c d t 5 = t 3 + t 4 uminus a = t 5
7.1 中间语言 三地址代码是语法树或 DAG 的一种线性表示 例 a=( b+c d)+c d 语法树的代码 DAG 的代码 t 1 = b t 1 = b assign t 2 = c d t 2 = c d a + t 3 = t 1 + t 2 t 3 = t 1 + 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
7.1 中间语言 本书常用的三地址语句 赋值语句 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 &y,x x = y 和 x = y
7.1 中间语言 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 中间语言 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
本节介绍 7.2 声明语句 为局部名字建立符号表条目 为它分配存储单元 符号表中包含名字的类型和分配给它的存储单元的相对地址等信息
7.2.1 过程中的声明 7.2 声明语句
7.2 声明语句 计算被声明名字的类型和相对地址 P {offset =0} D; S D D ; D D id : T {enter t ( id.lexeme, l 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 声明语句 计算被声明名字的类型和相对地址 P {offset =0} D; S D D ; D D id : T {enter t ( id.lexeme, l 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 声明语句 7.2.2 作用域信息的保存 sort 所讨论语言的文法 P D; S D D ; D id : T proc id ; D ; S var a: ; x: ; readarray var i: ; exchange quicksort ik var k, v: ; partition var i, j: ; 图 614 的程序图 6.14 的程序参数被略去
7.2 声明语句 sort readarray exchange quicksort ik partition sort 空表头 a x readarray exchange quicksort 指向 readarray 指向 exchange i readarray 表头 exchange 表头 符号表实例 quicksort 表头 k v partition ii partition
7.2 声明语句 符号表的特点 各过程有各自的符号表 符号表之间有双向链 构造符号表时需要符号表栈 构造符号表需要活动记录栈 语义动作用到的函数 mktable(previous) enter(table, name, type, offset) addwidth(table, width) enterproc(table, name, newtable) sort var a: ; x: ; readarray var i: ; exchange quicksort ik var k, v: ; partition var i, j: ; 图 614 6.14 的程序参数被略去
7.2 声明语句 P MD; S {addwidth (top (tblptr), top (offset)); pop(tblptr); pop (offset)} M {t = mktable (nil); push(t, tblprt); push (0, offset) } D D 1 ; D 2 D proc id ; N D 1 ; S {t = top(tblptr); addwidth(t, top(offset)); pop(tblptr); pop(offset); enterproc(top(tblptr),id.lexeme, ( p ) 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 声明语句 P MD; S {addwidth (top (tblptr), top (offset)); pop(tblptr); pop (offset)} M {t = mktable (nil); push(t, tblprt); push (0, offset) } D D 1 ; D 2 D proc id ; N D 1 ; S {t = top(tblptr); addwidth(t, top(offset)); pop(tblptr); pop(offset); enterproc(top(tblptr),id.lexeme, ( p ) 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 声明语句 P MD; S {addwidth (top (tblptr), top (offset)); pop(tblptr); pop (offset)} M {t = mktable (nil); push(t, tblprt); push (0, offset) } D D 1 ; D 2 D proc id ; N D 1 ; S {t = top(tblptr); addwidth(t, top(offset)); pop(tblptr); pop(offset); enterproc(top(tblptr),id.lexeme, ( p ) 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.3 记录的域名 T record D end 记录类型单独建符号表, 作为类型表达式的主要部分, 域的相对地址从 0 开始 record T record L D end a: ; {T.type = record (top(tblptr)); T.width = top(offset); pop(tblptr); pop(offset) } L {t = mktable(nil); push(t, tblprt); push(0, offset) } r : record i : ;... end; k : ; end
7.3 赋值语句 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, p =,E 1.place, +,E p 2.place) p }
7.3 赋值语句 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); l ) if p!= nil then E.place = p else error }
7.3 赋值语句 7.3.2 数组元素的地址计算一维数组 A 的第 i 个元素的地址计算 base + ( i low ) w 变换成 i w + (base low w) 减少了运行时的计算
7.3 赋值语句 二维数组 A: array[1..2, 1..3] of T A[1,1] A[1,2] A[1,3] 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]
7.3 赋值语句 i 2 二维数组 A: array[1..2, 1..3] of T i 2 A[1,1] A[1,2] 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)
7.3 赋值语句 多维数组下标变量 A[i 1, i 2,..., i k ] 的地址表达式 1 2 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 赋值语句 7.3.3 数组元素地址计算的翻译方案 下标变量访问的产生式 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 7.3 赋值语句
7.3 赋值语句 L id {L.place =id.place; L.offset = null } Elist id [ E {Elist.place l = E.place; Elist.ndim = 1; Elist.array =id.place } Elist Elist 1, E { t = newtemp(); m = Elist 1.ndim + 1; emit (t, =,Elist 1.place,, limit(elist 1.array, m)); emit (t, =,t, +,E.place); Elist.array = Elist 1.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 赋值语句 E L{if L.offset == null then / L 是简单变量 / E.place = L.place else begin E.place = newtemp(); emit (E.place, l =, L.place, [, L.offset, ] ) end } E E 1 + E 2 {E.place = newtemp(); emit (E.place, =, E 1.place, +, +,EE 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, [, L.offset, ], =, E.place)}
L.place =x L.offset = null x t 1 = y 20 t 1 = t 1 + z Elist.place = y Elist.ndim =1 Elist.array =A 7.3 赋值语句 x = t 4 S := t 4 = t 2 [t 3 ] E.place =t 4 t 2 = c L.place =t 2 t 3 = 4 t 1 L.offset =t 3 Elist.place =t 1 ] Elist.ndim =2 Elist.array =A A [ E.place = y L.place =y L.offset = null A[10, 20], y x := A[ y, z ] 的注释分析树 注 :c =A 84 E.place = z L.place =z L.offset = null z
7.3 赋值语句 7.3.4 类型转换 例 x=y+i j (x 和 y的类型是 real,i 和 j的类型是 integer) 中间代码 t 1 =iint j t 2 = inttoreal t 1 t 3 =yreal+ t 2 x=t 3
7.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 end else if E 1.type t == integer && E 2.type t == real then begin u = newtemp(); emit (u, =, inttoreal, E 1.place); p emit (E.place, =,u, real+, E 2.place); E.type = real end...
7.4 布尔表达式和控制流语句 7.4.1 布尔表达式 布尔表达式有两个基本目的 计算逻辑值 在控制流语句中用作条件表达式 本节所用的布尔表达式文法 B B or B B and B notb (B ) E relop E true false
7.4 布尔表达式和控制流语句 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 布尔表达式和控制流语句 7.4.2 控制流语句的翻译 S if B then S 1 if B then S else S if B then S 1 else S 2 while B do S 1 S 1 ; S 2
7.4 布尔表达式和控制流语句 B.true, B.false, S.begin, S.next 继承属性为便于翻译, 给指令加标号, 可通过调用 newlabel() 产生新标号指向 B.true 指向 B.true B.code 指向 B.false B.code 指向 B.false B.true: B.true: S 1.code S 1.code... goto S.next B.false: S 2.code (a) if-then... (b) if-then-else S.begin: B.true: B.code S 1.code goto S.begin... (c) while-do 指向 B.true 指向 B.false S 1.next: S 1.code S 2.code... (d) S 1 ; S 2
7.4 布尔表达式和控制流语句 (b) 中若 S 1.code 后用 goto S 1.next, S 1.next 为指令 goto S.next, 则产生冗余跳转指令指向 B.true 指向 B.true B.code 指向 B.false B.code 指向 B.false B.true: B.true: S 1.code S 1.code B.false:... goto S.next B.false: S 2.code (a) if-then... (b) if-then-else S.begin: B.true: B.code S 1.code goto S.begin... (c) while-do 指向 B.true 指向 B.false S 1.next: S 1.code S 2.code... (d) S 1 ; S 2
7.4 布尔表达式和控制流语句 S if B then S 1 B d {B.true = newlabel(); B.true: B.false = S.next; B.code S 1.code... 指向 B.true 指向 B.false S 1.next = S.next; (a) if-then S.code = B.code gen(b.true, : ) S 1.code }
7.4 布尔表达式和控制流语句 S if B then S 1 else S 2 B d {B.true = newlabel(); B.true: B.false = newlabel(); S 1.next = S.next; B.code S 1.code goto S.next B.false: S 2.code... (b) if-then-else 指向 B.true 指向 B.false S 2.next = S.next; S.code = B.code gen(b.true, : ) S 1.code gen( goto, S.next) gen(b.false, : ) S 2.code}
7.4 布尔表达式和控制流语句 S while B do S 1 {S.begin = newlabel(); B.true = newlabel(); B.false = S.next; S.begin: B.true: B.code S 1.code goto S.begin... S 1.next = S.begin; S.code = gen(s.begin, : ) B.code (c) while-do 指向 B.true 指向 B.false gen(b.true, : ) S 1.code gen( goto, S.begin)}
7.4 布尔表达式和控制流语句 S S 1 ; S 2 {S 1.next = newlabel(); S 2.next = S.next; S.code = S 1.code gen(s 1.next, : ) S 2.code } S 1.next: S 1.code S 2.code... (d) S 1 ; S 2
7.4 布尔表达式和控制流语句 7.4.3 布尔表达式的控制流翻译 如果 B 是 a < b 的形式, 那么代码是 : if a < b goto B.true goto B.false
7.4 布尔表达式和控制流语句 例表达式 a < b or c < d and e < f 的代码是 : if a < b goto L true goto L 1 L 1 : ifc < d goto L 2 goto L false L 2 : if e < f goto L true goto L false
7.4 布尔表达式和控制流语句 B B 1 or B 2 { B 1.true = B.true; B 1.false f = newlabel(); B 2.true = B.true; B 2.false = B.false; B.code = B 1.code gen(b 1.false, : ) B 2.code } B not B 1 { B 1.true = B.false; B 1.false = B.true; B.code = B 1.code }
7.4 布尔表达式和控制流语句 B B 1 and B 2 { B 1.true = newlabel(); B 1.false f = B.false; ; B 2.true = B.true; B 2.false = B.false; B.code = B 1.code gen(b 1.true, : ) B 2.code } B (B 1 ) { B 1.true = B.true; B 1.false = B.false; B.code = B 1.code }
7.4 布尔表达式和控制流语句 B E 1 relop E 2 { B.code = E 1.code E 2.code B true gen( if if, E 1.place, relop.op, E 2.place, goto, B.true) gen( goto, B.false) } { B.code = gen( goto, B.true)} B false { B.code = gen( goto, B.false)}
7.4 布尔表达式和控制流语句 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 end
7.4 布尔表达式和控制流语句 分支数较少时 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 1 : S n 的代码 L 1 : ift!=v 2 goto L 2 next: S 2 的代码 goto next L 2 :......
7.4 布尔表达式和控制流语句 分支较多时, 将分支测试代码集中在一起, 便于生成较好的分支测试代码 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 的代码... gotonext t if t == V n-1 goto L n-1... gotol n L n-1 : S n -1 的代码 next: goto next
7.4 布尔表达式和控制流语句 中间代码增加一种 case 语句, 便于代码生成器对它进行特别处理 test: case V 1 L 1 case V 2 L 2... case V n-1 1 L n-1 1 case t L n next: 一个生成 ( 两种优化 ): 用二分查找确定该执行的分支 建立入口地址表, 直接找到该执行的分支的例子见第 244 页习题 8.8
7.4 布尔表达式和控制流语句 7.4.5 过程调用的翻译 S call id (Elist) Elist Elist, E Elist E
7.4 布尔表达式和控制流语句 过程调用 id(e 1, E 2,,E n ) 的中间代码结构 E 1.place = E 1 的代码 E 2.place p = E 2的代码... E n.place = E n 的代码 n p n param E 1.place param E 2.place... param E n.place n call id.place, n
7.4 布尔表达式和控制流语句 S call id (Elist) { 为长度为 n 的队列中的每个 E.place, emit( call, id.place, n)} Elist Elist, E Elist E emit( param, E.place); { 把 E.place 放入队列末尾 } { 将队列初始化, 并让它仅含 E.place}
本章要点 中间代码的几种形式, 它们之间的相互转换 符号表的组织和作用域信息的保存 数组元素定址的翻译方案, 布尔表达式的两种不同实现方式 赋值语句和各种控制流语句的中间代码格式和生成中间代码的翻译方案 过程调用的中间代码格式和生成中间代码的翻译方案
例题 1 Pascal 语言的标准将 for 语句 for v := initial to final do stmt 定义成和下面的代码序列有同样的含义 : begin t 1 := initial; t 2 := final; if t 1 <= t 2 then begin v:=t 1 ; stmt; while v <> t 2 do begin end end end v := succ(v); stmt
例题 1 Pascal 语言的标准将 for 语句 for v := initial to final do stmt 能否定义成和下面的代码序列有同样的含义? begin end t 1 := initial; t 2 := final; 1 2 v:=t 1 ; while v <= t 2 do begin 2 stmt; v := succ(v) end
例题 1 Pascal 语言的标准将 for 语句 for v := initial to final do stmt 能否定义成和下面的代码序列有同样的含义? begin t 1 := initial; t 2 := final; 1 2 v:=t 1 ; while v <= t 2 do begin stmt; v := succ(v) end end final 为最大整数时, succ(final) 会导致越界错误
例题 1 Pascal 语言 for 语句 for v := initial to final do stmt 的中间代码结构如下 : t 1 =initial t 2 =final if t 1 > t 2 goto L1 v=t 1 L2: stmt L1: if v == t 2 goto L1 v=v+1 goto L2
例题 2 C 语言的 for 语句有下列形式 for (e 1 ;e 2 ;e 3 )stmt 它和 e 1 ; while (e 2 )do begin 2 stmt; e 3 ; 3 end 有同样的语义
例题 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, 产生一连串的值传送指令
例题 4 下面的翻译方案使用了变量 offset, 请重写该翻译方案, 它完成同样的事情, 但只使用文法符号的属性, 而不使用变量 offset P D D;D D D id : T {offset = 0} D { enter(id.lexeme, T.type, offset); offset = offset +T 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 {D1.offset1 =Doffset1 D.offset1 }D1; {D2.offset1 = D1.offset2 }D2 D.offset2} {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 }