中国科技大学编译技术及原理50讲视频

中国科技大学 编译技术及原理 50讲 视频教程下载，由陈意云主讲. 

课程介绍 

一、课程发展历史概述

编译器产生于20世纪60年代，在计算机科学技术的发展过程中发挥着巨大的作用，是开发计算机应用系统不可缺少的重要工具。编译器的原理和技术具有十分普遍的意义，在每一个计算机科技工作者的职业生涯中，这些原理和技术都被反复用到。编译器的设计涉及到形式语言和自动机理论、编程语言和类型理论、计算机体系结构、算法设计和软件工程等多个学科的知识。

第一个编译器诞生后不久，国外就开设了编译原理课程，并且随着相关理论和技术的不断发展和完善，课程内容在不断地更新、充实和深化。例如：

语法分析从介绍递归下降和算符优先分析方法过渡到主要介绍LR语法分析方法及语法分析器的自动生成；

语义分析从分离地介绍各个问题的解决办法到系统地介绍基于属性文法的语法制导定义及其实现方法；

运行时存储空间的组织和管理从静态分配、栈式分配、堆分配一直发展到增加垃圾收集算法；

代码优化从孤立地介绍各种优化技术到突出介绍数据流分析的理论基础，强调在数据流分析的一般框架下解决各个具体数据流问题。

编译原理课程自开设以来，一直是计算机科学技术专业学生的必修课程。

中国科学技术大学计算机专业在1958年由老一辈计算机科学家夏培肃院士等亲自创办。创办之初就参与了中科院计算所自主设计并研制成功的我国第1台通用计算机—107机的研制。1980年前后就开设了编译原理课程，由中科院计算所研究人员主讲，采用他们基于开发BCY语言（类ALGOL60语言）编译器的经验编写的讲义。1982年成立计算机科学技术系时，由王汝传老师（现在是南京邮电大学博导）采用自编讲义主讲编译原理，以介绍编译器各逻辑阶段的流程图为课程的主要内容。

1984年改由完成过Pascal语言编译器开发的陈意云老师主讲编译原理，从那时起到目前为止，编译原理课程的师资队伍中，除个别人外，都从事编程语言的理论和实现技术方面的研究工作，从而都很好地具备从事编译原理教学所需的理论和技术背景。

中国科学技术大学计算机专业编译原理课程1984年开始采用陈火旺、钱家骅和孙永强编写的教材《程序设计语言编译原理》（国防工业出版社，1984）；1987年开始在教学中补充Compilers: principles, techniques, and tools（Alfred V. Aho, Ravi Sethi Jeffrey, D. Ullman. New York: Addison-Wesley, 1986）书上有关属性文法和类型检查等方面的内容；1990年开始采用陈意云根据上述经典教材编写的教材。随着教学经验和相关科研工作的积累，对编译原理课程讲授内容和方法逐步形成自己的观点。为此，教材内容也在不断调整，现在采用的是陈意云和张昱编写的《编译原理》（高等教学出版社，第二版，2008）。

编译原理的课程实践从1984年开始，以实现扩展PL/0语言到扩展PL/0抽象机的编译器和实现扩展PL/0抽象机的解释器为内容。这个实验的内容经不断充实，一直持续到2000年以后。2007年开始实施新的课程实践，它以“源语言－抽象语法树－低级中间表示－汇编代码的内部表示－x86/MIPS汇编”为主线搭建的课程实践体系，安排了各种循序渐进、规模适度、“综观全局、实现局部”、强调工程质量规范的课程设计，并提供配套的实验支持库和课程设计开发包。

二、课程内容体系结构

近十年来，我们基于下面观点不断进行教学内容更新、教学方法改革和教材编写：

1、强调主线：让学生在宏观上理解和全局上把握编译原理和技术比掌握一些细节算法重要得多。

2、重视编程语言有关理论和形式方法：这对深刻理解和把握编译原理和技术是必要的。 

