编译原理实践及应用 ----清华大学出版社

教材及主要参考资料 教材：编译原理实践及应用，黄贤英，清华大学出版社 主要参考资料： (1) 编译原理，陈火旺，国防工业出版社 程序设计语言编译方法，肖军模，大连理工大学出版社 编译原理，张素琴，吕映芝，清华大学出版社 编译原理，alfred V.Aho等著，李建中等译，人民邮电出版社 2017年3月17日星期五2017年3月17日星期五

考 核 方 法 平时成绩、作业完成：10% 实验：30% 期末考试：60% 要求上课不迟到早退,不旷课,有事请假,记好笔记 考 核 方 法 平时成绩、作业完成：10% 要求上课不迟到早退,不旷课,有事请假,记好笔记 要求用大作业本, 不能交单张纸, 独立完成 实验：30% 要求程序可运行, 并有相关设计和使用说明 期末考试：60% 闭卷形式 2017年3月17日星期五2017年3月17日星期五

序言 C语言程序 汇编语言程序 void main( ) …… { int x,y,z; mov ax,3 x=3; mov x,ax z=x+y; } …… mov ax,3 mov x,ax mov ax,2 mov y,ax mov ax,x mov bx,y add ax,bx mov z,ax ...... 300 302 304 306 308 内存地址 内存内容 单元名字 …… 200H 3 x：局部变量 201H 2 y：局部变量 202H 5 z：局部变量 高级语言能够完成的功能，汇编语言和机器语言也能够完成，但高级语言是面向程序员的，接近于人的思维，不需要考虑内存地址，汇编语言和机器语言面向机器。计算机只能识别和执行机器语言，那么是谁，如何将高级语言翻译为能够在计算机上执行的机器语言呢？ 这就是编译程序 2017年3月17日星期五2017年3月17日星期五

为什么要学习编译原理？ 1、有助于深刻理解和正确使用程序设计语言，加深对高级语言程序执行过程的理解 2、有助于加深对整个计算机系统的理解。 3、设计开发编译程序的软件技术同样可以用于其他软件的设计开发。 4、随着微处理器技术的飞速发展，处理器性能在很大程度上取决于编译器的质量、编译技术成为计算机的核心技术，地位变得越来越重要。 2017年3月17日星期五2017年3月17日星期五

《编译原理》课程在计算机科学中的重要地位 (1) 学习编程最初是学习一门高级语言，C或Pascal，掌握编写一些简单程序的方法； (2) 学习数据结构，建立“算法”的概念，对编程有更深入的理解。遇到问题的时候，能够寻找相应的数据结构模型，设计适当的算法来解决问题； (3) 学习汇编语言，这门课程是我们真正深入了解计算机内部工作的第一门课程。通过学习了解汇编语言如何变为机器语言，如何对应于一条指令； (4) 计算机组成原理课程的学习使我们了解到计算机的硬件组成，以及机器指令程序如何在计算机中运行的过程。 (5) 编译原理课程帮助我们了解高级语言程序转换成机器指令程序的过程。可以帮助我们更深刻地理解高级语言程序运行的内部机制。 数据结构是一门非常重要的课程 汇编语言，尽管大多数人并不会在实际中用汇编语言来进行开发 2017年3月17日星期五2017年3月17日星期五

《编译原理》课程在计算机科学中的地位 高级语言程序设计 离散数学 数据结构 编译原理 操作系统 系统软件 应用软件 软件工程 信息系统 电子商务 汇编语言 计算机组成原理 2017年3月17日星期五2017年3月17日星期五

学习本课程的目的和任务 加深对编程语言设计和实现的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用，提升自身的编程能力 掌握编译程序的基本结构，掌握常用的编译技术和方法，将编译原理的理论和方法应用于一般的软件设计中 培养团队协作能力 编译方法不仅适用于编译程序，也广泛适用于其他系统软件和应用软件的开发。从根本上看，编译程序和其他应用程序一样，都可以归结为处理数据和表格，故可将它当作一个大型的应用实例。通过本课程学习，达到提高应用程序设计能力和解决实际问题能力的目的。 如词法分析中的字符串匹配技术可以应用于文本编辑程序、信息检索、通讯程序、模式识别中 上下文无关文法和语法制导的翻译可以用于分析表达式，写打字程序，绘图程序等小系统。 代码优化技术更可以用于自己的结构化程序中，用于改进性能、优化已有的程序等 2017年3月17日星期五2017年3月17日星期五

