编译器设计与实现 梁红瑾 hongjin@nju.edu.cn http://cs.nju.edu.cn/hongjin/teaching/ese_compiler

课程内容 介绍编译器构造的一般原理和基本实现方法 强调对编译原理和技术的宏观理解，不偏向于某 种源语言或目标机器 计算机系《编译原理》课程的简化版

学习意义 对编程语言的设计和实现有深刻的理解，对和编 程语言有关的理论有所了解 从软件工程看，编译器是一个很好的实例，所介 绍的概念和技术能应用到一般的软件设计之中 编译技术的应用和编译技术的发展 高级语言设计、计算机体系结构的优化（并行、内存 分层）、新型计算机体系结构设计、程序翻译、提高 软件开发效率的工具 、高可信软件 形式化的思维方式

教材和参考书 课程讲义、作业： http://cs.nju.edu.cn/hongjin/teaching/ese_compiler 《编译原理（第2版，本科教学版）》，Alfred V. Aho等著，赵建华等译 其他 A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. 2nd edition, Addison-Wesley, 2007 A. W. Appel. Modern Compiler Implementation in C/Java/ML. Cambridge University Press.

评分标准 书面作业：30% 约6次 抄袭/被抄袭：0分 期末考试（闭卷）：70%

编译器概述 源程序 编译器 目标程序

编译器的结构 编译器从逻辑上可以分成若干个步骤（Phase） 每个步骤把源程序从一种表示变换成另一种表示

符号表 词法分析 机器无关的代码优化 语法分析 代码生成 语义分析 机器相关的代码优化 中间代码生成 源程序字符流 中间表示 词法单元流 目标机器代码 词法单元流 语法树 中间表示 符号表

编译器的结构 前端（front end） 后端（back end） 中间端（middle end） 源程序  中间表示 收集源程序的信息，放入符号表 检查程序中可能存在的语法、语义错误 后端（back end） 借助符号表的信息，中间表示  目标机器代码 中间端（middle end） 中间表示上的优化，便于生成更好的目标程序 为什么需要中间表示？

符号表（symbol table） 记录源程序中使用的变量的名字，收集各种属性 在词法分析/语法分析时生成，每个变量都有一 个记录条目 类型 作用域 过程名字：参数数量、参数类型、返回值类型等 在词法分析/语法分析时生成，每个变量都有一 个记录条目 可由编译器的各个步骤使用 变量名 x y z . . . 1 2 3 属性

词法分析（lexical analysis） id, 1 = id, 2 + id, 3  60 position = initial + rate  60  字符流 符 号 表 position initial rate . . . 1 2 3 id, 1：id是表示标识符（identifier）的抽象符号，1指向符号表中的第一个条目  词法单元流

语法分析（syntax analysis, 也称作parsing）  词法单元流 语法分析 id, 1 = id, 2 + id, 3  60 = +  60 id, 1 id, 2 id, 3 符 号 表 position initial rate . . . 1 2 3  语法树 给出词法单元流的语法结构

表达式的语法 initial + rate * 60的语法树 任何一个标识符都是表 达式 任何一个数都是表达式 如果e1和e2都是表达式， 那么 e1 + e2 e1 * e2 (e1) 也都是表达式 表达式 标识符 (initial) (rate) 数 (60) * + 先介绍语法，然后才介绍语法分析。 initial + rate * 60的语法树

语义分析（semantic analysis） 使用语法树和符号表中的信息，检查源程序是否 满足语言定义的语义约束 类型检查 自动类型转换

 语法树 语义分析 = +  60 id, 1 id, 2 id, 3 符 号 表 position 假设rate被声明为string类型 语义分析 = +  60 id, 1 id, 2 id, 3  语法树 符 号 表 position initial rate . . . 1 2 3 类型错误

 语法树  语法树 语义分析 = +  60 id, 1 id, 2 id, 3 inttofloat 假设position, initial, rate被声明为float类型 语义分析 = +  60 id, 1 id, 2 id, 3 inttofloat  语法树 符 号 表 position initial rate . . . 1 2 3  语法树

中间代码生成 语法树  类机器语言的中间表示 一个编译器可能构造多个中间表示 中间表示应满足： 三地址代码 语法树可视为一种中间表示 易于生成 易于翻译成目标机器语言 三地址代码 类似汇编语言，每个指令最多包含三个运算分量，每 个运算分量像一个寄存器

 语法树  三地址中间代码 中间代码生成 t1 = inttofloat(60) t2 = id3  t1 t3 = id2 + t2 = +  inttofloat id, 1 id, 2 id, 3 60  语法树 符 号 表 position initial rate . . . 1 2 3  三地址中间代码 t1, t2, t3：编译器生成的临时名字