3、鼓励将所学理论和技术用于解决或解释实际问题：这些问题源于学生编写、编译和运行程序的实践，能激发学生学习本课程的兴趣。

4、跟踪新技术：及时将新技术反映在教学中，利于学生了解技术的动态和发展趋势。

课程内容粗略地可以分成如下几个板块（板块并非完全对应教材的章节）：

1、编译器各逻辑阶段的功能、接口和所采用的主要技术

该部分包括词法分析、语法分析、类型检查（静态语义分析）、中间代码生成、代码生成和独立于机器的优化。此外，还有学习代码生成部分必不可少的运行时存储空间的组织和管理。该部分构成编译原理课程的核心。

2、和编译技术相关的理论知识

该部分包括形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统、数据流分析的理论基础。这是深入把握编程语言及其实现技术的必备知识。

3、和编译及编程相关的一些实用知识

该部分强调编译知识与实际编写、编译和运行程序的联系，它包括：

用编译原理的知识分析实际编写、编译和运行程序中碰到问题的例题或习题。

编译系统和运行系统（其中无用单元收集部分因课时压缩到60学时而从未作为课堂教学内容）。

依赖于机器的优化。依赖于体系结构的优化涉及一些复杂算法，不太可能作为本科生编译原理课程的内容，但是简要介绍现代计算机体系结构、指令调度、基本块调度、全局调度、软件流水、并行性和数据局部性优化等，会引导学生关注如何编写高效的程序。

4、其它范型（paradigm）的编程语言的编译技术

该部分简要介绍面向对象语言和函数式语言的编译（课时压缩到60学时后，函数式语言的编译未再继续作为教学内容），以拓宽对编程语言和编译技术的了解。

三、教学内容组织方式与目的

在教学内容的组织上有以下几个特点。

1、以编译的各逻辑阶段为主线，按照它们的逻辑次序逐个介绍，这和其他学校没有什么区别。但是，我们把相关理论都穿插在这些逻辑阶段的适当位置介绍，使学生及时体会到学习这些理论的必要性。

2、把学生的注意力集中到对编译原理和技术的宏观理解和全局把握上。对于一些枝节的算法，如计算开始符号集合和后继符号集合的算法、多态类型检查的合一算法、控制流翻译的回填技术等，仅介绍其思想而不讲具体算法，避免学生过于关注这些枝节算法。

3、及时把编译理论和技术的发展，特别是计算机体系结构的发展对编译技术的推动等新内容补充进入教学和教材，如安全语言和类型可靠性、数据流分析的理论基础等。并及时删除过时的内容，如实际编译器已经不再使用的算符优先分析方法。目的是让学生及时了解编译理论和技术方面的最新热点。

4、几乎每章都有理论联系实际的例题和习题，使学生体会到编译知识和日常编写、编译和运行程序是息息相关的。用编译原理的知识把这些问题分析清楚，对激发学习编译原理的热情有出人意料的效果。

5、介绍其它范型语言的编译时，用已学技术和方法能解决的词法和语法分析、静态语义分析等都不介绍，只讲语言特征的不同给编译器设计带来的问题和解决办法。这样，花的课时不多，但对理解编程语言和学习编译技术都很有帮助。

学习方法

一、主要学习方法

1、把握全局骨架胜过掌握局部算法

编译器是一个非常庞大而复杂的系统程序，不可能在一门课时间把所有的部分都搞清楚，因此对编译原理和技术的宏观理解及全局把握就显得十分重要。这需要课后多思考、提问和讨论，并且自己动手完成课程设计，才能达到较好效果。

