编译原理 中南大学软件学院 陈志刚

《编译原理》课程简介 地位 计算机专业的一门核心课程 编译程序是计算机的重要系统软件，是高级程序设计语言的支撑基础 课程主要介绍设计和构造编译程序的基本原理和方法 2019/11/10 中南大学软件学院

本门课程的要求 了解计算机高级语言流程序被计算机接受、扫描、词法分析、语法分析、语义解释执行的原理与过程； 掌握编译的原理和基本算法、各种概念和语言描述。 2019/11/10 中南大学软件学院

用途与作用 这是本专业应具备的基本知识，就像其他原理一样，是基础。 三大系统软件： OS、DBMS、Compiling System 开发大型系统软件、工具软件的需要。 看资料、写论文的需要 2019/11/10 中南大学软件学院

《编译原理》前导课程 前导课程及涉及内容 组成原理——计算机组成及结构 微机原理——汇编语言与机器语言 离散数学——推理知识及其完备性 数据结构——树、表等的表示与实现 操作系统——提供虚拟机和系统调用 高级程序设计语言——语言定义和编程 2019/11/10 中南大学软件学院

教学目的 掌握编译的基本理论、常用的编译技术，了解编译过程及编译系统的构造 编译程序一般由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、目标代码生成程序、代码优化程序、表格管理和出错处理程序等成分构成。通过课程的学习应掌握各个成分的功能和设计原则，以及在编译阶段的逻辑关系。理解他们怎样作为一个整体完成编译任务。 能运用所学技术解决实际问题，能独立编写一个小型编译系统 2019/11/10 中南大学软件学院

意义: 学习编译程序构造原理，技术 更好地理解高级语言 编译的原理和方法有助于构造一些实用的工具 2019/11/10 中南大学软件学院

课程特点: 理解性 技术性 考核： 作业及上机实习：30% 笔试：70% 2019/11/10 中南大学软件学院

1.1 基本概念 1.2 编译过程 1.3 编译程序与程序设计环境 1.4 高级语言程序简介 第一章 引 论 1.1 基本概念 1.2 编译过程 1.3 编译程序与程序设计环境 1.4 高级语言程序简介

1.1 基本概念 一、发展 机器语言→汇编语言→高级语言→工具语言 第1代1GL 2GL 3GL 4GL 机器识别：0|1 代码 相去甚远 机器识别：0|1 代码 相去甚远 2019/11/10 中南大学软件学院

1.1 基本概念 二、翻译程序 把某一种语言程序(称为源语言程序)等价地转换成另一种语言程序(称为目标语言程序)的程序。如：中英互译系统、DBMS语言(DDL,DCL) 源语言程序 目标语言程序 翻译 程序 2019/11/10 中南大学软件学院

1.1 基本概念 三、编译程序(compiler) 把某一种高级语言程序等价地转换成另一种低级语言程序(如汇编语言或机器语言程序)的程序。 编译程序分类 诊断编译程序&优化编译程序 交叉编译程序&可变目标编译程序 高级语言程序 机器语言程序 结果 编译 程序 翻译 运行 2019/11/10 中南大学软件学院

1.1 基本概念 四、解释程序 把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。 源程序 结果 解释 程序 解释执行 2019/11/10 中南大学软件学院

编译程序 vs. 解释程序 编译 解释 2019/11/10 中南大学软件学院

1.1 基本概念 五、执行高级语言程序的步骤 把高级语言程序编译成低级语言目标程序 执行目标程序 2019/11/10 中南大学软件学院

1.2 编译过程 把英文翻译为中文 识别出句子中的一个个单词； 分析句子的语法结构； 根据句子的含义进行初步翻译； 对译文进行修饰； 写出最后的译文。 2019/11/10 中南大学软件学院

1.2 编译过程 一、高级语言程序的编译过程 词法分析 语法分析 中间代码产生 优化 目标代码生成 作用、实现者 (并非每个编译过程均有以上全过程) 2019/11/10 中南大学软件学院

1. 词法分析 任务: 输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号。 依循的原则：构词规则 描述工具：正规式和有限自动机 FOR I := 1 TO 100 DO 保留字 标识符 等符 整常数 保留字 整常数 保留字 2019/11/10 中南大学软件学院

2. 语法分析 任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。 依循的原则：语法规则 描述工具：上下文无关文法 Z := X + 0.618 * Y 算术表达式，赋值语句（层次结构分析） 2019/11/10 中南大学软件学院

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

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

中间代码（一） 序号 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) 2019/11/10 中南大学软件学院

转换后的等价代码（二） 序号 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) 2019/11/10 中南大学软件学院

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

模块A … a 模块B … b 模块C … c 模块B … b 模块C … c 模块A … a 模块D … 模块C … c 模块A … a 2019/11/10 中南大学软件学院

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 2019/11/10 中南大学软件学院

1.2 编译过程 二、编译程序的逻辑结构 2019/11/10 中南大学软件学院

1.2 编译过程 三、表格与表格管理 常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。 格式: 名字 信息 2019/11/10 中南大学软件学院

例: PASCAL程序段： PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END. 2019/11/10 中南大学软件学院

2019/11/10 中南大学软件学院

2019/11/10 中南大学软件学院

1.2 编译过程 四、出错处理 出错处理程序：发现源程序中的错误，把有关错误信息报告给用户 语法错误 语义错误 2019/11/10 中南大学软件学院

