Microsoft PowerPoint - ir

Size: px

Start display at page:

Download "Microsoft PowerPoint - ir"

墀砧寿
5 years ago
Views:

1 中间语言与中间代码生成张昱编译原理和技术中国科学技术大学计算机科学与技术学院记号流本章内容分析器语法树静态检查器语法树中间中间代码代码生成器代码生成器符号表本章内容中间语言 : 常用的中间表示 (Intermediate Representation) 后缀表示图表示三地址代码 LLVM IR 基本块和控制流图中间代码的生成声明语句 (=> 更新符号表 ) 表达式赋值语句 (=> 产生临时变量查符号表 ) 布尔表达式控制流语句 (=> 标号 / 回填技术短路计算 ) 张昱 : 编译原理和技术中间代码的表示与生成 2 后缀表示 1. 中间语言后缀形式图形表示三地址代码静态单赋值 LLVM IR 后缀表示不需要括号 (8 5) + 2 的后缀表示是后缀表示的最大优点是便于计算机处理表达式计算栈输入串张昱 : 编译原理和技术中间代码的表示与生成 4 后缀表示后缀表示不需要括号 (8 5) + 2 的后缀表示是后缀表示的最大优点是便于计算机处理表达式后缀表示的表达能力可以拓广到表示赋值语句和控制语句但很难用栈来描述控制语句的计算图形表示语法树是一种图形化的中间表示有向无环图也是一种中间表示 assign a + assign a uminus c d c d uminus c d b b (a) 语法树 (b) DAG a = ( b + c d) + c d 的图形表示张昱 : 编译原理和技术中间代码的表示与生成 5 张昱 : 编译原理和技术中间代码的表示与生成 6 1

2 图形表示构造赋值语句语法树的语法制导定义产生式 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) 张昱 : 编译原理和技术中间代码的表示与生成 7 三地址代码三地址代码 (three-address code) 一般形式 :x = y op z 例表达式 x + y z 翻译成的三地址语句序列是 = y z t 2 = x + 张昱 : 编译原理和技术中间代码的表示与生成 8 三地址代码三地址代码是语法树或 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 t 2 = c d t 2 = c d t 3 = + t 2 t 3 = + t 2 t 4 = c d t 4 = t 3 + t 2 t 5 = t 3 + t 4 a = t 5 a = t 5 uminus b assign a + + c (b) DAG d 张昱 : 编译原理和技术中间代码的表示与生成 9 张昱 : 编译原理和技术中间代码的表示与生成 10 三地址代码常用的三地址语句赋值语句 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 静态单赋值静态单赋值形式 (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 张昱 : 编译原理和技术中间代码的表示与生成 11 张昱 : 编译原理和技术中间代码的表示与生成 12 2

3 静态单赋值静态单赋值形式 (static single-assignment form) 一种便于某些代码优化的中间表示和三地址代码的主要区别所有赋值指令都是对不同名字的变量的赋值一个变量在不同路径上都定值的解决办法 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 张昱 : 编译原理和技术中间代码的表示与生成 13 LLVM IR 参考资料 LLVM IR 参考手册 ( 教程 ( 举例 :bar(a) foo(a, 4.0) + bar(31337); define %a) { entry: %calltmp = call %a, double e+00) %calltmp1 = call e+04) %addtmp = fadd double %calltmp, %calltmp1 ret double %addtmp } 张昱 : 编译原理和技术中间代码的表示与生成基本块和控制流图基本块流图基本块程序举例 prod = 0; i=1; do { prod = prod + a[i] b[i]; i=i+1; } while (i <= 20); (2) i = 1 (3) =4 i 张昱 : 编译原理和技术中间代码的表示与生成 16 基本块和流图基本块的划分基本块连续的语句序列, 控制流从它的开始进入, 并从它的末尾离开, 没有停止或分支的可能性 ( 末尾除外 ) 流图 (flow graph) 用有向边表示基本块之间的控制流信息, 基本块作为结点 (2) i = 1 (3) =4 i 划分方法首先确定所有入口语句序列的第一个语句能由 ( 无 ) 条件转移语句转到的语句紧跟在 ( 无 ) 条件转移语句后面的语句每个入口语句到下一个入口语句之前 ( 或到程序结束 ) 的语句序列构成一个基本块 (2) i = 1 (3) =4 i 张昱 : 编译原理和技术中间代码的表示与生成 17 张昱 : 编译原理和技术中间代码的表示与生成 18 3

