陈意云编译原理chapter

1、编译原理和技术编译原理和技术中国科学技术大学中国科学技术大学计算机科学与技术学院计算机科学与技术学院陈意云陈意云第一页，共27页。课课 程程 简简 介介课程内容课程内容介绍编译器构造的一般原理和根本实现方法介绍编译器构造的一般原理和根本实现方法包括的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论与类型系统、程序分析原理包括的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论与类型系统、程序分析原理等等强调形式描绘技术和自动生成技术强调形式描绘技术和自动生成技术强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于任何源语言或目的机器强调对编译原理和技

2、术的宏观理解，不把注意力分散到枝节算法，不偏向于任何源语言或目的机器第二页，共27页。课课 程程 简简 介介学习意义学习意义对编程语言的设计和实现有深化的理解，对和编程语言有关的理论有所理解，对宏观上把握编程语言来说，对编程语言的设计和实现有深化的理解，对和编程语言有关的理论有所理解，对宏观上把握编程语言来说，起一个奠基的作用起一个奠基的作用从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中编译技术的应用和编译技术的开展编译技术的应用和编译技术的开展高级语言设计、计算机体系构造的优

3、化并行、内高级语言设计、计算机体系构造的优化并行、内存分层、新型计算机体系构造设计、程序翻译、存分层、新型计算机体系构造设计、程序翻译、进步软件开发效率的工具进步软件开发效率的工具 、高可信软件、高可信软件第三页，共27页。课课 程程 简简 介介教材和参考书教材和参考书陈意云、张昱，编译原理，高等教育出版社，陈意云、张昱，编译原理，高等教育出版社，张昱、陈意云，编译原理实验教程，高等教育出版社，张昱、陈意云，编译原理实验教程，高等教育出版社， A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Tec

4、hniques, and Tools , 2nd edition, Addison-Wesley, 2007 陈意云、张昱，编译原理习题精选与解析，高等教育出版社，陈意云、张昱，编译原理习题精选与解析，高等教育出版社，2005 教学资源网页：教学资源网页： :/ :/ 程程 简简 介介课程要求课程要求质量上的目的：师生共同努力，达国内最好程度质量上的目的：师生共同努力，达国内最好程度讲课进展较快，平时不复习并加深理解，后面将听不懂讲课进展较快，平时不复习并加深理解，后面将听不懂作业：少而精，周一课间交作业作业：少而精，周一课间交作业课程设计：自己动手，大有收获课程设计：自己动手，大有收获考试：

5、开卷，灵敏运用知识考试：开卷，灵敏运用知识学期总评学期总评 = 考试成绩占考试成绩占60%，作业占，作业占10%，课程设计，课程设计30%上课、设计、考试时间大体安排上课、设计、考试时间大体安排第五页，共27页。课课 程程 简简 介介课程设计要求课程设计要求内容：独立地研发扩展内容：独立地研发扩展PL/0语言的编译器和解释器语言的编译器和解释器目的：稳固对理论和技术的理解，进步程序设计才能目的：稳固对理论和技术的理解，进步程序设计才能技术准备：技术准备：VC+的编程环境，的编程环境，C语言编程语言编程考察与评分：对截止时间前提交的程序，通过测试和辩论进展公开评分考察与评分：对截止时间前提交的程

6、序，通过测试和辩论进展公开评分前四年课程设计的经历和教训前四年课程设计的经历和教训对该课程设计的综合性认识缺乏对该课程设计的综合性认识缺乏对考察的对考察的“动真格认识缺乏动真格认识缺乏第六页，共27页。对对 课课 程程 的的 评评 论论本校少年班本校少年班1994级一个同学，级一个同学，Stanford大学博士大学博士1999年年 Actually I think the quality of the compiler course in USTC is really very good and can be compared with any universities here. 本系某考研