本课程的特点 (1) 本课程理论性很强，学习时需要很强的逻辑思维能力 (2) 涉及的算法复杂，要深入地理解这些算法很困难 (3) 整个编译程序的构造方法非常精妙，就像一部走时精确的时钟，很多齿轮、部件协调地运转，以驱动指针准确地旋转；编译程序也是如此，一边扫描源程序，一边经过各个部件的运算，准确地输出为目标语言。 (4) 编译原理课程各个部分之间的独立性很强，包括词法分析、语法分析、存储的组织与分配、中间语言、语法制导翻译、代码生成与优化这几大部分。词法分析和语法分析是其中的重点，语法分析也是难点，需要掌握比较复杂的算法逻辑；其他部分相对来说知识性更强一些。各部分之间的方法也互相独立，在学习时，便于逐个击破。 (5) 考试考查的内容相对来说是很稳定的，绝大多数题目的解法都非常机械。 2017年3月17日星期五2017年3月17日星期五

学习方法 (1) 尽可能地掌握编译原理的思想，要站得高一点，尽可能理解算法的思想，而不是背固定的算法。应该尽力理解为什么要这样做，逐渐在头脑中建立起编译器的整体概念，而不是零零散散的一些算法。 (2) 很多题目的解法比较固定，要熟练掌握相应的具体方法。 (3) 多做习题, 对于编译这样的学科，题目的规模很大，步骤繁多，而且前面的步骤一旦出错，后面都错。 (4) 要扎扎实实地牢记重要算法，配合大量的习题进行练习，达到拿到题目就可以动手做的地步。 (5) 一边学习，一边总结，关键是找差异：同一问题可以用多种方法来求解，不同方法适用于不同的文法，对文法的限制和要求，相应的表格的构造、使用等，各个方面的差异都要关注。 (6) 亲自动手实现书上的一些算法,完成实验指导书上给出的一个简单的编译程序，或者编译程序的一部分，这样能更灵活地掌握编译程序构造的精髓。 (1)尽可能地掌握编译原理的思想，要站得高一点，不要一开始就紧紧盯在一些具体的算法上，尽可能理解算法的内部机制，而不是去机械地背下那些固定的算法，比如各种语法分析的方法。应该尽力理解为什么要这样做，逐渐在头脑中建立起编译器的整体概念，而不是零零散散的一些算法。 (2)要熟练掌握了相应的具体方法，无论怎么出题都应该能够套用。 (3)多做习题，千万不能觉得自己知道方法了，就不用做了。尤其对于编译这样的学科，题目的规模很大，步骤繁多，而且前面的步骤一旦出错，后面都错。如果不熟练掌握的话，考试的时候必定慌乱。 (4) 要扎扎实实地把重要算法记牢，同时配合大量的习题进行练习，达到拿到题目就可以动手做的地步。同时也会加深对编译原理进一步的理解。 (5) 同一问题可以用多种方法来求解(如词法分析有多种方式，语法分析也有多种方法)，不同的方法适用于哪类文法，对文法的限制和要求，相应的表格的构造、使用等，各个方面的差异都要关注。 2017年3月17日星期五2017年3月17日星期五

第一章 引 论

本章要求 主要内容：各种翻译程序的概念，编译过程和阶段划分，编译程序的组成和结构，编译程序的构造方法 重点掌握：编译程序工作的基本过程及其各阶段的基本任务，编译程序总框。 2017年3月17日星期五2017年3月17日星期五

1.1 程序设计语言与翻译程序 为什么要使用编译程序？ 机器语言 (machine language) 1.1 程序设计语言与翻译程序 为什么要使用编译程序？ 机器语言 (machine language) C7 06 0000 0002 汇编语言 (assembler language) MOV X , 2 高级语言 (high-level language) X = 2 2017年3月17日星期五2017年3月17日星期五

为什么要使用编译程序？ 机器语言 (machine language) 汇编语言 (assembler language) MOV X , 2 高级语言 (high-level language) X = 2 2017年3月17日星期五2017年3月17日星期五

计算机中的语言层次和转换关系 2017年3月17日星期五2017年3月17日星期五

编译程序所处的层次 语言处理程序 高 级 语 言 操作系统 . 语 言 计算机硬件 汇编语言 Fortran语言 Fortran编译程序 C Basic解释程序 Basic语言 2017年3月17日星期五2017年3月17日星期五