4 流图流图 (2) i = 1 (3) =4 i (2)i=1 (3) =4 i B 1 B 2 张昱 : 编译原理和技术中间代码的表示与生成 19 (2) i = 1 (3) =4 i (2)i=1 (3) =4 i B 1 B 2 张昱 : 编译原理和技术中间代码的表示与生成 20 流图 ( 变换成 SSA 格式 ) (2) i 1 = 1 (3) i 3 = (i 1,i 2 ) (4) =4 i 3 (5) t 2 =a[ ] (6) t 3 =4 i 3 (7) t 4 =b[t 3 ] (8) t 5 =t 2 t 4 (9) t 6 =prod+t 5 (10) prod = t 6 (11) t 7 = i 3 +1 (12) i 2 =t 7 (13) if i 2 <= 20 goto (3) (2) i 1 =1 (3) i 3 = (i 1,i 2 ) (4) =4 i 3 (5) t 2 =a[ ] (6) t 3 =4 i 3 (7) t 4 =b[t 3 ] (8) t 5 =t 2 t 4 (9) t 6 =prod+t 5 (10) prod = t 6 (11) t 7 = i 3 +1 (12) i 2 =t 7 (13) if i 2 <= 20 goto (3) B 1 B 2 张昱 : 编译原理和技术中间代码的表示与生成中间代码生成概述方法和关键问题符号表结构的变化中间代码生成的方法边解析边生成中间代码语法制导的翻译方案难点 : 理解分析器的运转机制继承属性的处理基于树访问的中间代码生成重点 : 树结构的设计访问者模式 enter/exit 接口及实现如实验 2 的任务本节将以基于树访问的中间代码生成方法为主来讲解, 这是现代编译器使用的主流方法张昱 : 编译原理和技术中间代码的表示与生成 23 中间代码生成的关键问题假设采取的中间语言类似三地址代码类型与符号表的变化多样化类型 => 整型 ( 字节字 ) 浮点型类型符号表 1 个某类型的数据 => m 个字节 (m 为类型对应的字宽 ) 语句的翻译声明语句 : 不生成指令, 但会更新符号表 ( 作用域, 字宽及存放的相对地址 ) 赋值语句 : 引入临时变量数组 / 记录元素的地址计算类型转换控制流语句 : 跳转目标的确定 ( 引入标号或使用回填技术 ) 短路计算张昱 : 编译原理和技术中间代码的表示与生成 24 4

5 符号表的设计类型检查后的符号表符号表条目 :( 标识符存储类别类型信息 ) 存储类别 :extern, static, register, 类型信息 :( 类别标识, 该类别关联的其他信息 ) 如数组 (Array,(len, elemtype)) 本章符号表的变化作用域 => 多个符号表变量 : 字宽存储的相对地址 ( 以字节为单位 ) 记录类型 : 用符号表管理各个成员的字宽相对地址 4. 声明语句分配存储单元, 更新符号表作用域的管理记录类型的管理张昱 : 编译原理和技术中间代码的表示与生成 25 声明语句的翻译主要任务为局部名字分配存储单元符号表条目 : 名字类型字宽偏移作用域信息的保存记录类型的管理不产生中间代码指令, 但是要更新符号表张昱 : 编译原理和技术中间代码的表示与生成 27 块中无变量声明时的翻译计算被声明名字的类型和相对地址 P {offset =0} D; S 相对地址初始化为 0 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} 张昱 : 编译原理和技术中间代码的表示与生成 28 仅有主过程时的翻译基于树访问生成 enterp 时处理 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} visitd 时处理 ( 只有访问 D 时才知道 D 是哪种结构 ) exitd 时处理 exitt 时处理 visitt 时处理 ( 只有访问 T 时才 T T 1 {T.type = pointer (T 1.type); T.width =4} 知道 T 是哪种结构 ) 张昱 : 编译原理和技术中间代码的表示与生成 29 允许自定义过程时的翻译所讨论语言的文法 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: ; P186, 图 6.14 ( 过程参数被略去 ) 张昱 : 编译原理和技术中间代码的表示与生成 30 5

