编译原理课程是一门专门学习与研究程序设计语言的实现技术的课程，在计算机科学领域有着及其重要的地位。全书以浅显的语言引入编译原理的基本概念，分章对程序语言、语言分析基础，程序设计语言常用语法与翻译方法、词法分析、自上而下的语法分析、自下而上的语法分析、运行时存储空间管理、优化及目标代码生成等内容进行了详细的讲解。本书适用于高等院校计算机专业本科教材，也可供教师、研究生及有关科技工作者学习和参考。

        编写这本教材的初衷在于：现有的教材基本上是面向高等教育的课本，编者的教学是面向大众的高等教育。编译原理在计算机教学体系中被认为是较难的课程，学生们在学习时往往感到十分吃力。因此，本书的编写宗旨就是“浅显易懂”。



        本书共10章。第1章为“编译的基本概念”，讲述了编译程序的功能、结构、工作过程和结构方式。第2章为“程序语言”，分析了程序设计语言作为一种人工语言的特性，介绍了一些语言要素及几种不同程序语言的特点。第3章为“语言分析基础”，介绍了一些形式语言理论。这些理论有助于理解编译程序的构造与方法，并着重介绍了上下无关文法。第4章为“程序设计语言常用语法与翻译方法”，这一章的目的在于尽早地建立高级语言到目标语言翻译过程的概念，并以此概念统领以后各章的理解。第5章为“词法分析”，从此章开始深入研究编译程序的构造原理。本章首先介绍了描述词的形式化方法：正规表达式；接着讨论了作为实现正规表达式有效工具的算法：有限自动机及它的确定化和最小化；另外还介绍了正规文法与正规表达式的对应关系。第6章为“自上而下的语法分析”，此章为构造语法分析程序方法的前半部分内容，主要介绍LL(1)分析方法和递归下降分析方法。第7章为“自下而上的语法分析”，介绍如何用算符优先、LR(0)、SLR(1)、LR(1)和LALR分析方法构造语法分析程序。第8章为“语法制导翻译”，主要讨论了语法制导翻译方法的基本原理、属性翻译文法以及它们在中间代码生成中的应用。第9章为“运行时存储空间管理”，主要介绍编译后的可执行程序在运行过程中内存的分配策略。其中包括对应不同语言的分配技术，以及过程调用、参数传递、数组和记录的存取方式。第10章为“优化及目标代码生成”，介绍优化的概念和方法。即如何使编译程序生成的代码在执行时更为有效；同时简单讨论汇编语言形式目标代码的生成原理。

本书的第一版出版至今已两年有余。有很多师生、同行使用过本教材，并给予好评。对此本人深表谢意；同时对第一版中出现较多的文字错误、编辑错误及印刷错误倍感不安。此次再版的主旨即为对前版的勘误，并对因前版中的错误给读者造成的不便深表歉意。

第1章  编译的基本概念 1

1.1  为什么需要编译程序 1

1.2  编译的基本过程 2

习题 10

第2章  程序语言 11

2.1  高级语言 11

2.1.1  高级语言的分类 11

2.1.2  数据类型及其操作 12

2.1.3  语句与表达式 14

2.1.4  程序的结构 16

2.2  中间语言 18

2.2.1  逆波兰表示法 18

2.2.2  三地址代码 19

习题 21

第3章  语言分析基础 22

3.1  语言和语法 22

3.2  产生式 23

3.3  上下文无关文法及其语言 23

3.3.1  上下文无关文法的基本概念 24

3.3.2  上下文无关文法所定义的语言 25

3.4  语法树与抽象语法树 28

3.4.1  语法树 28

3.4.2  二义文法 28

3.4.3  抽象语法树 29

3.5  上下文无关文法的设计 30

3.5.1  文法设计基础 30

3.5.2  消除二义性 32

3.6  形式语言浅述 34

3.6.1  语言的组成 35

3.6.2  产生式文法 36

3.6.3  乔姆斯基文法分类 36