本课程涉及很多具体算法，每个逻辑阶段都有，不可把注意力集中在记住这些算法上。

       2、重视理论知识的学习

       计算机科学与技术学科中不少知识领域或知识单元都是在本课程中给出初步介绍的，如形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统、数据流分析的一般框架等。它们是计算机专业理论知识的重要部分，在今后的职业生涯中，这些理论都被反复用到。在本书中结合应用来学习这些知识，有助于较快领会和掌握。切不可因为它们和设计一个小语言的编译器关系不大而忽视它们。

       3、联系日常编写、编译和运行程序的实际

       编译原理知识可用来分析和解决日常编写、编译和运行程序的实践中碰到的问题，注意联系实际会激发自己学习编译原理和技术的积极性。在我们编写的参考书《编译原理习题精选与解析》（高等教育出版社，2005.8）中，有很多从实际碰到的问题中抽象或抽取出的例题和习题，它们会增强学好编译原理课程的信心和能力。

       4、自己动手完成课程设计

自己动手完成一个小语言的编译器，对融会贯通课堂所学的原理和技术有非常大的作用。由于该课程设计是一项综合性的工程实践，对提高软件开发能力也有极大帮助。

为达到最好的效果，应该注意下面几点：

课程开始阶段就应该做技术准备：Java语言的学习、编程工具与环境的熟悉；

先行完成《编译原理实验教程》（高等教育出版社，2009.3）中的一些小实验，以积累一点经验；

在教师布置综合级实验后，要有不怕疲劳和连续作战的精神，严格按照时间节点的要求提交中间结果和最后成果。自己动手完成该课程实践后，一定会认为非常值得。

二、学习难点与重点

       1、学习重点

语法分析的各种方法：这是理解编程语言的语法设计和类型系统必不可少的部分。

语法制导的翻译：是学习后面几章的基础知识，并且不是很容易掌握。

运行时存储空间的组织和管理：对理解目标程序运行时的程序状态，对实际开发中定位和排除程序错误都极为重要。

       2、学习难点

LR分析方法：算法比较复杂，要两次课才能讲完，并且手工构造一个非常简单的语言的分析表也需要几个小时。

继承属性及其计算方法：继承属性依赖上下文，其计算不是简单地自下而上遍历分析树能完成的，可能会涉及对分析树的多次遍历。

数据流分析的一般框架：涉及偏序关系、格、数据流等式、迭代求解算法等多方面知识。

教学大纲

课程名称 编译原理和技术

英文名称 Principles and Techniques of Compilers

课程编号 01113300           总学时  60    学分  3.5

预修课程 数据结构、汇编语言程序设计、C语言程序设计      开课学期 春 或 秋

大纲撰写人 陈意云

一、教学目标和基本要求

       本课程是高校计算机科学与技术专业的专业基础课，目的是让学生对程序设计语言的设计和实现技术有深刻的理解，对和程序设计语言有关的理论有所了解，并能把本课程讨论的概念和技术用到软件设计和开发中。

二、课程简介

本课程介绍编译器构造的一般原理、基本设计方法和主要实现技术，其内容包括词法分析、语法分析、语义分析、类型检查、运行时存储空间的组织和管理、中间代码生成、代码优化、目标代码生成、编译系统和运行系统等。除了介绍命令式编程语言的编译技术外，本课程还介绍面向对象语言的实现技术。本课程还强调一些相关的理论知识，如形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统、数据流分析的一般框架等。

三、教学重点、难点

       教学重点：语法分析的各种方法、语法制导的翻译、运行时存储空间的组织和管理。

       教学难点：LR分析方法、继承属性及其计算方法、数据流分析的一般框架。

四、教材名称及主要参考书

       教材：陈意云、张昱.《编译原理》（第二版），北京：高等教育出版社，2008。

       主要参考书：

[1] AHO A V, LAM M S, SETHI R, et al. Compilers: Principles, Techniques and Tools. 2nd, ed. New York: Addison-Wesley, 2007.

       [2] APPEL A W. Modern Compiler Implementation in C. Cambridge Eng.: Cambridge University Press, 1998.

[3] AHO A V, SETHI R, ULLMAN J D. Compilers: principles, techniques, and tools. New York: Addison-Wesley, 1986.

       [4] APPEL A W. Modern Compiler Implementation in Java. Cambridge Eng.: Cambridge University Press, 1998.

[5] WILHELM R., MAURER D. Compiler design. New York: Addison-Wesley, 1995.

