编译原理第一章编译原理引论

1、编译原理课程概述编译原理课程概述授课：付永钢授课：付永钢Email：课程简介课程简介课程内容课程内容介绍编译器构造的一般原理和基本实现方法介绍编译器构造的一般原理和基本实现方法理论知识：形式语言和自动机理论、语法制导的定理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论等义和属性文法、类型论等强调形式化描述技术强调形式化描述技术强调对编译原理和技术的宏观理解，不把注意力分散到枝节强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于某种源语言或目标机器算法，不偏向于某种源语言或目标机器课程简介课程简介课程意义课程意义对编程语言的设计和实现有深刻的理解，对宏观把对编程语

2、言的设计和实现有深刻的理解，对宏观把握编程语言来说，起一个奠基的作用。握编程语言来说，起一个奠基的作用。从软件工程看，编译器是一个很好的实例，所介绍从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中。的概念和技术能应用到一般的软件设计之中。大多数程序员同时是简单语言的设计者，有助于提大多数程序员同时是简单语言的设计者，有助于提高对这些语言的设计水平。高对这些语言的设计水平。在软件逆向工程、程序理解和软件安全等方面有着在软件逆向工程、程序理解和软件安全等方面有着广泛的应用。广泛的应用。课程简介课程简介l 教材：教材：教材名称：编译原理教材名称：编译原理主编：陈意云

3、主编：陈意云 张昱张昱出版社：高等教育出版社出版社：高等教育出版社l 主要参考资料主要参考资料 程序设计语言编译原理（第程序设计语言编译原理（第3 3版）版），国防工业出版社，陈火旺等编，国防工业出版社，陈火旺等编著著 编译原理编译原理，清华大学出版社，吕映芝、张素琴、蒋维杜编著，清华大学出版社，吕映芝、张素琴、蒋维杜编著 A.Aho,R.Sethi,and J.D.Ullman,A.Aho,R.Sethi,and J.D.Ullman,Compilers:Principles,Techniques, Compilers:Principles,Techniques, and Toolsand

4、Tools, 2nd edition, Addison-Wesley, 1986, 2nd edition, Addison-Wesley, 1986 陈意云、张昱，陈意云、张昱，编译原理习题精选编译原理习题精选，中国科大出版社，中国科大出版社，20022002 教学资源网页：教学资源网页：http:/ 考试成绩考试成绩占占70%，作业占，作业占15%，上机实验，上机实验15%课程教学内容及时间安排课程教学内容及时间安排l 编译原理概论编译原理概论-2-2课时课时l 词法分析词法分析-6-6课时课时l 文法及其描述文法及其描述-2-2课时课时l 自顶向下语法分析方法自顶向下语法分析方法-4-4

5、课时课时l 自底向上语法分析法自底向上语法分析法-8-8课时课时l 语法制导翻译语法制导翻译-6-6课时课时l 类型检查类型检查-2-2课时课时l 运行时空间组织运行时空间组织- 2- 2课时课时l 中间代码生成中间代码生成-4-4课时课时l 代码生成代码生成-4-4课时课时l 代码优化代码优化-4-4课时课时第一章第一章 编译原理引论编译原理引论内容提要内容提要l 编译器构造法的研究目的编译器构造法的研究目的l 编译器的结构编译器的结构编译的基本原则编译的基本原则编译器应有的性质编译器应有的性质编译器技术的应用编译器技术的应用l 关于学习编译原理关于学习编译原理编译器构造法的研究目的编译器构

6、造法的研究目的l什么是编译程序什么是编译程序编译编译程序程序高级程序设高级程序设计语言书写计语言书写的程序的程序低级语低级语言程序言程序术语术语源语言源语言(程序程序)目标语言目标语言(程序程序)实现语言实现语言S TI源语言源语言程序程序目标语目标语言程序言程序翻译翻译程序程序翻译翻译q翻译程序翻译程序 把某一种语言程序把某一种语言程序( (称为源语言程序称为源语言程序) )等价地转等价地转换成另一种语言程序换成另一种语言程序( (称为目标语言程序称为目标语言程序) )的程序的程序编译器构造法的研究目的编译器构造法的研究目的什么是编译程序什么是编译程序?高级语高级语言程序言程序机器语机器语言