什么叫编译程序 翻译程序：能够将某种语言写的程序转换成另一种语言的程序，而且后者与前者在逻辑上是等价的。 编译程序：将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 解释程序：将高级程序设计语言写的源程序作为输入，边解释边执行源程序本身，而不产生目标程序的翻译程序。 2017年3月17日星期五2017年3月17日星期五

编译程序的功能 编译程序 源程序 目标程序 计算机运行 输入数据 结果 2017年3月17日星期五2017年3月17日星期五

解释程序的功能 解释程序 源程序 输入数据 结果 2017年3月17日星期五2017年3月17日星期五

对编译程序的一些说明 编译程序实质上是一个翻译程序，要注意等价变换 本课程的任务就是讲解在这个转换过程中所涉及到的一些理论和方法，最后，使用这些理论和方法，自己编写一个小的编译器 转换是一个总体的功能，要抓住总体结构，逐层细分，写编译器时要体现软件工程中软件设计的原则，自顶向下，逐层分解。 编译器要完成的转换任务相当复杂，实现编译器时必须分步骤分阶段实现。分阶段实现的好处是能够简化程序的设计，当然也可以不分阶段实现。 2017年3月17日星期五2017年3月17日星期五

编译程序的分类 诊断编译程序 优化编译程序 可变目标编译程序 交叉编译程序 2017年3月17日星期五2017年3月17日星期五

与编译程序相关的程序 编辑器(editor) 预处理器(Preprocessor) 汇编程序(assembler) 连接程序(linker) 将源程序汇集到一起，宏展开等 汇编程序(assembler) 连接程序(linker) 连接系统函数与系统资源 装入程序(loader) 重定位(relocation) Debugger,Profiler,Project Manager 统计信息，用于优化 2017年3月17日星期五2017年3月17日星期五

什么是编译原理 编译原理是讨论编译程序设计的基本理论、基本概念、基本方法 2017年3月17日星期五2017年3月17日星期五

1.2 编译过程概述 1、逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成 1.2 编译过程概述 1、逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成 每个阶段把源程序从一种表示变换成另一种表示 词法 分析 语法分析 语义分析与中间代码生成 代码优化 目标代码生成 2017年3月17日星期五2017年3月17日星期五

划分阶段的依据是什么？每个阶段所实现的功能相对独立。 按照词法分析、语法分析、语义分析等这种方式来划分阶段的原因是：每个阶段的复杂程度不同，所依据的理论基础不同，实现时采用的方法也不同。主要是方便理解和实现。 划分阶段的依据是什么？每个阶段所实现的功能相对独立。 2017年3月17日星期五2017年3月17日星期五

第一阶段：词法分析 任务:从左到右扫描源程序，识别出每个单词 附加任务：a、滤掉空格 b、识别单词 单词符号是语言的基本组成成分 词法分析的工作主要依据语言的词法规则，描述词法规则的有效工具是正规式和有限自动机。 单词的种类： （1） 标识符 （2） 关键字（char、int、if、else、switch、while、for等） （3） 运算符（即运算符号 +、－、*、/、&等） （4） 界符（常见的有 ； ， ： （ ）等） （5） 常数 2017年3月17日星期五2017年3月17日星期五

例: begin result:=5＋B * C＋B * C end; 单词 类型 内部形式 begin 关键字 $begin result 标识符 id1 := 界符 5 常数 int1 + 算符 B * C id2 id3 end $end ; 例: begin result:=5＋B * C＋B * C end; 2017年3月17日星期五2017年3月17日星期五

第二阶段：语法分析 任务: 在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。 任务: 在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。 确定整个输入串是否构成语法上正确的程序。 根据规则判定：赋值语句：标识符：＝表达式 表达式：标识符、常数是表达式 表达式的运算也是表达式 例：识别符号串id1:=int1 + id2 * id3 + id2 * id3（即 result:= 5＋B * C＋B * C）是一个赋值语句， 而int1 + id2 * id3 + id2 * id3 （5＋B * C＋B * C） 是一个表达式 2017年3月17日星期五2017年3月17日星期五

注意树的形式！！ id1:=int1 + id2 * id3 + id2 * id3 语法分析所依据的是语言的语法规则， 表示语法规则的工具是上下文无关文法,用下推自动机实现。 2017年3月17日星期五2017年3月17日星期五

第三阶段：语义分析和中间代码生成 任务：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)。 静态语义审查 变量定义 类型匹配 类型转换 例：C:=A*B (检查C与Ａ、Ｂ类型) 中间代码的翻译    中间代码有多种形式，如： 四元式: (运算符，运算对象1，运算对象2，结果) 2017年3月17日星期五2017年3月17日星期五

