编译原理 编译原理

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

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

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

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

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

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

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

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

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

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

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

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

中间代码（一） 序号 OPR OPN1 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) 400次加法 200次乘法 编译原理

转换后的等价代码（二） 序号 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 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) 301次加法 编译原理

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

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

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 0100 01 00 00010011 编译原理

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

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

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

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

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

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

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

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

编译原理

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

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

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

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

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

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

.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提供了一个简单易用、整合企业建模工具的综合开发工具。好处：降低总拥有成本。 编译原理

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

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

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

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

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

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