7、程序言程序结果结果编译编译程序程序翻译翻译运行运行什么是编译程序什么是编译程序? ?q编译程序编译程序(compiler)(compiler) 把某一种高级语言程序等价地转换成另一种低级语把某一种高级语言程序等价地转换成另一种低级语言程序言程序( (如汇编语言或机器语言程序如汇编语言或机器语言程序) )的程序的程序诊断编译程序诊断编译程序优化编译程序优化编译程序交叉编译程序交叉编译程序可变目标编译程序可变目标编译程序什么是编译程序什么是编译程序? ?q解释程序解释程序 把源语言写的源程序作为输入，但不产生目标程序，把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身而是边解

8、释边执行源程序本身源程序源程序结果结果解释解释程序程序解释执行解释执行编译程序编译程序 vs. 解释程序解释程序编译编译解释解释什么叫编译程序什么叫编译程序?l编译程序编译程序:是指这样的程序，它能够把某种语是指这样的程序，它能够把某种语言的程序转换成另一种语言的程序，言的程序转换成另一种语言的程序，而后者与而后者与前者在逻辑上是等价的前者在逻辑上是等价的。如果源语言是诸如。如果源语言是诸如FORTRAN、Pascal、C、Ada、Smalltalk或或Java这样的这样的“高级语言高级语言”，而目标语言如汇编，而目标语言如汇编语言之类的语言之类的“低级语言低级语言”这样的翻译程序则称这样的翻

9、译程序则称之为编译程序。之为编译程序。内容提要内容提要l 编译器构造法的研究目的编译器构造法的研究目的l 编译器的结构编译器的结构编译的基本原则编译的基本原则编译器应有的性质编译器应有的性质编译器技术的应用编译器技术的应用 l 关于学习编译原理关于学习编译原理编译过程编译过程l把英文翻译为中文把英文翻译为中文 识别出句子中的一个个单词；识别出句子中的一个个单词；分析句子的语法结构；分析句子的语法结构；根据句子的含义进行初步翻译；根据句子的含义进行初步翻译；对译文进行修饰；对译文进行修饰；写出最后的译文。写出最后的译文。 编译过程编译过程词法分析器词法分析器语法分析器语法分析器语义分析器语义分析

10、器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理器出错管理器符号表管理器符号表管理器1. 词法分析词法分析l词法分析也叫线性分析和扫描。词法分析也叫线性分析和扫描。从左到右读构成源程序的字符流，分组为多个记号。从左到右读构成源程序的字符流，分组为多个记号。词法分析器词法分析器position = initial + rate position = initial + rate * * 60 60idid1 1 = = idid2 2 + + idid3 3 * * 60 60符符 号号 表表 positioninitialrate. .

11、 . . . . .1232. 语法分析语法分析l任务任务:在词法分析的基础上，根据语言的语法在词法分析的基础上，根据语言的语法规则把规则把单词符号串单词符号串分解成各类语法单位。分解成各类语法单位。l依循的原则：语法规则依循的原则：语法规则l描述工具：上下文无关文法描述工具：上下文无关文法语法分析（续）语法分析（续）语法分析器语法分析器idid1 1 = id = id2 2 + id + id3 3 * * 60 60idid1 1idid3 3idid2 2= =+ +* *6060在本例中，算符优先级可在本例中，算符优先级可以通过如下方法定义：以通过如下方法定义：1.定义程序语言的语法

12、规定义程序语言的语法规则体现算符的优先级则体现算符的优先级2.通过某些规则库，例如通过某些规则库，例如算符优先级表格等来定义算符优先级表格等来定义算符的优先级算符的优先级符符 号号 表表 positioninitialrate. . . . . . .1233. 语义分析语义分析l语义分析语义分析 这一阶段通常包括两方面的工作，首先这一阶段通常包括两方面的工作，首先对各种语法范畴进行静态语义检查，如果正对各种语法范畴进行静态语义检查，如果正确则进行另一方面的工作，即进行中间代码确则进行另一方面的工作，即进行中间代码的翻译。的翻译。 通常使用通常使用属性文法属性文法描述语义规则。描述语义规则。

13、语义分析（续）语义分析（续）语义分析器语义分析器idid1 1idid3 3idid2 2= =+ +* *6060idid1 1idid3 3idid2 2= =+ +* *inttorealinttoreal6060在本例中，几个标识符在本例中，几个标识符都是实数类型，而且源都是实数类型，而且源程序语言允许整数向实程序语言允许整数向实数类型的强制转换数类型的强制转换编译过程编译过程词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理出错管理符号表管理符号表管理前三个阶段前三个阶段

