课程概况
同学们可能都有过使用高级程序设计语言编写程序的经历。当我们给计算机输入一段程序以后，计算机就可以按照我们的意图去工作。我们都知道，由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 中间代码生成及编译器后端概述
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
【讨论1-1】编译过程与人工翻译过程之间的关系
【讨论1-2】符号表中NAME字段的设计
第1讲 测验（计分）
第2讲 程序设计语言及其文法
2-1 基本概念
2-2 文法的定义
2-3 语言的定义
2-4 文法的分类
2-5 CFG的分析树
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
【讨论2-1】计算机中是如何表示语言的？
【讨论2-2】每一类单词可否看成一种语言？
第2讲测验（计分）
第3讲 词法分析
3-1 正则表达式
3-2 正则定义
3-3 有穷自动机
3-4 有穷自动机的分类
3-5 从正则表达式到有穷自动机
3-6 从NFA到DFA的转换
3-7 识别单词的DFA
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第3讲测验（计分）
第4讲 语法分析_1
4-1 自顶向下分析概述
4-2 文法转换
4-3 LL(1)文法
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第4讲测验（计分）
4-4 FIRST集和FOLLOW集的计算
第5讲 语法分析_2
4-5 递归的预测分析法
4-6 非递归的预测分析法
4-7 预测分析中的错误处理
本讲模拟练习题(不计分）
本讲教学课件(PDF文档)
第5讲测验（计分）
第6讲 语法分析_3
4-8 自底向上分析概述
4-9 LR分析法概述
4-10 LR(0)分析
4-11 LR(0)分析表构造算法
本讲模拟练习题(不计分）
本讲教学课件(PDF文档)
【讨论6-1】下推自动机与有穷自动机之间的关系
【讨论6-2】LR语法分析栈中状态信息与文法符号信息之间的关系
第6讲测验（计分）
第7讲 语法分析_4
4-12 SLR分析
4-13 LR(1)分析
4-14 LALR分析法
4-15 二义性文法的LR分析
4-16 LR分析中的错误处理
本讲模拟练习题(不计分）
本讲教学课件(PDF文档)
【讨论7-1】为什么合并同心项集不会产生移进-归约冲突？
【讨论7-2】为什么LALR分析法不会作错误的移进操作？
第7讲测验（计分）
第8讲 语法制导翻译_1
5-1 语法制导翻译概述
5-2 语法制导定义SDD
5-3 SDD的求值顺序
5-4 S-属性定义与L-属性定义
本讲模拟练习题(不计分）
本讲教学课件(PDF文档)
【讨论8-1】如何表示语义信息？
【讨论8-2】如何计算语义属性？
【讨论8-3】如何判定一个属性是综合属性还是继承属性？
【讨论8-4】什么样的SDD可以保证存在对其属性进行计算的顺序？
【讨论8-5】为什么S-SDD与L-SDD能够保证存在属性计算顺序？
第8讲测验（计分）
第9讲 语法制导翻译_2
5-5 语法制导翻译方案SDT
5-6 在非递归的预测分析过程中进行翻译
本讲模拟练习题(不计分）
本讲教学课件(PDF文档)
【讨论9-1】为什么S-SDD的SDT可以在语法分析的过程中同时实现？
【讨论9-2】非递归预测分析器的扩展
第9讲测验（计分）
第10讲 语法制导翻译_3
5-7 在递归的预测分析过程中进行翻译
5-8 L-属性定义的自底向上翻译
本讲模拟练习题(不计分）
本讲教学课件(PDF文档)
【讨论10-1】递归预测分析器的扩展
【讨论10-2】文法及翻译方案的修改
第10讲测验（计分）
第11讲 中间代码生成_1
6-1 类型表达式
6-2 声明语句的翻译
本讲模拟练习题(不计分）
本讲教学课件(PDF文档)
【讨论11-1】如何计算数组的类型表达式及数组宽度？
第11讲测验（计分）
第12讲 中间代码生成_2
6-3 简单赋值语句的翻译
6-4 数组引用的翻译
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
【讨论12-1】数组元素寻址的翻译
第12讲测验（计分）
第13讲 中间代码生成_3
6-5 控制流语句及其SDT
6-6 布尔表达式及其SDT
6-7 控制流翻译的例子
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第13讲测验（计分）
第14讲 中间代码生成_4
6-8 布尔表达式的回填
6-9 控制流语句的回填
6-10 switch语句的翻译
6-11 过程调用语句的翻译
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第14讲测验（计分）
第15讲 运行存储分配
7-1 运行存储分配概述
7-2 静态存储分配
7-3 栈式存储分配
7-4 调用序列和返回序列
7-5 非局部数据的访问
7-6 符号表
7-7 符号表的建立
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
【讨论15-1】如何基于符号表构造访问链？
【讨论15-2】如何基于符号表访问非局部数据？
第15讲测验（计分）
第16讲 代码优化_1
8-1 流图
8-2 常用的代码优化方法（一）
8-3 常用的代码优化方法（二）
8-4 基本块的优化
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第16讲测验（计分）
第17讲 代码优化_2
8-5 数据流分析
8-6 到达定值分析
8-7 到达定值方程的计算
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第17讲测验（计分）
第18讲 代码优化_3
8-8 活跃变量分析
8-9 可用表达式分析
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第18讲测验（计分）
第19讲 代码优化_4
8-10 支配结点和回边
8-11 自然循环及其识别
8-12 删除全局公共子表达式和复制语句
8-13 代码移动
8-14 作用于归纳变的强度削弱
8-15 归纳变量的删除
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第19讲测验（计分）
第20讲 代码生成
9-1 代码生成器的主要任务
9-2 一个简单的目标机模型
9-3 指令选择
9-4 寄存器的选择
9-5 寄存器选择函数getReg的设计
9-6 窥孔优化
本讲模拟练习题(不计分)
本讲教学课件(PDF文档)
第20讲测验（计分）
预备知识
高级程序设计语言
数据结构
集合与图论
参考资料
Alfred Aho ect. 《编译原理》本科教学版，赵建华等译，机械工业出版社，2010.3
Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools (Second Edition). Pearson Education, Inc. 2006
编译原理 ISBN：978-7-04-029058-5主编：蒋宗礼 姜守旭 高等教育出版社
常见问题
Q：我将来不打算从事编译器的开发工作，为什么还要学习编译原理这门课程？
A：（1）首先，这门课程可以让我们更加深刻地理解高级语言程序的内部运行机制。例如，对于程序中声明的数据对象，在内存中是如何为它们分配空间的？在程序运行的某一时刻，既可以访问本过程声明的局部数据对象，还可以访问过程外声明的非局部数据，如何找到这些非局部数据？通过这门课程的学习，我们还可以了解到编译器是如何自动诊断出源程序中的错误并给出诊断信息的。同学们可能接触过很多种编程语言。但是，我们学习一门技术，不仅要知其然，还要知其所以然。同学们有没有思考过每一种语言为什么要这样定义语法？事实上，每一种语言的语法都不是随便定义的，其背后有着深刻的道理。编译原理就是这样一门课程，它教给我们隐藏在编程技术后面的基本原理。掌握了这些基本原理，无论语言如何更新换代，我们都能应对自如，不被技术的发展所淘汰。
（2）这门课教给我们的不只是编译器构造的基本原理和流程，同时，还教给我们如何严谨地去思考、编写程序。通过本课程的学习，我们对编程也会有更深入的了解。对于代码应该怎么写，为什么要那么写，怎么写更好，错误是如何出现的，如果出错的后果是什么等等都能有理论到实践的全面认识。
（3）本课程非常有助于锻炼我们的逻辑思维能力。编译原理蕴含了计算机科学解决问题的基本思路和方法，即 “形式化→自动化”。
（4）本课程涉及的理论和方法在自然语言处理、模式识别、人工智能等领域都会或多或少地被用到。
（5）真正写编译器几乎不会用到，但有可能写简单的脚本解释器或使用、修改别人的解释器。
Q：学习本课程之前是否需要先学习《形式语言与自动机理论》？
A：本课程内容只涉及到少许形式语言与自动机理论方面的知识，并且已将对相关知识的讲解渗透到了课程相关部分，因此，在学习本课程之前可以不必先学习《形式语言与自动机理论》。
