中国科学技术大学 计算机科学与技术学院 陈意云

Presentation on theme: "中国科学技术大学 计算机科学与技术学院 陈意云"— Presentation transcript:

1 中国科学技术大学 计算机科学与技术学院 陈意云 0551-3607043 yiyun@ustc.edu.cn
编译原理和技术 中国科学技术大学 计算机科学与技术学院 陈意云

2 课 程 简 介 课程内容 介绍编译器构造的一般原理和基本实现方法
包括的理论知识：形式语言和自动机理论、语法制导的定义和属性文法、类型论与类型系统、程序分析原理等 强调形式描述技术和自动生成技术 强调对编译原理和技术的宏观理解，不把注意力分散到枝节算法，不偏向于任何源语言或目标机器 1．本课程介绍编译器构造的一般原理和基本实现方法，主要介绍编译器的各个阶段：词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。反映直至20世纪末的一些重要成果，如有关类型制导的编译思想。 2．本课程在介绍命令式程序设计语言实现技术的同时，强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论等。它们是计算机专业理论知识的重要一部分，在本书中结合应用来介绍这些知识，有助于学生较快领会和掌握。 3．本课程强调形式化描述技术，并以语法制导定义作为翻译的主要描述工具。 4．本课程强调对编译原理和技术在宏观上的理解，而不把读者的注意力分散到一些枝节的算法上，如计算开始符号集合和后继符号集合的算法，回填技术等。作为原理性的教材，本书介绍基本的理论和方法，而不偏向于某种源语言或目标机器。

3 课 程 简 介 学习意义 对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论有所了解，对宏观上把握编程语言来说，起一个奠基的作用
从软件工程看，编译器是一个很好的实例，所介绍的概念和技术能应用到一般的软件设计之中 编译技术的应用和编译技术的发展 高级语言设计、计算机体系结构的优化（并行、内 存分层）、新型计算机体系结构设计、程序翻译、 提高软件开发效率的工具 、高可信软件 虽然只有少数人从事构造或维护程序设计语言的编译器，但是本课程对本科生来说是一门重要课程。 1．本课程能使学生对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 2．对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大型例子，学生从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3．大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。 4．编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程：以另外一种形式创建系统同一层次的表示或者更高层次的抽象， 应用：技术仿造、软件维护。 程序理解：通过分析、抽象和一般化来获取软件知识的演绎过程。（1）基于机器代码和中间代码层的理解，需要借助于反汇编和反编译技术；（2）基于源代码的理解；（3）基于语法层的理解，程序分段、程序切片和程序分析等技术就是其中的最典型代表；（4）基于程序语义层的理解，模式匹配、格局识别(plan recognition)、概念赋值（concept assigned）和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全：满足安全策略。基本安全策略：类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学：都有编程语言和编译器方面的课程，80%有这方面的研究。国内对这方面的人才需求将增加。

4 课 程 简 介 教材和参考书 陈意云、张昱，编译原理，高等教育出版社，2008 张昱、陈意云，编译原理实验教程，高等教育出版社， 2009
A. V. Aho, M. S. Lam, R. Sethi, and J. D. Ullman, Compilers: Principles, Techniques, and Tools , 2nd edition, Addison-Wesley, 2007 陈意云、张昱，编译原理习题精选与解析，高等教育出版社，2005 教学资源网页： 虽然只有少数人从事构造或维护程序设计语言的编译器，但是本课程对本科生来说是一门重要课程。 1．本课程能使学生对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 2．对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大型例子，学生从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3．大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。 4．编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程：以另外一种形式创建系统同一层次的表示或者更高层次的抽象， 应用：技术仿造、软件维护。 程序理解：通过分析、抽象和一般化来获取软件知识的演绎过程。（1）基于机器代码和中间代码层的理解，需要借助于反汇编和反编译技术；（2）基于源代码的理解；（3）基于语法层的理解，程序分段、程序切片和程序分析等技术就是其中的最典型代表；（4）基于程序语义层的理解，模式匹配、格局识别(plan recognition)、概念赋值（concept assigned）和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全：满足安全策略。基本安全策略：类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学：都有编程语言和编译器方面的课程，80%有这方面的研究。国内对这方面的人才需求将增加。