[6] MUCHNICK S S. Advanced compiler design and implementation. Hong Kong: Morgan Kaufmann Publishers, 1997.

[7] LEVINE J R. Linkers and loaders. Hong Kong: Morgan Kaufmann Publishers, 1999.

五、课程章节主要内容及学时分配

第1章 引论（2学时）

       通过简要描述编译器的各个组成部分以及编译器技术的各种应用来介绍编译这个课题。

1.1编译器概述（1.5学时）

       1.2 编译器技术的应用（0.5学时）

第2章 词法分析（5学时）

       重点围绕词法分析器的自动生成展开，先介绍与之有关的正规式和有限自动机概念，然后介绍词法分析器的自动生成方法，最后介绍一个词法分析器自动生成工具Lex。

2.1 词法记号及属性（0.5学时）

2.2 词法记号的描述与识别（1.5学时）

2.3 有限自动机（2学时）

       2.4 从正规式到有限自动机（0.5学时）

2.5 词法分析器的生成器（0.5学时）

第3章 语法分析（10学时）

       阐述编译器采用的典型语法分析方法。首先提出有关上下文无关文法的基本概念，然后介绍适合于手工实现的预测分析技术，最后给出语法分析器自动工具使用的LR分析算法。本章还扩展所介绍的分析方法，使之能从常见的错误中恢复过来。

3.1 上下文无关文法（1学时）

3.2 语言和文法（2学时）

3.3 自上而下分析（2学时）

3.4 自下而上分析（0.5学时）

3.5 LR分析器（3学时）

3.6 二义文法的应用（1学时）

3.7 语法分析器的生成器（0.5学时）

第4章 语法制导的翻译（6学时）

       讨论语义规则和产生式相联系的两种方式：语法制导的定义和语法制导的翻译方案，还讨论它们的实现方法。

4.1 语法制导的定义（1学时）

4.2  S属性定义的自下而上计算（2学时）

4.3  L属性定义的自上而下计算（2学时）

4.4  L属性的自下而上计算（1学时）

第5章 类型检查（6学时）

       以类型检查为代表，介绍编译器的静态检查工作。主要介绍简单类型系统的设计、多态类型概念、类型表达式的等价和算符的重载。

5.1 类型在编程语言中的作用（1学时）

5.2 描述类型系统的语言（0.5学时）

5.3 一个简单类型检查器的规范（1学时）

5.4 多态函数（2学时）

5.5 类型表达式的等价（0.5学时）

5.6 函数和算符的重载（1 学时）

第6章 运行时存储空间的组织和管理（6学时）

在考虑代码生成之前，需要讨论静态的程序正文和运行时的过程活动之间的联系，考察静态的名字和运行时数据对象之间的绑定关系。不仅要讨论一个活动记录中的数据安排，还要讨论程序执行过程中，所有存活过程活动的活动记录的组织方式。

6.1 局部存储分配（1.5学时）

6.2 全局栈式存储分配（3学时）

6.3 非局部名字的访问（1学时）

6.4 参数传递（0.5学时）

第7章 中间代码生成（5学时）

介绍几种常用的中间表示，并用语法制导定义方法来描述编程语言的构造怎样被翻译成独立于机器的中间表示。

7.1 中间语言（1学时）

7.2 声明语句（1学时）

7.3 赋值语句（1学时）

7.4 布尔表达式和控制流语句（2学时）

第8章 代码生成（3学时）

基于一种简单的机器模型，介绍一种简单的代码生成算法。

8.1 代码生成器设计中的问题（0.5学时）

8.2 目标语言（0.5学时）

8.3 基本块和流图（1学时）

8.4 一个简单的代码生成器（1学时）

第9章 独立于机器的优化（12学时）

       先通过一个简单的实例来了解代码优化；然后介绍数据流分析，它包括几类重要的全局收集且随后用于代码改进变换的信息。进一步介绍数据流分析框架的一般思想，并基于此框架来介绍常量传播和部分冗余删除优化，最后讨论程序中循环的发现和分析。