例：对赋值语句： id1:=int1 + id2 * id3 + id2 * id3 1. 检查result、Ｂ、C是否定义、类型 2. 生成中间代码 id1:=int1 + id2 * id3 + id2 * id3 (运算符，运算对象1，运算对象2，结果) (*, id2, id3, T1) (+, int1, T1, T2) (*, id2, id3, T3) (+, T2, T3, T4) (:=, T4, _, id1) 2017年3月17日星期五2017年3月17日星期五

第四阶段： 代码优化 任务：对已产生的中间代码进行加工变换，使生成的目标代码更为高效(时间和空间)。 优化方法包括：公共子表达式的提取、循环优化、删除无用代码等。 代码的优化依据的是程序的等价变换规则。 序号 四元式 1 (*, id2, id3, T1) 2 (+, int1, T1, T2) 3 (*, id2, id3, T3) 4 (+, T2, T3, T4) 5 (:=, T4, _, id1) 序号 四元式 1 (*, id2, id3, T1) 2 (+, int1, T1, T2) 3 (+, T2, T1, id1) 2017年3月17日星期五2017年3月17日星期五

第五阶段：目标代码的生成 任务：把中间代码(或经优化的中间代码)变换成特定机器上的低级语言代码。 依赖于机器的硬件系统结构和机器指令的含义 目标代码可以是：绝对指令代码、可重定位的指令代码、汇编指令代码 （1）mov AX, id2 （2）mul AX, id3 （3）mov BX, AX （4）add AX, int1 （5）add AX, BX （6）mov id1, AX 序号 四元式 1 (*, id2, id3, T1) 2 (+, int1, T1, T2) 3 (+, T2, T1, id1) 2017年3月17日星期五2017年3月17日星期五

1.2编译程序的结构 由左图可以看出，词法分析是实现编译器的基础，语法分析是实现编译器的关键。 因此按照这个顺序来实现编译器 每一步的实现都依赖于一定的理论基础。 数学，尤其是离散数学是程序设计方法学的理论基础 2017年3月17日星期五2017年3月17日星期五

1.2 编译阶段的组合 几个概念 遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 1.2 编译阶段的组合 几个概念 遍：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 编译前端：主要指与源语言有关，与目标语言无关的部分，通常包括词法分析、语法分析、语义分析和中间代码生成，与机器无关部分的代码优化 编译后端：指与目标机器有关的部分。如与机器有关的优化、目标代码生成 2017年3月17日星期五2017年3月17日星期五

编译阶段的组合 2017年3月17日星期五2017年3月17日星期五

为什么生成中间代码 2017年3月17日星期五2017年3月17日星期五

1.2 编译程序的结构(续) 编译程序中的主要数据结构: (1) 记号(token) 1.2 编译程序的结构(续) 编译程序中的主要数据结构: (1) 记号(token) 当扫描程序将字符收集到一个记号中时，它通常是以符号表示这个记号；这也就是说，作为一个枚举数据类型的值来表示源程序的记号集。 2017年3月17日星期五2017年3月17日星期五

编译程序中的主要数据结构 (2) 语法树（syntax tree） 如果分析程序确实生成了语法树，它的构造通常为基于指针的标准结构，在进行分析时动态分配该结构，则整棵树可作为一个指向根节点的单个变量保存。结构中的每一个节点都是一个记录，它的域表示由分析程序和之后的语义分析程序收集的信息。 2017年3月17日星期五2017年3月17日星期五

编译程序中的主要数据结构: (3) 符号表（symbol table） 这个数据结构中的信息与标识符有关：函数、变量、常量以及数据类型。符号表几乎与编译器的所有阶段交互：扫描程序、分析程序或将标识符输入到表格中的语义分析程序；语义分析程序将增加数据类型和其他信息；优化阶段和代码生成阶段也将利用由符号表提供的信息选出恰当的代码。因为对符号表的访问如此频繁，所以插入、删除和访问操作都必须比常规操作更有效。尽管可以使用各种树的结构，但杂凑表却是达到这一要求的标准数据结构。有时在一个列表或栈中可使用若干个表格。 2017年3月17日星期五2017年3月17日星期五

编译程序中的主要数据结构: (4) 常数表（literal table） 常数表的功能是存放在程序中用到的常量和字符串，因此快速插入和查找在常数表中也十分重要。但是，在其中却无需删除，这是因为它的数据全程应用于程序而且常量或字符串在该表中只出现一次。 2017年3月17日星期五2017年3月17日星期五