5 课 程 简 介 课程要求 质量上的目标：师生共同努力，达国内最好水平 讲课进展较快，平时不复习并加深理解，后面将听不懂
作业：少而精，周一课间交作业 课程设计：自己动手，大有收获 考试：开卷，灵活运用知识 学期总评 = 考试成绩占60%，作业占10%，课程设计30% 上课、设计、考试时间大体安排 虽然只有少数人从事构造或维护程序设计语言的编译器，但是本课程对本科生来说是一门重要课程。 1．本课程能使学生对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 2．对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大型例子，学生从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3．大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。 4．编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程：以另外一种形式创建系统同一层次的表示或者更高层次的抽象， 应用：技术仿造、软件维护。 程序理解：通过分析、抽象和一般化来获取软件知识的演绎过程。（1）基于机器代码和中间代码层的理解，需要借助于反汇编和反编译技术；（2）基于源代码的理解；（3）基于语法层的理解，程序分段、程序切片和程序分析等技术就是其中的最典型代表；（4）基于程序语义层的理解，模式匹配、格局识别(plan recognition)、概念赋值（concept assigned）和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全：满足安全策略。基本安全策略：类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学：都有编程语言和编译器方面的课程，80%有这方面的研究。国内对这方面的人才需求将增加。

6 课 程 简 介 课程设计要求 内容：独立地研发扩展PL/0语言的编译器和解释器 目标：巩固对理论和技术的理解，提高程序设计能力
技术准备：VC++的编程环境，C语言编程 考查与评分：对截止时间前提交的程序，通过测试和答辩进行公开评分 前四年课程设计的经验和教训 对该课程设计的综合性认识不足 对考查的“动真格”认识不足 虽然只有少数人从事构造或维护程序设计语言的编译器，但是本课程对本科生来说是一门重要课程。 1．本课程能使学生对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 2．对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大型例子，学生从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3．大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。 4．编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程：以另外一种形式创建系统同一层次的表示或者更高层次的抽象， 应用：技术仿造、软件维护。 程序理解：通过分析、抽象和一般化来获取软件知识的演绎过程。（1）基于机器代码和中间代码层的理解，需要借助于反汇编和反编译技术；（2）基于源代码的理解；（3）基于语法层的理解，程序分段、程序切片和程序分析等技术就是其中的最典型代表；（4）基于程序语义层的理解，模式匹配、格局识别(plan recognition)、概念赋值（concept assigned）和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全：满足安全策略。基本安全策略：类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学：都有编程语言和编译器方面的课程，80%有这方面的研究。国内对这方面的人才需求将增加。

7 对 课 程 的 评 论 本校少年班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. 本系某考研同学（2006年） 感觉您出的题目很有创意，也很有深度 ，没有局限于固定的算法和题型，只看课本和复习往年的题目而不深入思考的人是做不出来的，能够真正从本质上考察一个考生的水平 虽然只有少数人从事构造或维护程序设计语言的编译器，但是本课程对本科生来说是一门重要课程。 1．本课程能使学生对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 2．对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大型例子，学生从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3．大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。 4．编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程：以另外一种形式创建系统同一层次的表示或者更高层次的抽象， 应用：技术仿造、软件维护。 程序理解：通过分析、抽象和一般化来获取软件知识的演绎过程。（1）基于机器代码和中间代码层的理解，需要借助于反汇编和反编译技术；（2）基于源代码的理解；（3）基于语法层的理解，程序分段、程序切片和程序分析等技术就是其中的最典型代表；（4）基于程序语义层的理解，模式匹配、格局识别(plan recognition)、概念赋值（concept assigned）和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全：满足安全策略。基本安全策略：类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学：都有编程语言和编译器方面的课程，80%有这方面的研究。国内对这方面的人才需求将增加。