9.1 优化的主要种类（2学时）

9.2 数据流分析介绍（2学时）

9.3 数据流分析的基础（2学时）

       9.4 常量传播（2学时）

       9.5 部分冗余删除（2学时）

       9.6 流图中的循环（2学时）

第10章 编译系统和运行系统（3学时）

介绍编译器的伙伴程序，它们包括预处理器、汇编器和连接器等工具；还介绍Java的运行系统。

10.1 C语言的编译系统（2学时）

       10.2 Java语言的运行系统（1学时）

第11章 面向对象语言的编译（2学时）

回顾面向对象语言的一些重要概念，概述它们的实现技术。为突出一些重要概念的实现技术，本章以C++语言为例，介绍如何将C++程序翻译成C程序。

       11.1 面向对象语言的概念（0.5学时）

       11.2 方法的编译（0.5学时）

       11.3 继承的编译方案（1学时）

 课程介绍

一、课程发展历史概述

编译器产生于20世纪60年代，在计算机科学技术的发展过程中发挥着巨大的作用，是开发计算机应用系统不可缺少的重要工具。编译器的原理和技术具有十分普遍的意义，在每一个计算机科技工作者的职业生涯中，这些原理和技术都被反复用到。编译器的设计涉及到形式语言和自动机理论、编程语言和类型理论、计算机体系结构、算法设计和软件工程等多个学科的知识。

第一个编译器诞生后不久，国外就开设了编译原理课程，并且随着相关理论和技术的不断发展和完善，课程内容在不断地更新、充实和深化。例如：

语法分析从介绍递归下降和算符优先分析方法过渡到主要介绍LR语法分析方法及语法分析器的自动生成；

语义分析从分离地介绍各个问题的解决办法到系统地介绍基于属性文法的语法制导定义及其实现方法；

运行时存储空间的组织和管理从静态分配、栈式分配、堆分配一直发展到增加垃圾收集算法；

代码优化从孤立地介绍各种优化技术到突出介绍数据流分析的理论基础，强调在数据流分析的一般框架下解决各个具体数据流问题。

编译原理课程自开设以来，一直是计算机科学技术专业学生的必修课程。

中国科学技术大学计算机专业在1958年由老一辈计算机科学家夏培肃院士等亲自创办。创办之初就参与了中科院计算所自主设计并研制成功的我国第1台通用计算机—107机的研制。1980年前后就开设了编译原理课程，由中科院计算所研究人员主讲，采用他们基于开发BCY语言（类ALGOL60语言）编译器的经验编写的讲义。1982年成立计算机科学技术系时，由王汝传老师（现在是南京邮电大学博导）采用自编讲义主讲编译原理，以介绍编译器各逻辑阶段的流程图为课程的主要内容。

1984年改由完成过Pascal语言编译器开发的陈意云老师主讲编译原理，从那时起到目前为止，编译原理课程的师资队伍中，除个别人外，都从事编程语言的理论和实现技术方面的研究工作，从而都很好地具备从事编译原理教学所需的理论和技术背景。

中国科学技术大学计算机专业编译原理课程1984年开始采用陈火旺、钱家骅和孙永强编写的教材《程序设计语言编译原理》（国防工业出版社，1984）；1987年开始在教学中补充Compilers: principles, techniques, and tools（Alfred V. Aho, Ravi Sethi Jeffrey, D. Ullman. New York: Addison-Wesley, 1986）书上有关属性文法和类型检查等方面的内容；1990年开始采用陈意云根据上述经典教材编写的教材。随着教学经验和相关科研工作的积累，对编译原理课程讲授内容和方法逐步形成自己的观点。为此，教材内容也在不断调整，现在采用的是陈意云和张昱编写的《编译原理》（高等教学出版社，第二版，2008）。