1.2 编译过程 五、遍(Pass) 所谓“遍”，对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 每遍由从外存上获得前一遍的工作结果开始，完成工作后，把结果存在外存上。每遍工作完成后所占用的存贮空间大部分被释放。 例：IBM Pascal： Pass1, Pass2 Link？ 生成可重定位代码。 所以运行时要连接成绝对指令代码。 2019/11/10 中南大学软件学院

1.2 编译过程 六、编译前端与后端 编译前端：与源语言有关，如词法分析， 语法分析，语义分析与中间代码产生， 与机器无关的优化 中间语言 目标语言 编译前端：与源语言有关，如词法分析， 语法分析，语义分析与中间代码产生， 与机器无关的优化 编译后端 ：与目标机有关，与目标机有关的优化，目标代码产生 2019/11/10 中南大学软件学院

1.3 编译程序与程序设计环境 程序设计环境 集成化的程序设计环境 编辑程序 编译程序 连接程序 调试工具 2019/11/10 中南大学软件学院

.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上工作的最佳选择。 让我们看一看它和.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超越Java的主要体现之一，它为所有的语言支持垃圾收集，线程管理等功能 OS就不用说了，MS的强项。 VS .NET则在一个整合的IDE中为.NET Framework提供了一个简单易用、整合企业建模工具的综合开发工具，当Linux还在追求User Friendly的时候，微软早已经进入了Developer Friendly的时代。好处：降低总拥有成本。 2019/11/10 中南大学软件学院

1.3 编译程序与程序设计环境 编译程序的生成 以汇编语言和机器语言为工具 优点: 可以针对具体的机器，充分发挥计算机的系统功能。生成的程序效率高。 缺点: 程序难读、难写、易出错、难维护、生产的效率低。 2019/11/10 中南大学软件学院

1.3 编译程序与程序设计环境 高级语言书写 优点: 程序易读、易理解、容易维护、生产的效率高。 优点: 程序易读、易理解、容易维护、生产的效率高。 缺点: 难以充分发挥计算机的系统功能，生成的程序效率低。 2019/11/10 中南大学软件学院

1.3 编译程序与程序设计环境 高级语言书写 利用已有的某种语言的编译程序实现另一语言的编译程序。 L2语言 A代码 P2: L1语言 2019/11/10 中南大学软件学院

1.3 编译程序与程序设计环境 移植方法 把一种机器上的编译程序移植到另一种机器上。 L语言 B代码 P2: L语言 B代码 P2: L语言 A代码 L语言 A代码 P1: 2019/11/10 中南大学软件学院

1.3 编译程序与程序设计环境 自展技术 L1+L2+...+Ln … L1+L2 L1 2019/11/10 中南大学软件学院

1.3 编译程序与程序设计环境 编译程序自动产生 编译程序-编译程序，编译程序书写系统 L语言的语法描述 编译程序 L语言的 语义描述 自动产生器 L语言的 编译程序 目标语言 或机器描述 LEX 词法分析程序产生器 YACC 语法分析程序产生器 2019/11/10 中南大学软件学院

1.4 高级语言程序简介 一、参数传递 模块之间进行参数传递有三种形式： 1、传地址(call by reference)： 把实在参数的地址传递给相应的形式参数 2、传值(call by value): 调用段把实在参数的值计算出来并放在被调用段 可以拿到的地方，把值带入。 3、传名(call by name)： 过程调用的作用相当于把被调用的过程体抄到调 用出现的地方，但把其中任一出现的形式参数都替换 成相应的实在参数(文字替换)。 2019/11/10 中南大学软件学院

1.4 高级语言程序简介 二、存贮管理 1、静态存贮分配 编译时就安排好目标程序运行时的全部数据空 间，并能确定每个数据项目的单元地址。 2、动态存贮分配 如果允许递归、可变数据结构，则必须动态分 配。 ①栈式：整个程序数据空间安排在一个栈中 ②堆式：允许自由地申请和退还空间 2019/11/10 中南大学软件学院

1.4 高级语言程序简介 例：对于下述程序，试分析用传名、传值、传 地址方法传递参数时所得的打印结果。 PROGRAM SS(input,output); VAR A,B:integer; PROCEDURE P(x,y,z:integer); begin y:=y+1;z:=z+x; end; BEGIN A:=2;b:=3; P(A+B,A,A); writeln (‘A=‘,A); END 2019/11/10 中南大学软件学院

1.4 高级语言程序简介 解: (1)传名：相当于执行 A:=2;B:=3; A:=A+1;A:=A+(A+B) writeln(‘A=‘,A); 所以，结果为A=9 (2)传值：把实参的值计算出来传给形参。 在调用过程P时，形参x=5;y=2;z=2 出过程P时，形参x=5;y=3;z=7 这并不把结果回送到主程序，所以结果为A=2 2019/11/10 中南大学软件学院

1.4 高级语言程序简介 所以，①为A:=A+1=3 ②为A:=A+T=8。 因此，最后A=8. (3)传地址：实参计算出结果，把地址送形参。 设变量T=A+B(结果为5)。执行时把T、A、A的 地址(设为addr1,addr2,addr2)送给形参： x=daar1,y=addr2,z=addr2。 T的地址addra即x A的地址addra即y A的地址addra即z 执行过程P即为：①y↑:=y↑+1;②z↑:=z↑+x↑ 所以，①为A:=A+1=3 ②为A:=A+T=8。 因此，最后A=8. T A B 5 2 3 2019/11/10 中南大学软件学院

1.4 高级语言程序简介 例： Procedure P(x,y,z); begin y:=x+y; z:=z*z; end begin A:=2; B:=A*2; P(B-A,A,B); print A,B 传地址、传值，结果如何？ 2019/11/10 中南大学软件学院