6 各过程的符号表 sort readarray exchange quicksort partition readarray 表头 i sort 空表头 a x readarray exchange quicksort exchange 表头指向 readarray 指向 exchange quicksort 表头 k v partition partition 张昱 : 编译原理和技术中间代码的表示与生成 31 符号表的组织与管理相关的数据结构设计 sort 符号表 : 哈希表 var a: ; x: ; readarray 符号表之间的连接 ( 双向链 ) var i: ; 父子 : 过程中包含哪些子过程定义 : exchange 子父 : 分析完子过程后继续分析父过程一遍分析时, 需要维护符号表栈 quicksort var k, v: ; 本章使用的符号表相关的函数 partition mktable(previous) var i, j: ; enter(table, name, type, offset) addwidth(table, width) P186, 图 6.14 enterproc(table, name, newtable) ( 过程参数被略去 ) 张昱 : 编译原理和技术中间代码的表示与生成 32 声明语句的处理 P D; S tblptr: 符号表栈 D D ; D id : T offset: 偏移量栈 proc id ; D ; S enterp:t = mktable (nil); push(t, tblptr); push (0, offset) visitd: 1) id : T: 更新符号表中 id 对应的条目 enter(top(tblptr), id.lexeme, T.type, top(offset)); top(offset) =top(offset) +T.width 声明语句的处理 P D; S tblptr: 符号表栈 D D ; D id : T offset: 偏移量栈 proc id ; D ; S enterp:t = mktable (nil); push(t, tblptr); push (0, offset) visitd: 1) id : T: 更新符号表中 id 对应的条目 2) proc id ; D; S: 访问 D 前 : 新建该过程的符号表, 进入该过程的作用域 t=mktable(top(tblptr)); push(t,tblptr);push(0, offset) 张昱 : 编译原理和技术中间代码的表示与生成 33 张昱 : 编译原理和技术中间代码的表示与生成 34 声明语句的处理 P D; S tblptr: 符号表栈 D D ; D id : T offset: 偏移量栈 proc id ; D ; S enterp:t = mktable (nil); push(t, tblptr); push (0, offset) 如果 S 中存在对该过 visitd: 程的递归调用, 则在分 1) id : T: 更新符号表中 id 对应的条目析 S 前将该过程名插入符号表 2) proc id ; D; S: 访问 D 前 : 新建该过程的符号表, 进入该过程的作用域访问 S 后 : 将该过程符号信息插入到父符号表, 退出作用域 t = top(tblptr); addwidth(t, top(offset) ); pop(tblptr); pop(offset); enterproc(top(tblptr), id.lexeme, t) 张昱 : 编译原理和技术中间代码的表示与生成 35 声明语句的处理 P D; S tblptr: 符号表栈 D D ; D id : T offset: 偏移量栈 proc id ; D ; S enterp:t = mktable (nil); push(t, tblptr); push (0, offset) visitd: 1) id : T: 更新符号表中 id 对应的条目 2) proc id ; D; S: exitp: addwidth (top (tblptr), top (offset)); pop(tblptr); pop (offset) 张昱 : 编译原理和技术中间代码的表示与生成 36 6

7 记录的域名管理关联的文法 T record D 记录类型单独建符号表 ( 类型表达式 ), 域相对地址从 0 开始 visitt: record D 访问 D 之前 : 建立符号表, 进入作用域 t = mktable(nil); push(t, tblptr); push(0, offset) 结尾 : 设置记录的类型表达式和宽度, 退出作用域 T.type = record (top(tblptr) ); T.width = top(offset); pop(tblptr); pop(offset) 张昱 : 编译原理和技术中间代码的表示与生成赋值语句分配临时变量, 存储表达式计算的中间结果数组元素的地址计算类型转换赋值语句的翻译主要任务赋值语句的中间代码生成关联的文法复杂的表达式 => 多条计算指令组成的序列 S id := E E E 1 + E 2 E 1 (E 1 ) id 分配临时变量保存中间结果 id: 查符号表获得其存储的场所数组元素 : 元素地址计算符号表中保存数组的基址和用于地址计算的常量表达式的值数组元素在中间代码指令中表示为基址 [ 偏移 ] 可以进行一些语义检查类型检查变量未定义 / 重复定义 / 未初始化类型转换 : 因为目标机器的运算指令是区分类型的张昱 : 编译原理和技术中间代码的表示与生成 39 visits: id := E 结尾 : 获取 id 的地址和存放 E 结果的场所, 发射赋值指令 p = lookup(id.lexeme); if p!= nil then emit ( p, =,E.place) else error visite: E E 1 + E 2 结尾 : 发射加法指令 E.place = newtemp(); emit (E.place, =,E 1.place, +,E 2.place) 张昱 : 编译原理和技术中间代码的表示与生成 40 赋值语句的中间代码生成关联的文法 S id := E visite: E E 1 + E 2 E 1 (E 1 ) id E E 1 + E 2 结尾 : 发射加法指令 E - E 1 结尾 : 发射负号运算指令 E.place = newtemp(); emit (E.place, =, uminus, E 1.place) E ( E 1 ) 结尾 :E.place = E 1.place; E id 结尾 : 获取 id 的地址并作为 E 的场所 p = lookup(id.lexeme); if p!= nil then E.place = p else error 张昱 : 编译原理和技术中间代码的表示与生成 41 数组元素的地址计算一维数组元素的地址计算 A 的第 i 个元素的地址 : base +(i low ) w 变换成 : i w + (base low w) low w 是常量, 编译时计算, 减少运行时计算二维数组元素的地址计算列为主序 ( 列优先 )? 行为主序? 行为主序时 :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) 张昱 : 编译原理和技术中间代码的表示与生成 42 7