8 对 课 程 的 评 论 西南科技大学某考研学生（2004年）
看过你编的书后，感觉编译的原理可以一下子和我平常学的很多学科和语言都联系起来了，可以学到很多可以实际用到的东西，虽然是在讲同样的东西，但您的教学方式让我很适应，学起来也很有兴趣，大大减轻了我考研的疲劳感 虽然只有少数人从事构造或维护程序设计语言的编译器，但是本课程对本科生来说是一门重要课程。 1．本课程能使学生对编程语言的设计和实现有深刻的理解，对和编程语言有关的理论（形式语言和自动机理论、类型论等）有所了解，对宏观上把握编程语言来说，起一个奠基的作用。 2．对软件工程来说，编译器是一个很好的实例（基本设计、模块划分等），也是本科期间能碰到的唯一的大型例子，学生从本课程的学习也能了解到软件工程中的一些技术（如基于事件驱动的编程）。本课程所介绍的概念和技术能应用到一般的软件设计之中。 3．大多数程序员同时是语言的设计者，虽然是一些简单的语言（如输入输出），本课程的学习有助于提高对这些语言的设计水平。 4．编译技术在软件逆向工程、程序理解和软件安全等方面有着广泛的应用 软件逆向工程：以另外一种形式创建系统同一层次的表示或者更高层次的抽象， 应用：技术仿造、软件维护。 程序理解：通过分析、抽象和一般化来获取软件知识的演绎过程。（1）基于机器代码和中间代码层的理解，需要借助于反汇编和反编译技术；（2）基于源代码的理解；（3）基于语法层的理解，程序分段、程序切片和程序分析等技术就是其中的最典型代表；（4）基于程序语义层的理解，模式匹配、格局识别(plan recognition)、概念赋值（concept assigned）和概念分析(concept analysis)等都是进行语义级的软件理解和分析技术。 软件安全：满足安全策略。基本安全策略：类性安全、控制流安全和内存安全。还有信息流安全。用到词法、语法和语义分析、类性系统和类性检查、控制流分析和数据流分析等。编译器将走向类型制导的编译器。 美国的名牌大学：都有编程语言和编译器方面的课程，80%有这方面的研究。国内对这方面的人才需求将增加。

9 第一章 引 论 名词解释 编译器从逻辑上可以分成若干个阶段 每个阶段把源程序从一种表示变换成另一种表示
第一章 引 论 名词解释 翻译器(translator)、编译器(compiler) 解释器(interpreter) 编译器从逻辑上可以分成若干个阶段 每个阶段把源程序从一种表示变换成另一种表示 本章通过描述编译器的各个阶段来介绍编译这个课题

10 1.1 编译器概述 源程序 符号表 词法分析器 语法分析器 代码生成器 语义分析器 中间代码生成器 目标机器代码 独立于机器的代码优化器
依赖于机器的代码优化器 目标机器代码 符号表

11 position = initial + rate  60
1.1 编译器概述  字符流 词法分析器 id, 1 = id, 2 + id, 3  60 position = initial + rate  60 符 号 表 position initial rate . . . 1 2 3  记号流

12 1.1 编译器概述 表达式的语法特征 任何一个标识符都是表达式 任何一个数都是表达式 如果e1和e2都是表达式，那么  e1 + e2
也都是表达式 表达式 标识符 (initial) (rate) 数 (60) * + 先介绍语法，然后才介绍语法分析。 initial + rate * 60的分析树

13 id, 1 = id, 2 + id, 3  60
1.1 编译器概述  记号流 语法分析器 id, 1 = id, 2 + id, 3  60 = +  60 id, 1 id, 2 id, 3 符 号 表 position initial rate . . . 1 2 3  语法树

14 1.1 编译器概述  语法树  语法树 语义分析器 = +  60 id, 1 id, 2 id, 3
inttofloat  语法树 符 号 表 position initial rate . . . 1 2 3  语法树

