南京大学：《编译原理 Principles and Techniques of Compilers》课程教学电子教案（课件讲义）第六章 中间代码生成

第六章中间代码生成 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版

许畅 南京大学计算机系 2022年春季 第六章 中间代码生成 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅

本章内容 。中间代码表示 表达式的有向无环图DAG 三地址代码：x=y0叩z 。 类型检查 类型、类型检查、表达式的翻译 中间代码生成 控制流、回填 2

本章内容 • 中间代码表示 – 表达式的有向无环图DAG – 三地址代码：x = y op z • 类型检查 – 类型、类型检查、表达式的翻译 • 中间代码生成 – 控制流、回填 2 南大编译许畅

编译器前端的逻辑结构 前端是对源语言进行分析并产生中间表示 处理与源语言相关的细节，与目标机器无关 前端后端分开的好处：不同的源语言、不同的机 器可以得到不同的编译器组合 语法 静态检 中间代码 中间 代码 分析器 查程序 生成器 代码 生成器 前端 后端 图6-1一个编译器前端的逻辑结构

编译器前端的逻辑结构 • 前端是对源语言进行分析并产生中间表示 • 处理与源语言相关的细节，与目标机器无关 • 前端后端分开的好处：不同的源语言、不同的机 器可以得到不同的编译器组合 3 南大编译许畅

中间代码表示及其好处 形式 多种中间表示，不同层次 抽象语法树 三地址代码 重定位 为新的机器建编译器，只需要做从中间代码到新的目 标代码的翻译器（前端独立） 高层次的优化 优化与源语言和目标机器都无关 4

中间代码表示及其好处 • 形式 – 多种中间表示，不同层次 – 抽象语法树 – 三地址代码 • 重定位 – 为新的机器建编译器，只需要做从中间代码到新的目 标代码的翻译器 (前端独立) • 高层次的优化 – 优化与源语言和目标机器都无关 4 南大编译许畅

中间代码的实现 静态类型检查和中间代码生成的过程都可以用语 法制导的翻译来描述和实现 对于抽象语法树这种中间表示的生成，第五章已 经介绍过 语法 静态检 中间代码 中间 代码 分析器 查程序 生成器 代码 生成器 前端 后端 图6-1一个编译器前端的逻辑结构 5

中间代码的实现 • 静态类型检查和中间代码生成的过程都可以用语 法制导的翻译来描述和实现 • 对于抽象语法树这种中间表示的生成，第五章已 经介绍过 5 南大编译许畅

生成抽象语法树的语法制导定义 ·a+a*(b-c)+(b-c)*d的抽象语法树 PRODUCTION SEMANTIC RULES 1) E→E1+T E.node new Node('+',E1.node,T.node) 2) E→E1-T E.node new Node('-,E.node,T.node) 3) E→T E.node=T.node 4) T→（E) T.node=E.node 5) T→id T.node =new Leaf(id,id.entry) 6) T→num T.node new Leaf(num,num.val) 6

生成抽象语法树的语法制导定义 • a + a * (b – c) + (b – c) * d的抽象语法树 6 南大编译许畅

表达式的有向无环图 语法树中，公共子表达式每出现一次，就有一颗 对应的子树 表达式的有向无环图(Directed Acyclic Graph, DAG)能够指出表达式中的公共子表达式，更简 洁地表示表达式 b 图6-3 表达式a+a*(b-c)+ (b-c)*d的DAG 7

表达式的有向无环图 • 语法树中，公共子表达式每出现一次，就有一颗 对应的子树 • 表达式的有向无环图 (Directed Acyclic Graph, DAG) 能够指出表达式中的公共子表达式，更简 洁地表示表达式 7 南大编译许畅

DAG构造 可以用和构造抽象语法树一样的SDD来构造 不同的处理 在函数Lemf和Node每次被调用时，构造新节点前先检查 是否已存在同样的节点，如果已经存在，则返回这个 已有的节点 1) PI Leaf (id,entry-a) 。构造过程示例 2) P2 Leaf(id,entry-a)=p 3) P3 Leaf(id,entry-b) 4)pa Leaf(id,entry-c) 5)）5=Node'-',ps,p4) 6)p6=Node('*',p1,pP5) 7)p= Node('+',p1,p6) 8)ps Leaf (id,entry-b)=p3 9) po Leaf(id,entry-c)=pa 10) P1o Node('-',P3,PA)=ps 11) pu=Leaf(id,entry-d) 12) p12=Node('*',p5,p11) 13) p13=Node'+',p7,p12) 图6-3表达式a+a*(b-c)+ (b-c)*d的DAG 图6-5 图6-3所示的DAG的构造过程 8

DAG构造 • 可以用和构造抽象语法树一样的SDD来构造 • 不同的处理 – 在函数Leaf和Node每次被调用时，构造新节点前先检查 是否已存在同样的节点，如果已经存在，则返回这个 已有的节点 • 构造过程示例 8 南大编译许畅

三地址代码(1) 每条指令右侧最多有一个运算符 一般情况可以写成x=y0p2 0 允许的运算分量 名字：源程序中的名字作为三地址代码的地址 常量：源程序中出现或生成的常量 编译器生成的临时变量 9

三地址代码 (1) • 每条指令右侧最多有一个运算符 – 一般情况可以写成x = y op z • 允许的运算分量 – 名字：源程序中的名字作为三地址代码的地址 – 常量：源程序中出现或生成的常量 – 编译器生成的临时变量 9 南大编译许畅

三地址代码(2) 指令集合(1) 运算/赋值指令： x=yopz 人/ x=opy 复制指令： x=y 无条件转移指令： goto L 条件转移指令： if x goto L if False x goto L 条件转移指令： if x relop y goto L 10

三地址代码 (2) • 指令集合 (1) – 运算/赋值指令： x = y op z x = op y – 复制指令： x = y – 无条件转移指令： goto L – 条件转移指令： if x goto L if False x goto L – 条件转移指令： if x relop y goto L 10 南大编译许畅