(5) 中间代码（intermediate code） 编译程序中的主要数据结构: (5) 中间代码（intermediate code） 根据中间代码的类型（例如三元式代码）和优化的类型，该代码可以是文本串的数组、临时文本文件或是结构的连接列表。对于进行复杂优化的编译器，应特别注意选择允许简单重组的表示。 2017年3月17日星期五2017年3月17日星期五

(6) 临时文件（t e m p o r a ry file） 编译程序中的主要数据结构: (6) 临时文件（t e m p o r a ry file） 计算机过去一直未能在编译器时将整个程序保留在存储器中。这一问题已经通过使用临时文件来保存翻译时中间步骤的结果或通过“匆忙地”编译（也就是只保留源程序早期部分的足够信息用以处理翻译）解决了。 2017年3月17日星期五2017年3月17日星期五

1.3 编译程序的构造 构造编译程序要掌握以下几方面的内容： 源语言：理解其结构和含义 目标语言：必须清楚硬件的系统结构和指令的格式等 编译方法 2017年3月17日星期五2017年3月17日星期五

1.3 编译程序的构造 一般实现编译程序的方法有： 1.直接用机器语言编写编译程序 2.用汇编语言编写编译程序 3.用高级语言编写编译程序 注：编译程序核心部分常用汇编语言编写 3.用高级语言编写编译程序 注：这是普遍采用的方法 4.自编译 5.用编译工具自动生成:LEX(词法分析)与YACC(用于自动产生LALR分析表) 6.移植（同种语言的编译程序在不同类型的机器之间移植） 2017年3月17日星期五2017年3月17日星期五

本书构成及编译程序框架 2017年3月17日星期五2017年3月17日星期五

1.4 编译技术的发展 1954年至1957年间，FORTRAN语言及其编译器的开发。花了18个人年。 几乎与此同时，Noam Chomsky开始研究语言文法(grammar，结构规则)的难易程度以及识别它们所需的算法来为语言分类。 在6 0年代和7 0年代进行的分析问题(parsing problem，用于限定上下文无关语言的识别的有效算法)的研究。 有穷自动机(finite automata)和正规式(regular expression) 的研究与乔姆斯基的研究几乎同时开始，引出了表示程序设计语言的单词的符号方式。 接着又深化了生成有效的目标代码的方法，这就是最初的编译器，实际上应称作代码改进技术(code improvement technique)。 当分析问题变得好懂起来时，人们就在开发程序上花费了很大的功夫来研究这一部分的编译器的自动构造。Lex与Yacc。 在70年代后期和80年代早期，大量的项目都关注于编译器其他部分的生成自动化，这其中就包括了代码生成。这些尝试并未取得多少成功。 2017年3月17日星期五2017年3月17日星期五

1.4 编译技术最近的发展 与复杂的程序设计语言的发展结合在一起。如用于函数语言编译的Hindley-Milner类型检查的统一算法。 编译器已成为基于窗口的交互开发环境(IDE)的一部分，IDE的标准并没有多少，但已对标准的窗口环境进行了开发。近年来对此进行了大量研究，但是基本的编译器设计近20年来没有多大的改变，现在正迅速地成为计算机科学课程中的中心一环。 由多处理机的发展以及对并行处理的要求，最近的研究方向是并行编译。 随着嵌入式应用的迅速增长，推动了交叉编译技术的发展；对系统芯片设计方法和关键EDA技术的研究，也带动了专用语言VHDL等及其编译技术的不断深化。 2017年3月17日星期五2017年3月17日星期五

1.4 编译技术的应用 语言的结构化编辑器 :Turbo-Edit、editplus和Ultraedit等 语言程序的调试工具 语言程序的测试工具 高级语言之间的转换工具 交叉编译程序 2017年3月17日星期五2017年3月17日星期五

思考题1 1. 什么是编译程序 ？ 2. 编译过程分哪些阶段？各阶段的功能和任务是什么? 3. 写出pascal语言中字符集、单词、数据类型、各种表达式、语句和程序的组成 4. 查阅如下一种资料： (1) 与某种语言(如java、VB等)的编译程序有关 (2) 与编译程序的理论有关 (3) 与某种高级语言的发展有关 5. 用某种熟悉的语言的编译程序来理解层次和遍 2017年3月17日星期五2017年3月17日星期五