14、完成对源程完成对源程序的分析序的分析4. 中间代码生成中间代码生成符符 号号 表表 positioninitialrate. . . . . . .123中间代码生成器中间代码生成器temp1 = inttoreal(60)temp2 = id3 * temp1temp3 = id2 + temp2id1 = temp3=+* *60id1id2id3inttoreal5.代码优化代码优化符符 号号 表表 positioninitialrate. . . . . . .123代码优化器代码优化器temp1 = inttoreal(60)temp2 = id3 * temp1temp3 = id

15、2 + temp2id1 = temp3temp1 = id3 * * 60.0id1 = id2 + + temp1l 任务：对于前阶段产生的中间代码任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产进行加工变换，以期在最后阶段产生更高效的目标代码。生更高效的目标代码。l 依循的原则：程序的等价变换规则依循的原则：程序的等价变换规则6. 目标代码产生目标代码产生l任务任务: 把中间代码变换成特定机器上的目标代把中间代码变换成特定机器上的目标代码。码。l依赖于硬件系统结构和机器指令的含义依赖于硬件系统结构和机器指令的含义l目标代码三种形式目标代码三种形式:绝对指令代码绝对指令代码:

16、可直接运行可直接运行 可重新定位指令代码可重新定位指令代码: 连接装配，连接装配，汇编指令代码汇编指令代码: 需要进行汇编需要进行汇编符符 号号 表表 positioninitialrate. . . . . . .123temp1 = id3 * * 60.0id1 = id2 + + temp1代码生成器代码生成器MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1编译过程编译过程词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目

17、标程序目标程序出错管理器出错管理器符号表管理器符号表管理器 后三个阶后三个阶段对源程段对源程序进行综序进行综合合编译过程编译过程词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器代码优化器代码优化器代码生成器代码生成器目标程序目标程序出错管理出错管理符号表管理符号表管理后三个阶后三个阶段对源程段对源程序进行综序进行综合合编译前端与后端编译前端与后端l前端前端(front end)主要由与源语言有关，但与主要由与源语言有关，但与目标机无关的那些部分组成。通常包括词法目标机无关的那些部分组成。通常包括词法分析、语法分析、语义分析与中间代码产生，分析

18、、语法分析、语义分析与中间代码产生，有的代码优化工作，也可以包括在前端。有的代码优化工作，也可以包括在前端。 后端后端(back end)包括编译程序中与目标代码包括编译程序中与目标代码有关的部分，如与目标机有关的有关的优化，有关的部分，如与目标机有关的有关的优化，和目标代码的生成等。和目标代码的生成等。源语言源语言中间语言中间语言目标语言目标语言前端前端后端后端编译器的应用模型编译器的应用模型出出错错处处理理语法分析程序语法分析程序语义分析程序语义分析程序目标代码生成程序目标代码生成程序词法分析程序词法分析程序中间代码生成程序中间代码生成程序代码优化程序代码优化程序表表格格管管理理编译的前端

19、编译的前端（Front End）编译的后端编译的后端（Back End）编译器的构造工具编译器的构造工具l编译程序自动产生编译程序自动产生编译程序编译程序-编译程序，编译程序书写系统编译程序，编译程序书写系统LEX 词法分析程序产生器词法分析程序产生器YACC 语法分析程序产生器语法分析程序产生器编译程序编译程序自动产生器自动产生器L语言的语法描述语言的语法描述语义描述语义描述目标语言目标语言或机器描述或机器描述L语言的语言的编译程序编译程序内容提要内容提要l 编译器构造法的研究目的编译器构造法的研究目的l 编译器的结构编译器的结构编译器的基本原则编译器的基本原则编译器应有的性质编译器应有的性

20、质编译器技术的应用编译器技术的应用l 关于学习编译原理关于学习编译原理编译器技术的应用 l 高级语言的实现 高级编程语言易于编程，但程序运行较慢 低级语言编程时可实施更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护 流行编程语言的大多数演变都是朝着提高抽象级别的方向 每一轮编程语言新特征的出现都刺激编译器优化的新研究编译器技术的应用 l 高级语言的实现每一轮编程语言新特征的出现都刺激编译器优化的新研究 支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran 面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C+、C#、Java 类型安全的语言：Java没有指针，也不允许指针算术。它用无用单元收集机制来自动地释放那些不再使用的变量占据的内存 Java设计来支持代码移植和代码移动编译器技术的应用 l 针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要 并行化 编译器重新整理指令，使得指令级并行更有效 编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上 内存分层 编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效编译器技术的应用 l 新计算机体系结构的设计 现在计算机系统的性能不仅仅取决于它的原始速度，还取决于