7、同学本系某考研同学2006年年感觉您出的题目很有创意，也很有深度感觉您出的题目很有创意，也很有深度 ，没有局限于固定的算法和题型，只看课本和复习，没有局限于固定的算法和题型，只看课本和复习往年的题目而不深化考虑的人是做不出来的，可以真正从本质上考察一个考生的程度往年的题目而不深化考虑的人是做不出来的，可以真正从本质上考察一个考生的程度第七页，共27页。对对 课课 程程 的的 评评 论论西南科技大学某考研学生西南科技大学某考研学生2004年年看过你编的书后，感觉编译的原理可以一下子和我平常学的很多学科和语言都联络起来了，可以学看过你编的书后，感觉编译的原理可以一下子和我平常学的很多学科和语言都联

8、络起来了，可以学到很多可以实际用到的东西，虽然是在讲同样的东西，但您的教学方式让我很适应，学起来也很有兴趣，大大减轻了我考到很多可以实际用到的东西，虽然是在讲同样的东西，但您的教学方式让我很适应，学起来也很有兴趣，大大减轻了我考研的疲劳感研的疲劳感第八页，共27页。第一章第一章 引引 论论 名词解释名词解释 翻译器翻译器(translator)(translator)、编译器、编译器(compiler)(compiler) 解释器解释器(interpreter)(interpreter)编译器从逻辑上可以分成假设干个阶段编译器从逻辑上可以分成假设干个阶段每个阶段把源程序从一种表示变换成另一种表

9、示每个阶段把源程序从一种表示变换成另一种表示本章通过描绘编译器的各个阶段来介绍编译这个课题本章通过描绘编译器的各个阶段来介绍编译这个课题第九页，共27页。1.1 编译器概述编译器概述词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器独立于机器的代码优化器独立于机器的代码优化器代码生成器代码生成器依赖于机器的代码优化器依赖于机器的代码优化器目标机器代码目标机器代码符号表符号表第十页，共27页。符符 号号 表表 positioninitialrate. . . . . . .123词法分析器词法分析器 id, 1 = id, 2 + id, 3 6

10、0 position = initial + rate 601.1 编译器概述编译器概述 记号流记号流 字符流字符流第十一页，共27页。1.1 编译器概述编译器概述表达式的语法特征表达式的语法特征任何一个标识符都是表达式任何一个标识符都是表达式任何一个数都是表达式任何一个数都是表达式假如假如e1和和e2都是表达式，那么都是表达式，那么 e1 + e2 e1 * e2 (e1)也都是表达式也都是表达式表达式表达式表达式表达式表达式表达式标识符标识符表达式表达式表达式表达式(initial)标识符标识符(rate)数数(60)*+initial + rate * * 60的分析树的分析树第十二页，

11、共27页。符符 号号 表表 positioninitialrate. . . . . . .123语法分析器语法分析器 id, 1 = id, 2 + id, 3 60 = + 60 id, 1 id, 2 id, 3 语法树语法树1.1 编译器概述编译器概述 记号流记号流第十三页，共27页。符符 号号 表表 positioninitialrate. . . . . . .1231.1 编译器概述编译器概述语义分析器语义分析器 = + 60 id, 1 id, 2 id, 3 = + inttofloat id, 1 id, 2 id, 3 60 语法树语法树 语法树语法树第十四页，共27页。

12、符符 号号 表表 positioninitialrate. . . . . . .123中间代码生成器中间代码生成器t1 = inttofloat(60)t2 = id3 t1t3 = id2 + t2id1 = t3 = + inttofloat id, 1 id, 2 id, 3 60 1.1 编译器概述编译器概述 三地址三地址中间代码中间代码 语法树语法树第十五页，共27页。符符 号号 表表 positioninitialrate. . . . . . .123代码优化器代码优化器t1 = inttofloat(60)t2 = id3 t1t3 = id2 + t2id1 = t3t1

13、= id3 * * 60.0id1 = id2 + t11.1 编译器概述编译器概述 三地址三地址中间代码中间代码 三地址三地址中间代码中间代码第十六页，共27页。符符 号号 表表 positioninitialrate. . . . . . .123代码生成器代码生成器MOVF id3, R2MULF #60.0, R2MOVF id2, R1ADDF R2, R1MOVF R1, id1t1 = id3 * * 60.0id1 = id2 + t11.1 编译器概述编译器概述 三地址三地址中间代码中间代码 汇编汇编代码代码第十七页，共27页。1.1 编译器概述编译器概述解释器和编译器的区别

