Download presentation
Presentation is loading. Please wait.
1
邱锡鹏 复旦大学计算机科学技术学院 xpqiu@fudan.edu.cn
2
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 月
3
成绩 程序项目 20% （ C++, Java ） 6-8 次课后作业 10% 可以用电子版写好，交打印稿 http://www.graphviz.org/(The DOT Language) 期中考试 35% 四月底 期末考试 35% 六月底
4
编译简介 本课程介绍程序设计语言编译程序构造的基本原理和 基本实现技术. 词法分析 语法分析 中间代码产生 优化 目标代码产生 编译器自动构造工具
5
高级语 言程序 机器语 言程序 结果 编译 程序 翻译 运行 什么是编译程序？ 编译程序 (compiler) 把某一种高级语言程序等价地转换成另一种低级 语言程序 ( 如汇编语言或机器语言程序 ) 的程序 诊断编译程序优化编译程序 交叉编译程序可变目标编译程序 初始数据
6
语言是什么？ 不同语言的区别是什 么？
7
源语言 程序 目标语 言程序 翻译 程序 翻译 什么是编译程序？ 把某一种语言程序 ( 称为源语言程序 ) 等价地转换成另 一种语言程序 ( 称为目标语言程序 ) 的程序。 错误信息
8
程序语言 程序设计语言：用来编写计算机程序的语言。 过程式语言 Fortran,Pascal,C 函数式语言 Lisp 逻辑式语言 Prolog 对象式语言 C++, Java, C# 汇编语言 机器语言 程序设计语言 高级语言低级语言：面向机器的语言
9
什么是编译程序？ 解释程序 (Interpreter) 把源语言写的源程序作为输入，但不产生目标程序， 而是边解释边执行源程序本身 源程序结果 解释 程序 解释执行 初始数据
10
编译程序 vs 解释程序 解释器是源程序的执行系统 编译器是源程序的转换系统 编译程序要比解释程序高效
11
二. 编译过程 把英文翻译为中文 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。
12
编译过程 编译程序的工作一般分为五个阶段 : 词法分析 语法分析 中间代码产生 优化 目标代码产生
13
四元式 单词符号语法单位 四元式 目标代码 词法分析器 语法分析器 语义分析与中间代码 生成器 中间代码优化 源程序 表格管理表格管理 出错处理出错处理 目标代码生成器
14
1. 词法分析 (Lexical Analysis) 任务 : 输入源程序，对构成源程序的字符串进行扫描和分解识 别出一个个单词符号。 依循的原则：构词规则 删除无用符合（空格符，回车符） 删除注释 检查词法错误 描述工具：正则表达式和有限自动机 FOR I := 1 TO 100 DO 保留字 标识符 等符 整常数 保留字 整常数 保留字 例子： Z = X + 0.618 * Y;
15
2. 语法分析 (Syntax Analysis) 任务 : 在词法分析的基础上，根据语言的语法规则把单词符号 串分解成各类语法单位。 检查语法错误 依循的原则：语法规则 描述工具：上下文无关文法
16
生成语法树 例子： Z := X + 0.618 * Y 算术表达式，赋值语句（层次结构分析）
17
语义分析 (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); } 程序语言用严格的规则 来消除二义性！
18
3. 中间代码生成 (Intermediate Code Generation) 任务 : 对各类不同语法范畴按语言的语义进行初步翻译。 依循的原则： 语义规则 中间代码 : 三元式、四元式、抽象语法树等 Z=X + 0.618 * Y 翻译成四元式为 : * 0.618 Y T1 + X T1 T2 = T2 - Z
19
4. 优化 (Optimization) 任务 对于前阶段产生的中间代码进行加工变换，以期在最后阶段 产生更高效的目标代码。 依循的原则 程序的等价变换规则 优化标准 空间指标 时间指标 优化方式 局部优化 全局优化
20
优化 Ex: for(k = 1;k<100;k++){ x = i+1; m = i+10*k; n = j+10*k; }
21
中间代码（一） 序号 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)
22
转换后的等价代码（二） 序号 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)
23
5. 目标代码产生 任务 把中间代码变换成特定机器上的目标代码。 通常为汇编 依赖于硬件系统结构和机器指令的含义 目标代码三种形式 : 绝对指令代码 : 无需连接可直接运行 可重新定位指令代码 : 需连接装配后运行 汇编指令代码 : 需要进行汇编
24
5. 目标代码产生 例 : b=a+2 MOV a, R1 ADD #2, R1 MOV R1, b 0001 01 00 00000000 * 0011 01 10 00000010 0100 01 00 00000100 * L=00001111 0001 01 00 00001111 0011 01 10 00000010 0100 01 00 00010011
25
中间语言 (Intermediate Languages) 许多编译器在连续的中间形式进行转换 除了源语言和目标语言，中间的形式都是中间语言 中间语言一般从低到高排序 最高是原语言 最低是机器语言
26
四元式 单词符号语法单位 四元式 目标代码 词法分析器 语法分析器 语义分析与中间代码 生成器 优化段 源程序 表格管理表格管理 出错处理出错处理 目标代码生成器
27
错误处理 (Error Handler) 出错处理程序：发现源程序中的错误，把有关错误信 息（位置、类型）报告给用户 词法错误 5x ， 256. 语法错误 X=(A*(B+C)+1 语义错误 静态语义错误：上下文有关的错误（重复声明） 动态语义错误：下标超界，除 0
28
2. 符号表和符号表管理 (Symbol Table Management) 常见的符号表 : 符号名表，常数表，标号表，入口名表， 四元式表和过程引用表。 格式 : 名字 信息
29
例 : PASCAL 程序段： PROCEDURE INCWAP(M ， N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END
32
遍 (pass) 所谓 " 遍 " ， 就是对源程序或源程序的中间表示从头到 尾扫描一次。 阶段与遍是不同的概念。一遍可以由若干段组成，一 个阶段也可以分若干遍来完成。
33
编译前端与后端 编译前端：与源语言有关，如词法分析，语法分析， 语义分析与中间代码产生，与机器无关的优化 编译后端 ：与目标机有关，与目标机有关的优化，目 标代码产生 优点：减少对内存容量的要求，程序逻辑结构清晰 ; 优 化更充分，有利于移植。 不足 : 编译程序运行的效率低 源语言中间语言目标语言 前端后端
34
JAVA 语言 操作系统平台 Java 虚拟机 ( 解释器 ) Java 编译器 Java 源程序 (.java) Java 虚拟机代码 (.class) 解释执行
35
.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…
36
四. 编译程序与程序设计环境 程序设计环境 编辑程序 编译程序 连接程序 调试工具 集成化的程序设计环境
37
与编译器相关的程序 解释程序 汇编程序 连接程序 装入程序 预处理器 编辑器 调试程序 描述器 项目管理程序
38
五. 编译程序生成 设计编译程序应考虑：可移植性、可维护性、可扩展 性 编译程序的性能：可靠性、编译速度、目标代码的运 行速度、空间节省 设计编译程序的过程： 确定编译程序的组织结构和各部分的功能、方案 确定使用工具、编写各组成部分
39
五. 编译程序生成 编译器中的主要数据结构： 记号（ token ） 语法树（ syntax tree ） 符号表（ symbol table ） 常数表（ literal table ） 中间代码（ intermediate code ） 临时文件（ temporary file ）
40
五. 编译程序生成 编译工具的选择 汇编 已有编译程序的高级语言 自动化工具
41
以汇编语言和机器语言为工具 优点 : 可以针对具体的机器，充分发挥计算机的系统 功能。生成的程序效率高。 缺点 : 程序难读、难写、易出错、难维护、生产的效 率低。
42
高级语言书写 优点 : 程序易读、易理解、容易维护、生产的效率高。 缺点 : 难以充分发挥计算机的系统功能，生成的程序 效率低。
43
移植法 假设在 A 机上已有 L 语言的编译程序，想在 B 机上开发 一个 L 语言的编译程序 直接转换法：将 L 语言编译程序的 A 机代码直接转换成 B 机代码 交叉编译：在 A 机上产生 B 机的目标代码
44
问题 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 ）
45
L 1 +L 2 +...+L n … L 1 +L 2 自展技术 Li 语言能写出 Li+1 语言的编译程序 L1L1
46
编译程序自动产生 编译程序书写系统 FLEX 词法分析程序产生器 YACC(Bison) 语法分析程序产生器 更多的自动生成工具： Javacc,ANTLR,JFlex 等 编译程序 自动产生器 L 语言的语法描述 语义描述 目标语言 或机器描述 L 语言的 编译程序
47
编译发展 程序语言 机器结构 语言理论 算法 软件工程
48
（程序）语言 输入和输出 目标 怎样给计算机发出指令 怎样使计算机有效地执行指令
49
（程序）语言 自然语言 中文，英文 我们的最终目标，但是远没有实现！ 程序语言 汇编,Fortran, Basic, C, C++, Java, C#
50
程序语言 程序语言应当有如下特性： 无二义性 准确性 简洁性 表达性 ？
51
机器结构 16 位、 32 位、 64 位 超线程 并行编译 SIMD MIMD 分布式计算
52
其他 程序语言 机器结构 语言理论 算法 软件工程
53
编译器现状 (Compiler Today) 总体框架保持不变 但是各部分的重要程度与 Fortran 相比已经发生了很多 变化 早期：词法、语法分析是更复杂、高代价的 目前：着重点已经转到其他阶段的优化，而词法、语法 分析相对廉价的
54
关于学习编译原理 构造编译程序的前提 : 掌握源语言 掌握目标语言 掌握编译方法
55
六. 关于学习编译原理 意义 : 学习编译程序构造原理，技术 更好地理解高级语言 编译的原理和方法有助于构造一些实用的工具
Similar presentations