机器无关的代码优化 改进中间代码，以便生成更好的目标代码 有些编译器会做许多代码优化工作 “更好”：运行的更快、占用更少的内存等 常量传播，死代码消除，….

 三地址中间代码  三地址中间代码 代码优化 t1 = inttofloat(60) t2 = id3  t1 id1 = id2 + t1  三地址中间代码 符 号 表 position initial rate . . . 1 2 3  三地址中间代码

代码生成 把中间表示形式映射到目标语言 寄存器分配 指令选择

 三地址中间代码  汇编代码 代码生成 LDF R2, id3 MULF R2, R2, #60.0 LDF R1, id2 ADDF R1, R1, R2 STF id1, R1 t1 = id3 * 60.0 id1 = id2 + t1  三地址中间代码 符 号 表 position initial rate . . . 1 2 3  汇编代码

符号表 词法分析 机器无关的代码优化 语法分析 代码生成 语义分析 机器相关的代码优化 中间代码生成 源程序字符流 中间表示 词法单元流 目标机器代码 词法单元流 语法树 中间表示 符号表

编译器的趟（Pass） 步骤（Phase）是逻辑组织方式 实践中，多个步骤可以组合成一趟 每趟读入一个文件，产生一个输出文件 例如，词法分析+语法分析+语义分析+中间代码生成， 可以组合成一趟 “趟”和具体的实现相关

编译器 vs 解释器 解释器不生成目标代码，而是直接执行源程序所 指定的运算 源程序 源程序 程序 输入 程序 输出 编译器 解释器 目标程序 程序 输入 程序 输出

编译器设计的考虑 高级语言通常易于编程，抽象程度高 源程序 1.编译器需支持新的语言特征 （如多态，类，模板，…） 目标程序 源程序 1.编译器需支持新的语言特征 （如多态，类，模板，…） 3.编译器需保证翻译的正确性（保持源程序的语义） 底层语言直接控制机器，可以很高效，但难编写、难维护、易出错 2.编译器需利用新的硬件特性 （如多核，大规模并行，…）

验证编译器（verified compiler） 数学严格证明编译过程保持源程序的语义 源语言C，目标语言Assembly http://compcert.inria.fr/

编译技术的应用 高级语言的实现 高级编程语言易于编程，但程序运行较慢 低级语言编程时可实施更有效的控制方式，得到更有 效的代码，但难编写、易出错、难维护 通过降低高级语言的执行开销，编译器可以推动这些 高级语言的使用

编译技术的应用 高级语言的实现 每一轮编程语言新特征的出现都刺激编译优化技术的 新研究 C支持用户定义的聚合数据类型和高级控制流，如数 组和记录、循环和过程调用 编译器：数据流优化，生成高效的数据访问代码 Java内置垃圾收集机制来自动地释放那些不再使用的 内存 编译器：优化对象分配，高效的垃圾收集算法

编译技术的应用 针对计算机体系结构的优化 计算机体系结构的迅速演化对新的编译器技术提出越 来越多的需求 并行化 内存分层 编译器重新整理指令，使得指令级并行更有效 编译器从传统的串行程序自动生成并行代码，使之运行于 多处理器上 内存分层 编译器优化历来集中在优化处理器的执行上，但是现在更 强调要使内存分层更有效

编译技术的应用 新计算机体系结构的设计 现在计算机系统的性能不仅仅取决于它的原始速度， 还取决于编译器是否能生成充分利用其特征的代码 在现代计算机体系结构的研究中，在处理器的设计阶 段就开发编译器，并将编译生成的代码在模拟器上运 行，以评价拟采用体系结构的特征 编译器技术影响计算机体系结构设计的一个著名例子 是精简指令集计算机（RISC）的发明

编译技术的应用 程序翻译 二进制翻译 数据库查询解释器 编译器技术可用于把一种机器的二进制代码翻译成另一种 机器的代码，以运行原先为别的指令集编译的代码 数据库查询解释器 数据库查询由一些谓词组成，这些谓词由包含关系运算的 布尔表达式组成，可以被解释执行,也可以被编译成搜索数 据库的命令

编译技术的应用 提高软件开发效率的工具 源于编译器中代码优化技术的程序分析一直在改进软 件开发效率 类型检查 边界检查 内存管理 捕捉程序中的前后不一致 边界检查 数据流分析技术可用来定位缓冲区溢出 内存管理 自动的内存管理删除内存泄漏等内存管理错误

符号表 词法分析 机器无关的代码优化 语法分析 代码生成 语义分析 机器相关的代码优化 中间代码生成 源程序字符流 中间表示 词法单元流 目标机器代码 词法单元流 语法树 中间表示 符号表