编译原理
分享
课程详情
课程评价
spContent=本课程主要讲授编译器设计与实现的主要理论和技术。内容包括词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等。本课程主要面向计算机相关专业学生、以及相关技术的从业人员等。
—— 课程团队
课程概述

    同学们可能都有过使用高级程序设计语言编写程序的经历。当我们给计算机输入一段程序以后,计算机就可以按照我们的意图去工作。我们都知道,由0和1构成的机器代码才是可以被计算机直接理解的语言。因此,用高级语言编写的程序,最终都要“翻译”成由0和1构成的机器代码才可以在计算机上执行,这一翻译过程,就称为编译。那么,计算机是如何将高级程序设计语言编写的程序自动翻译成机器代码的呢?通过这么课程的学习,我们就可以找到答案。

世界著名的计算机科学家Alfred V.Aho在他的经典著作《编译器》的第1章第1句话写道:“编写编译器的原理和技术具有十分普遍的意义,以至于在每个计算机科学家的研究生涯中,本课程中的原理和技术都会反复用到。”这句话点明了编译原理这门课程在计算机专业中的重要地位。

本课程共计20讲。

1 绪论

2 程序设计语言及其文法

3 词法分析

4讲 语法分析_1

5讲 语法分析_2

6 语法分析_3

7 语法分析_4

8 语法制导翻译_1

9 语法制导翻译_2

10 语法制导翻译_3

11 中间代码生成_1

12 中间代码生成_2

13 中间代码生成_3

14 中间代码生成_4

15 运行存储分配

16 代码优化_1

17 代码优化_2

18 代码优化_3

19 代码优化_4

20 代码生成

课程大纲

第1讲 绪论

1-1 什么是编译

1-2 编译系统的结构

1-3 词法分析概述

1-4 语法分析概述

1-5 语义分析概述

1-6 中间代码生成及编译器后端概述

第2讲 程序设计语言及其文法

2-1 基本概念

2-2 文法的定义

2-3 语言的定义

2-4 文法的分类

2-5 CFG的分析树

第3讲 词法分析

3-1 正则表达式

3-2 正则定义

3-3 有穷自动机

3-4 有穷自动机的分类

3-5 从正则表达式到有穷自动机

3-6 从NFA到DFA的转换

3-7 识别单词的DFA

第4讲 语法分析_1

4-1 自顶向下分析概述

4-2 文法转换

4-3 LL(1)文法

第5讲 语法分析_2

4-4 FIRST集和FOLLOW集的计算

4-5 递归的预测分析法

4-6 非递归的预测分析法

4-7 预测分析中的错误处理

第6讲 语法分析_3

4-8 自底向上分析概述

4-9 LR分析法概述

4-10 LR(0)分析

4-11 LR(0)分析表构造算法

第7讲 语法分析_4

4-12 SLR分析

4-13 LR(1)分析

4-14 LALR分析法

4-15 二义性文法的LR分析

4-16 LR分析中的错误处理

第8讲 语法制导翻译_1

5-1 语法制导翻译概述

5-2 语法制导定义SDD

5-3 SDD的求值顺序

5-4 S-属性定义与L-属性定义

第9讲 语法制导翻译_2

5-5 语法制导翻译方案SDT

5-6 在非递归的预测分析过程中进行翻译

第10讲 语法制导翻译_3

5-7 在递归的预测分析过程中进行翻译

5-8 L-属性定义的自底向上翻译

第11讲 中间代码生成_1

6-1 类型表达式

6-2 声明语句的翻译

第12讲 中间代码生成_2

6-3 简单赋值语句的翻译

6-4 数组引用的翻译

第13讲 中间代码生成_3

6-5 控制流语句及其SDT

6-6 布尔表达式及其SDT

6-7 控制流翻译的例子

第14讲 中间代码生成_4

6-8 布尔表达式的回填

6-9 控制流语句的回填

6-10 switch语句的翻译

6-11 过程调用语句的翻译

第15讲 运行存储分配

7-1 运行存储分配概述

7-2 静态存储分配

7-3 栈式存储分配

7-4 调用序列和返回序列

7-5 非局部数据的访问

7-6 符号表

7-7 符号表的建立

第16讲 代码优化_1

8-1 流图

8-2 常用的代码优化方法(一)

8-3 常用的代码优化方法(二)

8-4 基本块的优化

第17讲 代码优化_2

8-5 数据流分析

8-6 到达定值分析

8-7 到达定值方程的计算

第18讲 代码优化_3

8-8 活跃变量分析

8-9 可用表达式分析

第19讲 代码优化_4

8-10 支配结点和回边

8-11 自然循环及其识别

8-12 删除全局公共子表达式和复制语句

8-13 代码移动

8-14 作用于归纳变的强度削弱

8-15 归纳变量的删除

第20讲 代码生成

9-1 代码生成器的主要任务

9-2 一个简单的目标机模型

9-3 指令选择

9-4 寄存器的选择

9-5 寄存器选择函数getReg的设计

9-6 窥孔优化

预备知识

高级程序设计语言

数据结构

集合与图论

证书要求

设置“合格”(达到60分)、"优秀"(达到85分)两档课程标准,由任课教师签发课程结业证书,其中成绩“优秀”者将颁发优秀证书。

参考资料

Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools (Second Edition). Pearson Education, Inc. 2006

Alfred Aho ect. 《编译原理》本科教学版,赵建华等译,机械工业出版社,2010.3

 


常见问题

Q:我将来不打算从事编译器的开发工作,为什么还要学习编译原理这门课程?

A:(1)首先,这门课程可以让我们更加深刻地理解高级语言程序的内部运行机制。例如,对于程序中声明的数据对象,在内存中是如何为它们分配空间的?在程序运行的某一时刻,既可以访问本过程声明的局部数据对象,还可以访问过程外声明的非局部数据,如何找到这些非局部数据?通过这门课程的学习,我们还可以了解到编译器是如何自动诊断出源程序中的错误并给出诊断信息的。同学们可能接触过很多种编程语言。但是,我们学习一门技术,不仅要知其然,还要知其所以然。同学们有没有思考过每一种语言为什么要这样定义语法?事实上,每一种语言的语法都不是随便定义的,其背后有着深刻的道理。编译原理就是这样一门课程,它教给我们隐藏在编程技术后面的基本原理。掌握了这些基本原理,无论语言如何更新换代,我们都能应对自如,不被技术的发展所淘汰。

(2)这门课教给我们的不只是编译器构造的基本原理和流程,同时,还教给我们如何严谨地去思考、编写程序。通过本课程的学习,我们对编程也会有更深入的了解。对于代码应该怎么写,为什么要那么写,怎么写更好,错误是如何出现的,如果出错的后果是什么等等都能有理论到实践的全面认识。

(3)本课程非常有助于锻炼我们的逻辑思维能力。编译原理蕴含了计算机科学解决问题的基本思路和方法,即 “形式化→自动化”。

(4)本课程涉及的理论和方法在自然语言处理、模式识别、人工智能等领域都会或多或少地被用到。

(5)真正写编译器几乎不会用到,但有可能写简单的脚本解释器或使用、修改别人的解释器。


Q:学习本课程之前是否需要先学习《形式语言与自动机理论》?

A:本课程内容只涉及到少许形式语言与自动机理论方面的知识,并且已将对相关知识的讲解渗透到了课程相关部分,因此,在学习本课程之前可以不必先学习《形式语言与自动机理论》。