8 数组元素的地址计算多维数组元素的地址计算以行为主序下标变量 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 翻译的主要任务发射地址计算的指令基址 [ 偏移 ] 相关的中间指令 :t=b[o],b[o]=t 数组元素的访问处理关联的文法 S L := E Elist Elist, E E L id [ Elist ] id E L 采用语法制导的翻译方案时存在的问题 Elist Elist, E E 由 Elist 的结构只能得到各维的下标值, 但无法获得数组的信息 ( 如各维的长度 ) 需要改写文法为 :L Elist ] id Elist id [ E Elist, E Elist id [ E 由这个定义可以获得数组的信息, 并从左到右传播下去, 达到边分析边计算的目的张昱 : 编译原理和技术中间代码的表示与生成 43 张昱 : 编译原理和技术中间代码的表示与生成 44 数组元素的访问处理基于树来生成会简单多了, 关联的文法不用改写文法 S L := E L id [ Elist ] id Elist Elist, E E visitl: L id [ E 1, E 2,, E n ] 访问 E 1 之后 : ndim = 1; place = E 1.place; // 局部变量每次访问 E i 之后计算 : t = newtemp(); ndim ++; emit (t, =,place,, limit(id.place, m)); emit (t, =,t, +,E i.place); place = t; 结尾 : L.place = newtemp(); ndim ++; emit (L.place, =,base(id.place),, invariant (id.place) ); L.offset = newtemp(); emit (L.offset, =,place,, width(id.place)) ); 张昱 : 编译原理和技术中间代码的表示与生成 45 数组元素的访问处理关联的文法 S L := E E L visite: E L 结尾 :if(l.offset == null) / 简单变量 / E.place = L.place else { E.place = newtemp(); emit (E.place, =,L.place, [, L.offset, ] ); } visits: S L:=E 结尾 :if(l.offset == null) emit (L.place, =,E.place); else emit (L.place, [, L.offset, ], =, E.place); 张昱 : 编译原理和技术中间代码的表示与生成 46 例类型转换 x=y+i j (x 和 y 的类型是 real,i 和 j 的类型是 integer) 中间代码 =iint j t 2 = inttoreal t 3 =yreal+ t 2 x=t 3 目标机器的运算指令是区分整型和浮点型的高级语言中的重载算符 => 中间语言中的多种具体算符张昱 : 编译原理和技术中间代码的表示与生成 47 类型转换的处理以 E E 1 + E 2 为例说明 visite: E E 1 + E 2 结尾 : 判断 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; }elseif(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; } 张昱 : 编译原理和技术中间代码的表示与生成 48 8

9 中间代码生成的主要任务 6. 布尔表达式和控制流语句布尔表达式 : 短路计算控制流语句的翻译 : 标号回填技术 switch 的翻译优化过程调用的中间代码格式与翻译主要任务布尔表达式的计算 : 完全计算短路计算控制流语句分支结构 (if switch) 循环结构过程 / 函数的调用各子结构的布局 + 无条件或有条件转移指令跳转目标的两种处理方法标号技术 : 新建标号, 跳转到标号回填技术 : 先构造待回填的指令链表, 待跳转目标确定时再回填链表中各指令缺失的目标信息张昱 : 编译原理和技术中间代码的表示与生成 50 布尔表达式布尔表达式的作用计算逻辑值作为控制流语句中的条件本节关联的布尔表达式文法 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 张昱 : 编译原理和技术中间代码的表示与生成 51 控制流语句的翻译关联的控制流语句 S if B then S 1 if B then S 1 else S 2 while B do S 1 switch E begin case V 1 : S 1 case V n-1 : S n-1 default: S n callid(elist) S 1 ; S 2 Elist Elist, E E 张昱 : 编译原理和技术中间代码的表示与生成 52 if 语句的中间代码布局问题与对策 B 的短路计算中, 需要知道其为真或假时的跳转目标 B S 1 S 2 分别会发射多少条指令是不确定的引入标号 : 先确定标号, 在目标确定时发射标号指令可调用 newlabel( ) 产生新标号, 每条语句有 next 标号 B.code (a) if-then 指向 B.true 指向 B.false B.code goto S.next B.false: S 2.code (b) if-then-else 指向 B.true 指向 B.false 张昱 : 编译原理和技术中间代码的表示与生成 53 while 语句和顺序结构 while 循环语句的中间代码引入开始标号 S.begin, 作为循环的跳转目标顺序结构为每一语句 S 1 引入其后的下一条语句的标号 S 1.next S.begin: 指向 B.true B.code 指向 B.false goto S.begin (c) while-do S 1.next: S 2.code (d) S 1 ; S 2 张昱 : 编译原理和技术中间代码的表示与生成 54 9

10 if 语句的中间代码生成问题与对策 B 的短路计算中, 需要知道其为真或假时的跳转目标 B S 1 S 2 分别会发射多少条指令是不确定的引入标号 : 先确定标号, 在目标确定时发射标号指令可调用 newlabel( ) 产生新标号 visitif-then: B.code 访问 B 前 :B.true = newlabel(); B.false = S.next; // 继承属性进入 S 1 前 :S 1.next = S.next; (a) if-then 访问 S 1 后 :S.code = B.code gen(b.true, : ) S 1.code 指向 B.true 指向 B.false 张昱 : 编译原理和技术中间代码的表示与生成 55 if 语句的中间代码生成回填 : 仅使用综合属性把跳转到同一个标号的指令放到同一张指令表中如, 为 B 引入综合属性 truelist 和 falselist 分别收集要回填的跳转指令, 为 S 引入 nextlist 收集要回填的跳转指令等目的标号确定时, 再把它填到表中的各条指令中指向 B.true visitif-then:s if B then S 1 B.code 指向 B.false 准备访问 S 1 前 :instr = nextinstr; 访问 S 1 后 : backpatch(b.truelist, instr); // 回填 (a) if-then S.nextlist = merge(b.falselist, S 1.nextlist); 张昱 : 编译原理和技术中间代码的表示与生成 56 if 语句的中间代码生成 S if B then S 1 else S 2 ( 标号技术 ) 访问 B 前 :B.true = newlabel(); B.false = newlabel(); 进入 S 1 前 :S 1.next = S.next; 进入 S 2 前 :S 2.next = S.next; 访问 S 2 后 :S.code = B.code gen(b.true, : ) S 1.code gen( goto, S.next) gen(b.false, : ) S 2.code 张昱 : 编译原理和技术中间代码的表示与生成 57 if 语句的中间代码生成 S if B then S 1 else S 2 ( 标号技术 ) 访问 B 前 :B.true = newlabel(); B.false = newlabel(); 进入 S 1 前 :S 1.next = S.next; 进入 S 2 前 :S 2.next = S.next; 访问 S 2 后 :S.code = B.code gen(b.true, : ) gen( goto, S.next) gen(b.false, : ) S 2.code 回填进入 S 1 前 :instr1 = nextinstr; 访问 S 1 后 :nextlist=makelist(nextinstr); emit( goto_ ); 进入 S 2 前 :instr2 = nextinstr; 访问 S 2 后 :backpatch(b.truelist, instr1); backpatch(b.falselist, instr2); S.nextlist = merge(merge(s 1.nextlist, nextlist), S 2.nextlist); 张昱 : 编译原理和技术中间代码的表示与生成 58 while 语句的中间代码生成 S while B do S 1 访问 while 前 :S.begin = newlabel(); 访问 B 前 :B.true = newlabel(); B.false = S.next; 进入 S 1 前 :S 1.next = S.begin; S.begin: 指向 B.true B.code 指向 B.false goto S.begin (c) while-do 访问 S 1 后 :S.code = gen(s.begin, : ) B.code gen(b.true, : ) S 1.code gen( goto, S.begin) 张昱 : 编译原理和技术中间代码的表示与生成 59 while 语句的中间代码生成 S while B do S 1 访问 while 前 :S.begin = newlabel(); S.begin: B.code 访问 B 前 :B.true = newlabel(); B.false = S.next; goto S.begin 进入 S 1 前 :S 1.next = S.begin; (c) while-do 访问 S 1 后 :S.code = gen(s.begin, : ) B.code gen(b.true, : ) gen( goto, S.begin) 回填进入 B 前 :instr1 = nextinstr; 进入 S 1 前 :instr2 = nextinstr; 访问 S 1 后 :backpatch(s 1.nextlist, instr1); backpatch(b.truelist, instr2); S.nextlist = B.falselist; emit( goto, instr1); 指向 B.true 指向 B.false 张昱 : 编译原理和技术中间代码的表示与生成 60 10

11 布尔表达式的控制流翻译布尔表达式的翻译如果 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 or B 2 ( 标号技术 ) 访问 B 1 前 :B 1.true = B.true; B 1.false = newlabel(); 访问 B 2 前 :B 2.true = B.true; B 2.false = B 1.false; 访问 B 2 后 :B.code = B 1.code gen(b 1.false, : ) B 2.code B not B 1 ( 标号技术 ) 访问 not 前 :B 1.true = B.false; B 1.false = B.true; 访问 B 1 后 :B.code = B 1.code 张昱 : 编译原理和技术中间代码的表示与生成 61 张昱 : 编译原理和技术中间代码的表示与生成 62 布尔表达式的翻译 B B 1 and B 2 ( 标号技术 ) 访问 B 1 前 :B 1.true = newlabel(); B 1.false = B.false; 访问 B 2 前 :B 2.true = B.true; B 2.false = B.false; 访问 B 2 后 :B.code = B 1.code gen(b 1.true, : ) B 2.code 布尔表达式的翻译 B E 1 relop E 2 ( 标号技术 ) 访问 E 2 后 :B.code = E 1.code E 2.code gen( if, E 1.place, relop.op, E 2.place, goto, B.true) gen( goto, B.false) B (B 1 )( 标号技术 ) 访问 ( 前 :B 1.true = B.true; B 1.false = B.false; 访问 ) 后 :B.code = B 1.code 张昱 : 编译原理和技术中间代码的表示与生成 63 B true( 标号技术 ) 访问 true 后 :B.code = gen( goto, B.true) B false( 标号技术 ) 访问 false 后 :B.code = gen( goto, B.false) 张昱 : 编译原理和技术中间代码的表示与生成 64 布尔表达式的翻译 ( 回填 ) 布尔表达式的翻译 ( 回填 ) 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 _ ); } 张昱 : 编译原理和技术中间代码的表示与生成 65 张昱 : 编译原理和技术中间代码的表示与生成 66 11