14、解释器和编译器的区别词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器独立于机器的代码优化器独立于机器的代码优化器代码生成器代码生成器依赖于机器的代码优化器依赖于机器的代码优化器目标机器代码目标机器代码解释器不生成目的代码，而是直接执行源程序解释器不生成目的代码，而是直接执行源程序所指定的运算所指定的运算 解释器也需要对源程序进解释器也需要对源程序进展词法、语法和语义分析展词法、语法和语义分析,中间代码生成中间代码生成第十八页，共27页。1.1 编译器概述编译器概述BASIC年代的解释器年代的解释器功能：它将高级语言的源程序翻译成一种中间语言程

15、序，然后对中间语言程序进展解释执行功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进展解释执行在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器Java年代的解释器年代的解释器上述两个功能分在两个程序中上述两个功能分在两个程序中前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序后一个叫做解释器，它对字节码程序进展解释执行后一个叫做解释器，它对字节码程序进展解释执行第十九页，共27页。1.1 编译器概述编译器概述阶段分组阶

16、段分组前端前端后端后端词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器独立于机器的代码优化器独立于机器的代码优化器代码生成器代码生成器依赖于机器的代码优化器依赖于机器的代码优化器目标机器代码目标机器代码第二十页，共27页。1.1 编译器概述编译器概述词法分析器词法分析器语法分析器语法分析器语义分析器语义分析器源程序源程序中间代码生成器中间代码生成器独立于机器的代码优化器独立于机器的代码优化器代码生成器代码生成器依赖于机器的代码优化器依赖于机器的代码优化器目标机器代码目标机器代码阶段分组阶段分组遍遍第二十一页，共27页。1.2 编译器技术的应用

17、编译器技术的应用 高级语言的实现高级语言的实现高级编程语言易于编程，但程序运行较慢高级编程语言易于编程，但程序运行较慢低级语言编程时可施行更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护低级语言编程时可施行更有效的控制方式，得到更有效的代码，但难编写、易出错、难维护流行编程语言的大多数演变都是朝着进步抽象级别的方向流行编程语言的大多数演变都是朝着进步抽象级别的方向每一轮编程语言新特征的出现都刺激编译器优化的新研究每一轮编程语言新特征的出现都刺激编译器优化的新研究第二十二页，共27页。1.2 编译器技术的应用编译器技术的应用 高级语言的实现高级语言的实现每一轮编程语言新特征的出现都刺

18、激编译器优每一轮编程语言新特征的出现都刺激编译器优化的新研究化的新研究支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：支持用户定义的聚合数据类型和高级控制流，如数组和记录、循环和过程调用：C、Fortran面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：面向对象的主要概念是数据抽象和性质继承，使得程序更加模块化并易于维护：Smalltalk、C+、C#、Java类型平安的语言：类型平安的语言：Java没有指针，也不允许指针算术。它用无用单元搜集机制来自动地释放那些不没有指针，也不允许指针算术。它用无用单元搜集机制来自动地释放那些不再使用的变量占据的内

19、存再使用的变量占据的内存Java设计来支持代码移植和代码挪动设计来支持代码移植和代码挪动第二十三页，共27页。1.2 编译器技术的应用编译器技术的应用 针对计算机体系构造的优化针对计算机体系构造的优化计算机体系构造的迅速演化引起对新的编译器技术一种不知足的需要计算机体系构造的迅速演化引起对新的编译器技术一种不知足的需要并行化并行化 编译器重新整理指令，使得指令级并行更有效编译器重新整理指令，使得指令级并行更有效 编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上内存分层内存分层 编译器优化历来集中在优化处理器的执行上，但是如今更强调要使内存分层更有效编译器优化历来集中在优化处理器的执行上，但是如今更强调要使内存分层更有效第二十四页，共27页。1.2 编译器技术的应用编译器技术的应用 新计算机体系构造的设计新计算机体系构造的设计如今计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码如今计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码在现代计算机体系构造的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模在现代计算机体系构造的研究中，在处理器的设计阶段就开发编译器，并将编译生成的