本书系统地阐述了编译系统的结构、工作流程、设计原理和实现技术。主要内容包括程序设计语言基本知识、词法分析、语法分析、语义分析与属性文法、语法制导的代码生成、运行时存储空间组织、代码生成与优化等。通过本书的学习，使学生掌握编译理论和方法的基本知识，具有设计实现、分析和维护编译程序方面的初步能力，提高学生科学思维能力和综合运用专业知识的能力与解决实际问题的能力。书中每章开始有本章简介，每章后面都有与内容紧密相关、难度适宜的习题，可以使学生更好地掌握本章所学的知识内容。

本书适合作为高等学校计算机及相关专业的教材，也可以作为考研学生的一本参考书。

编译原理是计算机专业中一门重要的专业课程。设置本课程的目的，在于系统地向学生讲述编译系统的结构、工作流程、设计原理和实现技术。通过本书的学习，使学生掌握在编译理论和方法方面的基本知识，也具有设计实现、分析和维护编译程序方面的初步能力，也可以提高学生科学思维能力和综合运用专业知识与解决实际问题的能力，所以这门课程在计算机专业体系中占有十分重要的地位。

编译原理是一门理论性和实践性都比较强的课程。编者在编写过程中，力图尽可能使本教材达到知识内容组织合理，由浅入深，循序渐进的目的。书中详细而系统地介绍了程序设计语言翻译的基本原理与方法，同时本书的特色主要体现在每章开始都有本章简介，章末均有小结，另外，每章后面都有与讲解内容紧密相关的习题，可以使学生更好地掌握所学的知识内容，也可以成为考研学生很好的一本参考书籍。本书共分为11章，第1~6章由西北工业大学计算机学院的康慕宁教授编写，第7~9章由西北农林科技大学信息工程学院的唐晶磊编写，第10、11章由西北农林科技大学信息工程学院的任国霞副教授编写。

我们特别感谢北京工业大学蒋宗礼教授，蒋教授对本书进行了仔细的审阅，提出了许多宝贵的意见及指导性的建议。这里也特别感谢清华大学出版社的大力支持，使本书得以顺利出版。

由于我们的能力有限，书中难免有一些错误和不足，敬请读者批评指正。

作 者

第1章 编译程序理论概述1

1.1 导言1

1.2 语言及其翻译1

1.3 语法的功能3

1.4 程序设计语言的发展4

1.5 编译程序的结构6

1.5.1 词法分析7

1.5.2 字符串表9

1.5.3 语法分析9

1.5.4 语义分析10

1.5.5 符号表10

1.5.6 代码优化程序10

1.5.7 代码生成程序11

1.6 特殊约定12

缩写词与关键字12

习题12

第2章 语法及其分类14

2.1 概述14

2.2 文法14

2.2.1 字母表与字符串14

2.2.2 非终结符与产生式15

2.2.3 文法的例子15

2.3 文法及语言的Chomskey分类17

2.4 规范推导18

2.5 文法的二义性19

习题20

编译原理目  录第3章 扫描器与正规语言22

3.1 词法分析程序简介22

3.2 正规表达式22

3.2.1 正规表达式代数23

3.2.2 正规表达式的性质24

3. 3 有限状态自动机27

3. 4 非确定的有限状态自动机29

3. 5 将正规文法转换为自动机30

3. 6 NDFA的确定化及化简33

3. 7 从有限状态自动机转换到正规文法40

3. 8 有限自动机在计算机中的实现40

3. 9 扫描器实现中的特殊问题42

3. 9. 1 输入符号表42

3. 9. 2 扫描器自动机中的终止状态42

3. 9. 3 删除空白符号与注释43

3. 9. 4 输出单词43

3. 10 字符串表的实现46

3.11 保留字47

3.12 使用扫描器自动生成工具48

缩写词与关键字48

习题48

第4章 语法分析与前后文无关文法51

4. 1 导论51

4. 2 下推自动机51

4. 2. 1 停机条件的等价性53

4. 2. 2 从前后文无关文法CFG构造PDA54

4. 3 LL(k)规范文法55

4. 3. 1 FIRST集与FOLLOW集56

4. 3. 2 选择集合58

4. 4 文法的左递归性59

4. 5 公共左因子60

4. 6 用正规表达式运算符拓广CFG61

4. 7 递归下降分析程序62

4. 8 作为下推自动机的递归下降分析程序64

4.9 自底向上的语法分析器的构造66

4. 9. 1 自底向上的语法分析66

4. 9. 2 LR (k）分析法69

4. 10 错误的发现84

4.11 使用语法分析器生成工具85

关键字86

习题86

第5章 语义分析与属性文法88

5.1 引言88

5.2 属性文法AG88

5.2.1 继承属性和综合属性90

5.2.2 属性值流93

5.3 非终结符号作为属性计值函数94

5.4 符号表作为属性95

5.5 一个微Pascal语言的属性文法AG96

5.6 域和标识符种类98

5.6.1 标识符作用域文法99

5.6.2 标识符作用域例子的分析100

5.6.3 符号表的其他事项104

5.7 在递归下降分析中实现属性105

5.8 LR分析器的属性赋值106

5.9 实现一个符号表107

符号109

关键字109

习题109

第6章 语法制导的代码生成111

6.1 引言111

6.2 常见的中间语言简介111

6.2.1 逆波兰表示112

6.2.2 四元式113

6.2.3 其他表示法114

6.3 赋值语句的翻译114

6.4 布尔表达式的翻译116

6.5 程序流程控制语句的翻译122

6.5.1 常见控制结构的翻译122

6.5.2 语句标号及GOTO语句的翻译126

6.5.3 多分支语句的翻译130

6.6 含数组元素的算术表达式及赋值语句的翻译132

6.6.1 下标变量地址的计算133

6.6.2 含有下标变量的赋值语句的翻译136

6.7 过程说明和过程调用的翻译139

6.7.1 过程说明的翻译139

6.7.2 实参和形参间的信息传递140

6.7.3 过程语句的翻译141

6.7.4 关于形实结合的进一步讨论142

6.8 说明语句的翻译144

6.8.1 类型说明（变量及数组定义）语句的翻译144

6.8.2 数据类型定义语句的翻译147

习题150

第7章 符号表152

7.1 引言152

7.2 符号表的组织152

7.3 符号表结构153

7.3.1 线性符号表153

7.3.2 有序符号表154

7.3.3 散列表155

7.4 符号表的管理157

7.4.1 符号表的初始化157

7.4.2 符号表的查填157

7.4.3 符号表的删除158

关键字158

习题158

第8章 运行时存储空间的组织与管理161

8.1 引言161

8.2 语言相关概述161

8.2.1 过程161

8.2.2 名字的作用域和绑定162

8.3 存储分配的策略163

8.3.1 静态存储分配策略164

8.3.2 栈式存储分配策略166

8.3.3 堆式存储分配策略170

8.4 FORTRAN语言的存储分配173

关键字174

习题174

第9章 代码优化180

9.1 概述180

9.2 局部优化181

9.2.1 基本块的划分181

9.2.2 基本块的优化182

9.2.3 基本块的DAG图表示183

9.3 循环优化189

9.3.1 程序流图的概念190

9.3.2 循环优化方法190

第10章 目标代码生成194

10.1 概述194

10.2 一个简单的计算机模型196

10.3 一个简单的代码生成器197

10.3.1 变量的待用信息及其算法198

10.3.2 代码生成算法200

10.4 寄存器分配204

10.5 窥孔优化205

参考文献208