习题 38

第4章  程序设计语言常用语法与翻译方法 40

4.1  程序设计语言常用语法 40

4.1.1  表达式语法（算术） 40

4.1.2  赋值语句 41

4.1.3  if语句 41

4.1.4  循环语句 42

4.1.5  说明语句 42

4.1.6  函数的定义与调用 43

4.1.7  程序语句序列文法 43

4.2  中间代码的翻译 44

4.2.1  表达式中间代码生成 44

4.2.2  if语句中间代码生成 46

4.2.3  布尔表达式代码生成 49

4.2.4  循环语句中间代码 51

4.2.5  综合实例 52

习题 54

第5章  词法分析 55

5.1  词法与正规式 55

5.2  有限状态自动机 57

5.2.1  确定有限自动机（DFA） 57

5.2.2  非确定有限自动机（NFA） 62

5.2.3  从DFA到NFA的转换 63

5.2.4  从NFA到DFA的转换 65

5.2.5  确定有限自动机的化简 69

5.3  从自动机到正规式的转换 72

5.4  正规文法与有限自动机的等价性 74

5.5  正规文法与正规式 76

习题 77

第6章  自上而下的语法分析 80

6.1  自上而下语法分析概论 80

6.2  适合自上而下分析的文法 81

6.2.1  左递归的消除 81

6.2.2  消除回溯与提取左因子 84

6.3  LL(1)分析法 85

6.3.1  LL(1)分析的基本方法 85

6.3.2  LL(1)文法 86

6.3.3  求FIRST集合 87

6.3.4  求FOLLOW 集合 91

6.3.5  预测分析程序 95

6.4  递归下降分析程序 98

习题 99

第7章  自下而上的语法分析 102

7.1  自下而上语法分析概论 102

7.1.1  归约的概念 102

7.1.2  归约的问题 104

7.1.3  规范归约 104

7.2  算符优先分析 106

7.2.1  优先关系与算符优先文法 106

7.2.2  算符优先关系表的构造算法 108

7.2.3  算符优先分析算法 109

7.2.4  优先函数 113

7.3  LR分析法 114

7.3.1  LR分析 114

7.3.2  LR(0)项目集和LR(0)分析表的构造 119

7.3.3  SLR分析表的构造 122

7.3.4  规范LR分析表的构造 125

7.3.5  LALR分析表的构造 128

习题 132

第8章  语法制导翻译 135

8.1  属性文法 135

8.1.1  属性文法的概念 135

8.1.2  依赖图 139

8.1.3  综合属性与S属性文法 140

8.1.4  继承属性及其计算 142

8.2  符号表 145

8.2.1  符号表的组织与作用 145

8.2.2  符号表数据内容及查找 146

8.2.3  名字的作用域 147

8.3  翻译中间代码属性 149

8.3.1  算术表达式及赋值语句的翻译 150

8.3.2  控制语句的翻译 152

习题 159

第9章  运行时存储空间管理 161

9.1  程序运行时的存储环境 161

9.2  静态存储分配 163

9.3  基于栈的运行时存储器管理 164

9.3.1  简单的栈式存储管理 164

9.3.2  过程可局部定义的栈式存储管理 168

9.4  参数传递机制 172

9.4.1  值传递 173

9.4.2  地址传递 173

9.4.3  值结果传递 174

9.4.4  名字传递 176

习题 177

第10章  优化及目标代码生成 181

10.1  局部优化 181

10.1.1  基本块 181

10.1.2  基本块中的等价代换 182

10.2  全局优化 183

10.3  循环优化 185

10.3.1  外提不变式 186

10.3.2  强度削弱 187

10.3.3  删除基本归纳变量 188

10.4  目标代码生成 189

10.4.1  基本问题 189

10.4.2  目标机器模型 191

10.4.3  一个简单的代码生成器 191

10.4.4  寄存器的分配 194

习题 194

附录  部分习题详解 197

参考文献 267

无