邱锡鹏 复旦大学计算机科学技术学院

Text Books  “Dragon book”  Compilers: Principles, Techniques, and Tools (2nd Edition)  Alfred V. Aho;Monica S. Lam;Ravi Sethi;Jeffrey D. Ullman  Publisher: Addison-Wesley Pub Co  “Tiger Book”  现代编译原理 --C 语言描述 ( 英文影 印版 )  Andrew W. Appel, Maia Ginsburg  出版社 : 人民邮电出版社 出版日 期 :2005 年 9 月

成绩 程序项目 20% （ C++, Java ） 6-8 次课后作业 10% 可以用电子版写好，交打印稿 DOT Language) 期中考试 35% 四月底 期末考试 35% 六月底

编译简介 本课程介绍程序设计语言编译程序构造的基本原理和 基本实现技术. 词法分析 语法分析 中间代码产生 优化 目标代码产生 编译器自动构造工具

高级语 言程序 机器语 言程序 结果 编译 程序 翻译 运行 什么是编译程序？  编译程序 (compiler)  把某一种高级语言程序等价地转换成另一种低级 语言程序 ( 如汇编语言或机器语言程序 ) 的程序 诊断编译程序优化编译程序 交叉编译程序可变目标编译程序 初始数据

语言是什么？ 不同语言的区别是什 么？

源语言 程序 目标语 言程序 翻译 程序 翻译 什么是编译程序？ 把某一种语言程序 ( 称为源语言程序 ) 等价地转换成另 一种语言程序 ( 称为目标语言程序 ) 的程序。 错误信息

程序语言 程序设计语言：用来编写计算机程序的语言。 过程式语言 Fortran,Pascal,C 函数式语言 Lisp 逻辑式语言 Prolog 对象式语言 C++, Java, C# 汇编语言 机器语言 程序设计语言 高级语言低级语言：面向机器的语言

什么是编译程序？  解释程序 (Interpreter)  把源语言写的源程序作为输入，但不产生目标程序， 而是边解释边执行源程序本身 源程序结果 解释 程序 解释执行 初始数据

编译程序 vs 解释程序 解释器是源程序的执行系统 编译器是源程序的转换系统 编译程序要比解释程序高效

二. 编译过程 把英文翻译为中文 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。

编译过程 编译程序的工作一般分为五个阶段 : 词法分析 语法分析 中间代码产生 优化 目标代码产生

四元式 单词符号语法单位 四元式 目标代码 词法分析器 语法分析器 语义分析与中间代码 生成器 中间代码优化 源程序 表格管理表格管理 出错处理出错处理 目标代码生成器

1. 词法分析 (Lexical Analysis)  任务 :  输入源程序，对构成源程序的字符串进行扫描和分解识 别出一个个单词符号。  依循的原则：构词规则  删除无用符合（空格符，回车符）  删除注释  检查词法错误  描述工具：正则表达式和有限自动机 FOR I := 1 TO 100 DO 保留字 标识符 等符 整常数 保留字 整常数 保留字 例子： Z = X * Y;

2. 语法分析 (Syntax Analysis) 任务 : 在词法分析的基础上，根据语言的语法规则把单词符号 串分解成各类语法单位。 检查语法错误 依循的原则：语法规则 描述工具：上下文无关文法

生成语法树 例子： Z := X * Y 算术表达式，赋值语句（层次结构分析）

