编译原理 编译原理.

Presentation on theme: "编译原理 编译原理."— Presentation transcript:

1 编译原理 编译原理

2 第一章 引 论 本课程介绍程序设计语言编译程序构造的基本原理和基本实现技术. 编译原理

3 第一章 引 论 编译理论与方法 计算机科学与技术中理论和实践相结合的最好典范 ACM 图灵奖，授予在计算机技术领域作出突出贡献的科学家
第一章 引 论 编译理论与方法 计算机科学与技术中理论和实践相结合的最好典范 ACM 图灵奖，授予在计算机技术领域作出突出贡献的科学家 程序设计语言、编译理论与方法约占1/3 编译原理

4 一. 什么是编译程序 翻译程序 把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序 源语言程序
编译原理

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

6 一. 什么是编译程序 解释程序 把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身 源程序 结果 解释 程序 解释执行
编译原理

7 编译程序 vs. 解释程序 编译 解释 编译原理

8 二. 编译过程 词法分析 把英文翻译为中文 语法分析 中间代码产生 优化 目标代码产生 识别出句子中的一个个单词； 分析句子的语法结构；
二. 编译过程 词法分析 把英文翻译为中文 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。 语法分析 中间代码产生 优化 目标代码产生 编译原理

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

10 1. 词法分析 任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。 依循的原则：构词规则 描述工具：有限自动机
FOR I := TO DO 保留字 标识符 等符 整常数 保留字 整常数 保留字 编译原理

11 2. 语法分析 任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。 依循的原则：语法规则 描述工具：上下文无关文法
Z := X * Y 算术表达式，赋值语句 编译原理

12 3. 中间代码产生 任务:对各类不同语法范畴按语言的语义进行初步翻译。 依循的原则：语义规则 中间代码:三元式，四元式，树形结构等
Z:=X * Y 翻译成四元式为 (1) * Y T1 (2) X T1 T2 (3) := T _ Z 编译原理

13 4. 优化 任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。 依循的原则：程序的等价变换规则
FOR K:=1 TO 100 DO BEGIN X:=I+1; M := I + 10 * K; N := J + 10 * K; END 编译原理

14 中间代码（一） 序号 OPR OPN1 OPN2 RESULT 注释 (1) := 1 K K:=1
(2) j< 100 K (10) if (100<K) goto (10) (3) + I 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 K K:=K+1 (9) j (2) goto (2) (10) 400次加法 200次乘法 编译原理

15 转换后的等价代码（二） 序号 OPR OPN1 OPN2 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 M M:=M+10 (7) + N N N:=N+10 (8) + K 1 K K:=K+1 (9) j (5) goto (5) (10) 301次加法 编译原理

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

17 模块A … a 模块B … b 模块C … c 模块B … b 模块C … c 模块A … a 模块D … 模块C … c 模块A … a
编译原理

18 5. 目标代码产生 例: b=a+2 MOV a, R1 ADD #2, R1 MOV R1, b
* * L= 编译原理

19 三. 编译程序结构 编译程序总框 编译原理

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

21 2. 表格和表格管理 常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。 格式: 名字 信息 编译原理

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

23 PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN
K:=M+1; M:=N+4; N:=K; END. 编译原理

24 PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN
K:=M+1; M:=N+4; N:=K; END. 编译原理

25 PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN
K:=M+1; M:=N+4; N:=K; END. 编译原理

26 PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN
K:=M+1; M:=N+4; N:=K; END. 编译原理

27 编译原理

28 PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN
K:=M+1; M:=N+4; N:=K; END. 编译原理

29 3. 出错处理 出错处理程序：发现源程序中的错误，把有关错误信息报告给用户 语法错误 语义错误 编译原理

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

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

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

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

34 .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 VB C++ C# JScript … VS.NET是在.NET Framework上工作的最佳选择。 最上一层，支持多种语言，只要支持通用语言规范的语言它都支持。 ASP .NET是基于Web开发技术的核心，Windows Forms类似一个弱化的MFC（企业及网络应用中，Rich Client UI不再是重要组成部分，基于Web的方式将成为主流） ADO.NET提供全面的数据及XML访问技术，微软的UDA（统一数据访问）思想在这里充分得到体现。Database、XML在这里得到充分集成，随着SQL Server下一版本的推出，XML与数据库将充分融合成为XML DB。 CLR是.NET Framework为所有的语言支持垃圾收集，线程管理等功能 OS VS .NET则在一个整合的IDE中为.NET Framework提供了一个简单易用、整合企业建模工具的综合开发工具。好处：降低总拥有成本。 编译原理

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

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

37 五.编译程序生成 高级语言书写 利用已有的某种语言的编译程序实现另一语言的编译程序。 同一台机器 不同的语言 L2语言 A代码 P2:
编译原理

38 五.编译程序生成 移植方法 把一种机器上的编译程序移植到另一种机器上。 同一种语言不同的机器 L语言 B代码 P2: L语言 B代码 P2:
A代码 L语言 A代码 P1: 同一种语言不同的机器 编译原理

39 五.编译程序生成 自展技术 L1+L2+...+Ln … L1+L2 L1 编译原理

40 五.编译程序生成 编译程序自动产生 编译程序-编译程序，编译程序书写系统 L语言的语法描述 编译程序 L语言的 语义描述 自动产生器
目标语言 或机器描述 LEX 词法分析程序产生器 YACC 语法分析程序产生器 编译原理