编译原理的课程实践从1984年开始，以实现扩展PL/0语言到扩展PL/0抽象机的编译器和实现扩展PL/0抽象机的解释器为内容。这个实验的内容经不断充实，一直持续到2000年以后。2007年开始实施新的课程实践，它以“源语言－抽象语法树－低级中间表示－汇编代码的内部表示－x86/MIPS汇编”为主线搭建的课程实践体系，安排了各种循序渐进、规模适度、“综观全局、实现局部”、强调工程质量规范的课程设计，并提供配套的实验支持库和课程设计开发包。

二、课程内容体系结构

近十年来，我们基于下面观点不断进行教学内容更新、教学方法改革和教材编写：

1、强调主线：让学生在宏观上理解和全局上把握编译原理和技术比掌握一些细节算法重要得多。

2、重视编程语言有关理论和形式方法：这对深刻理解和把握编译原理和技术是必要的。 

3、鼓励将所学理论和技术用于解决或解释实际问题：这些问题源于学生编写、编译和运行程序的实践，能激发学生学习本课程的兴趣。

4、跟踪新技术：及时将新技术反映在教学中，利于学生了解技术的动态和发展趋势。

课程内容粗略地可以分成如下几个板块（板块并非完全对应教材的章节）：

1、编译器各逻辑阶段的功能、接口和所采用的主要技术

该部分包括词法分析、语法分析、类型检查（静态语义分析）、中间代码生成、代码生成和独立于机器的优化。此外，还有学习代码生成部分必不可少的运行时存储空间的组织和管理。该部分构成编译原理课程的核心。

2、和编译技术相关的理论知识

该部分包括形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统、数据流分析的理论基础。这是深入把握编程语言及其实现技术的必备知识。

3、和编译及编程相关的一些实用知识

该部分强调编译知识与实际编写、编译和运行程序的联系，它包括：

用编译原理的知识分析实际编写、编译和运行程序中碰到问题的例题或习题。

编译系统和运行系统（其中无用单元收集部分因课时压缩到60学时而从未作为课堂教学内容）。

依赖于机器的优化。依赖于体系结构的优化涉及一些复杂算法，不太可能作为本科生编译原理课程的内容，但是简要介绍现代计算机体系结构、指令调度、基本块调度、全局调度、软件流水、并行性和数据局部性优化等，会引导学生关注如何编写高效的程序。

4、其它范型（paradigm）的编程语言的编译技术

该部分简要介绍面向对象语言和函数式语言的编译（课时压缩到60学时后，函数式语言的编译未再继续作为教学内容），以拓宽对编程语言和编译技术的了解。

三、教学内容组织方式与目的

在教学内容的组织上有以下几个特点。

1、以编译的各逻辑阶段为主线，按照它们的逻辑次序逐个介绍，这和其他学校没有什么区别。但是，我们把相关理论都穿插在这些逻辑阶段的适当位置介绍，使学生及时体会到学习这些理论的必要性。

2、把学生的注意力集中到对编译原理和技术的宏观理解和全局把握上。对于一些枝节的算法，如计算开始符号集合和后继符号集合的算法、多态类型检查的合一算法、控制流翻译的回填技术等，仅介绍其思想而不讲具体算法，避免学生过于关注这些枝节算法。

3、及时把编译理论和技术的发展，特别是计算机体系结构的发展对编译技术的推动等新内容补充进入教学和教材，如安全语言和类型可靠性、数据流分析的理论基础等。并及时删除过时的内容，如实际编译器已经不再使用的算符优先分析方法。目的是让学生及时了解编译理论和技术方面的最新热点。

4、几乎每章都有理论联系实际的例题和习题，使学生体会到编译知识和日常编写、编译和运行程序是息息相关的。用编译原理的知识把这些问题分析清楚，对激发学习编译原理的热情有出人意料的效果。

5、介绍其它范型语言的编译时，用已学技术和方法能解决的词法和语法分析、静态语义分析等都不介绍，只讲语言特征的不同给编译器设计带来的问题和解决办法。这样，花的课时不多，但对理解编程语言和学习编译技术都很有帮助。