语义分析 (Semantic Analysis)  英语里的语义分析： Jack said Jerry left his assignment at home.  What does “his” refer to? Jack or Jerry? { int Jack = 3; { int Jack = 4; System.out.println(Jack); } 程序语言用严格的规则 来消除二义性！

3. 中间代码生成 (Intermediate Code Generation)  任务 :  对各类不同语法范畴按语言的语义进行初步翻译。  依循的原则：  语义规则  中间代码 :  三元式、四元式、抽象语法树等  Z=X * Y 翻译成四元式为 : * Y T1 + X T1 T2 = T2 - Z

4. 优化 (Optimization)  任务  对于前阶段产生的中间代码进行加工变换，以期在最后阶段 产生更高效的目标代码。  依循的原则  程序的等价变换规则  优化标准  空间指标  时间指标  优化方式  局部优化  全局优化

优化 Ex: for(k = 1;k<100;k++){ x = i+1; m = i+10*k; n = j+10*k; }

中间代码（一） 序号 OPROPN1 OPN2 RESULT 注释 (1):=1 K K=1 (2)j<100 K (10) if (100<K) goto (10) (3)+I 1 X X=I+1 (4)*10 K T1 T1=10*K (5)+I T1 M M=I+T1 (6)*10 K T2 T2=10*K (7)+J T2 N N=J+T2 (8)+K 1 K K=K+1 (9)j (2) goto (2) (10)

转换后的等价代码（二） 序号 OPROPN1OPN2 RESULT 注释 (1)+I 1 X X:=I+1 (2):=I M M:=I (3):=J N N:=J (4):=1 K K:=1 (5)j<100 K(10) if (100<K) goto (10) (6)+M 10 M M:=M+10 (7)+N 10 N N:=N+10 (8)+K 1 K K:=K+1 (9)j(5) goto (5) (10)

5. 目标代码产生 任务 把中间代码变换成特定机器上的目标代码。 通常为汇编 依赖于硬件系统结构和机器指令的含义 目标代码三种形式 : 绝对指令代码 : 无需连接可直接运行 可重新定位指令代码 : 需连接装配后运行 汇编指令代码 : 需要进行汇编

5. 目标代码产生  例 : b=a+2 MOV a, R1 ADD #2, R1 MOV R1, b * * L=

中间语言 (Intermediate Languages) 许多编译器在连续的中间形式进行转换 除了源语言和目标语言，中间的形式都是中间语言 中间语言一般从低到高排序 最高是原语言 最低是机器语言

四元式 单词符号语法单位 四元式 目标代码 词法分析器 语法分析器 语义分析与中间代码 生成器 优化段 源程序 表格管理表格管理 出错处理出错处理 目标代码生成器

错误处理 (Error Handler) 出错处理程序：发现源程序中的错误，把有关错误信 息（位置、类型）报告给用户 词法错误 5x ， 256. 语法错误 X=(A*(B+C)+1 语义错误 静态语义错误：上下文有关的错误（重复声明） 动态语义错误：下标超界，除 0

2. 符号表和符号表管理 (Symbol Table Management) 常见的符号表 : 符号名表，常数表，标号表，入口名表， 四元式表和过程引用表。 格式 : 名字 信息

例 : PASCAL 程序段： PROCEDURE INCWAP(M ， N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END

遍 (pass) 所谓 " 遍 " ， 就是对源程序或源程序的中间表示从头到 尾扫描一次。 阶段与遍是不同的概念。一遍可以由若干段组成，一 个阶段也可以分若干遍来完成。

编译前端与后端  编译前端：与源语言有关，如词法分析，语法分析， 语义分析与中间代码产生，与机器无关的优化  编译后端 ：与目标机有关，与目标机有关的优化，目 标代码产生  优点：减少对内存容量的要求，程序逻辑结构清晰 ; 优 化更充分，有利于移植。  不足 : 编译程序运行的效率低 源语言中间语言目标语言 前端后端

JAVA 语言 操作系统平台 Java 虚拟机 ( 解释器 ) Java 编译器 Java 源程序 (.java) Java 虚拟机代码 (.class) 解释执行

.NET Framework 与 VS.NET Operating System Common Language Runtime ADO.NET: Data and XML ASP.NET: Web Services & Web Forms Windows Forms Common Language Specification Visual Studio.NET VBC++C#JScript…

四. 编译程序与程序设计环境 程序设计环境 编辑程序 编译程序 连接程序 调试工具 集成化的程序设计环境

与编译器相关的程序  解释程序  汇编程序  连接程序  装入程序  预处理器  编辑器  调试程序  描述器  项目管理程序

五. 编译程序生成 设计编译程序应考虑：可移植性、可维护性、可扩展 性 编译程序的性能：可靠性、编译速度、目标代码的运 行速度、空间节省 设计编译程序的过程： 确定编译程序的组织结构和各部分的功能、方案 确定使用工具、编写各组成部分

五. 编译程序生成 编译器中的主要数据结构： 记号（ token ） 语法树（ syntax tree ） 符号表（ symbol table ） 常数表（ literal table ） 中间代码（ intermediate code ） 临时文件（ temporary file ）

五. 编译程序生成 编译工具的选择 汇编 已有编译程序的高级语言 自动化工具

以汇编语言和机器语言为工具 优点 : 可以针对具体的机器，充分发挥计算机的系统 功能。生成的程序效率高。 缺点 : 程序难读、难写、易出错、难维护、生产的效 率低。

高级语言书写  优点 : 程序易读、易理解、容易维护、生产的效率高。  缺点 : 难以充分发挥计算机的系统功能，生成的程序 效率低。

移植法 假设在 A 机上已有 L 语言的编译程序，想在 B 机上开发 一个 L 语言的编译程序 直接转换法：将 L 语言编译程序的 A 机代码直接转换成 B 机代码 交叉编译：在 A 机上产生 B 机的目标代码

问题 1 ： A 机上有一个 C 语言的编译器，是否可利用此 编译器实现 B 机上的 C 语言编译器？ 解决： 用 C 语言写一个 B 机上的编译程序（ P0 ： C － >B) 用 A 机上的 C 编译器（ P1 ）编译 P0 ，得到可在 A 机上运行 的 “B 机上的编译器 ” （ P2 ： C － >B ） 在 A 机上用 P2 编译 P0 ，得到可在 B 机上运行的 C 编译器 （ P3 ）

L 1 +L L n … L 1 +L 2 自展技术 Li 语言能写出 Li+1 语言的编译程序 L1L1

编译程序自动产生 编译程序书写系统 FLEX 词法分析程序产生器 YACC(Bison) 语法分析程序产生器 更多的自动生成工具： Javacc,ANTLR,JFlex 等 编译程序 自动产生器 L 语言的语法描述 语义描述 目标语言 或机器描述 L 语言的 编译程序

编译发展 程序语言 机器结构 语言理论 算法 软件工程

（程序）语言 输入和输出 目标 怎样给计算机发出指令 怎样使计算机有效地执行指令

（程序）语言 自然语言 中文，英文 我们的最终目标，但是远没有实现！ 程序语言 汇编,Fortran, Basic, C, C++, Java, C#

程序语言 程序语言应当有如下特性： 无二义性 准确性 简洁性 表达性 ？

机器结构 16 位、 32 位、 64 位 超线程 并行编译 SIMD MIMD 分布式计算

其他 程序语言 机器结构 语言理论 算法 软件工程

编译器现状 (Compiler Today) 总体框架保持不变 但是各部分的重要程度与 Fortran 相比已经发生了很多 变化 早期：词法、语法分析是更复杂、高代价的 目前：着重点已经转到其他阶段的优化，而词法、语法 分析相对廉价的

关于学习编译原理 构造编译程序的前提 : 掌握源语言 掌握目标语言 掌握编译方法

六. 关于学习编译原理 意义 : 学习编译程序构造原理，技术 更好地理解高级语言 编译的原理和方法有助于构造一些实用的工具