15 1.1 编译器概述  语法树  三地址中间代码 中间代码生成器 t1 = inttofloat(60) t2 = id3  t1
= +  inttofloat id, 1 id, 2 id, 3 60  语法树 符 号 表 position initial rate . . . 1 2 3  三地址中间代码

16 1.1 编译器概述  三地址中间代码  三地址中间代码 代码优化器 t1 = inttofloat(60) t2 = id3  t1
id1 = id2 + t1 符 号 表 position initial rate . . . 1 2 3  三地址中间代码

17 1.1 编译器概述  三地址中间代码  汇编代码 代码生成器 MOVF id3, R2 MULF #60.0, R2
ADDF R2, R1 MOVF R1, id1 t1 = id3 * 60.0 id1 = id2 + t1  三地址中间代码 符 号 表 position initial rate . . . 1 2 3  汇编代码

18 1.1 编译器概述 解释器和编译器的区别 解释器也需要对源程序进行词法、语法和语义分析,中间代码生成
解释器不生成目标代码，而是直接执行源程序所指定的运算 词法分析器 语法分析器 语义分析器 源程序 中间代码生成器 独立于机器的代码优化器 代码生成器 依赖于机器的代码优化器 目标机器代码

19 1.1 编译器概述 BASIC年代的解释器 Java年代的解释器
功能：它将高级语言的源程序翻译成一种中间语言程序，然后对中间语言程序进行解释执行 在那个年代，编译和解释两个功能是合在一个程序中，该程序被称为解释器 Java年代的解释器 上述两个功能分在两个程序中 前一个叫做编译器，它把源程序翻译成一种叫做字节码的中间语言程序 后一个叫做解释器，它对字节码程序进行解释执行

20 1.1 编译器概述 阶段分组 前端 后端 源程序 词法分析器 语法分析器 代码生成器 语义分析器 中间代码生成器 目标机器代码
独立于机器的代码优化器 代码生成器 依赖于机器的代码优化器 目标机器代码

21 1.1 编译器概述 阶段分组 遍 源程序 词法分析器 语法分析器 代码生成器 语义分析器 中间代码生成器 目标机器代码
独立于机器的代码优化器 代码生成器 依赖于机器的代码优化器 目标机器代码

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

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

24 1.2 编译器技术的应用 针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要 并行化
1.2 编译器技术的应用 针对计算机体系结构的优化 计算机体系结构的迅速演化引起对新的编译器技术一种不知足的需要 并行化  编译器重新整理指令，使得指令级并行更有效  编译器从传统的串行程序自动生成并行代码，使之运行于多处理器上 内存分层  编译器优化历来集中在优化处理器的执行上，但是现在更强调要使内存分层更有效

25 1.2 编译器技术的应用 新计算机体系结构的设计 现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码
1.2 编译器技术的应用 新计算机体系结构的设计 现在计算机系统的性能不仅仅取决于它的原始速度，还取决于编译器是否能生成充分利用其特征的代码 在现代计算机体系结构的研究中，在处理器的设计阶段就开发编译器，并将编译生成的代码在模拟器上运行，以评价拟采用体系结构的特征 编译器技术影响计算机体系结构设计的一个著名例子是精简指令集计算机（RISC）的发明

26 1.2 编译器技术的应用 程序翻译 二进制翻译 编译器技术可用于把一种机器的二进制代码翻译成另一种机器的代码，以运行原先为别的指令集编译的代码 数据库查询解释器 数据库查询由一些谓词组成，这些谓词由包含关系运算的布尔表达式组成，可以被解释执行,也可以被编译成搜索数据库的命令

27 1.2 编译器技术的应用 提高软件开发效率的工具 源于编译器中代码优化技术的程序分析一直在 改进软件开发效率 类型检查
1.2 编译器技术的应用 提高软件开发效率的工具 源于编译器中代码优化技术的程序分析一直在 改进软件开发效率 类型检查 类型检查是一种捕捉程序中前后不一致的成熟而有效的技术 边界检查 数据流分析技术可用来定位缓冲区溢出 内存管理 自动的内存管理删除内存泄漏等内存管理错误