12 switch 语句的翻译 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 ift!=v 1 goto L 1 S 1 goto next L 1 : ift!=v 2 goto L 2 S 2 goto next L 2 : L n-2 :ift!=v n-1 goto L n-1 S n-1 goto next L n-1 : S n next: 张昱 : 编译原理和技术中间代码的表示与生成 67 switch 语句的翻译分支较多时, 将分支测试代码集中在一起, 便于生成较好的分支测试代码 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... goto L n L n-1 : S n -1 next: goto next 张昱 : 编译原理和技术中间代码的表示与生成 68 switch 语句的翻译过程调用的翻译中间代码增加一种 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) 张昱 : 编译原理和技术中间代码的表示与生成 69 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 张昱 : 编译原理和技术中间代码的表示与生成 70 过程调用的翻译例题 1 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 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) 张昱 : 编译原理和技术中间代码的表示与生成 71 张昱 : 编译原理和技术中间代码的表示与生成 72 12

13 例题 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) 会导致越界错误张昱 : 编译原理和技术中间代码的表示与生成 73 例题 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: 张昱 : 编译原理和技术中间代码的表示与生成 74 例题 2 例题 3 C 语言的 for 语句有下列形式 for (e 1 ;e 2 ;e 3 )stmt 它和 e 1 ; while (e 2 )do begin stmt; e 3 ; 有同样的语义 e 1 L1: e 2 L2: e 3 goto L1 stmt goto L2 假转, 由外层语句决定真转 Pascal 语言 var a,b : array[1..100] of integer; a:=b // 允许数组之间赋值也允许在相同类型的记录之间赋值 C 语言数组类型不行, 结构体类型可以为这种赋值选用或设计一种三地址语句, 它要便于生成目标代码答 : 仍然用中间代码复写语句 x=y, 在生成目标代码时, 必须根据它们类型的 size, 产生一连串的值传送指令张昱 : 编译原理和技术中间代码的表示与生成 75 张昱 : 编译原理和技术中间代码的表示与生成 76 13

Microsoft PowerPoint - ch7 [Compatibility Mode]

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