章 绪论1

1.1 编译程序简介1

1.1.1 编译概述1

1.1.2 编译技术的重要性3

1.1.3 编译技术的应用3

1.2 编译程序的结构及编译过程4

1.2.1 词法分析器5

1.2.2 语法分析器6

1.2.3 语义分析与中间代码生成器7

1.2.4 代码优化器8

1.2.5 目标代码生成器9

1.2.6 表格管理10

1.2.7 错误处理10

1.2.8 常见术语10

1.3 编译程序的构造11

1.4 本章小结12

1.5 习题12

第2章 不错语言及其语法描述13


2.1 不错语言简介13

2.1.1 不错语言的定义13

2.1.2 不错语言的一般特性13

2.1.3 L语言说明17

2.2 不错语言的语法描述19

2.2.1 符号和符号串19

2.2.2 上下文无关文法20

2.2.3 语法分析树24

2.2.4 文法的二义性24

2.2.5 文法的分类25

2.3 本章小结26

2.4 习题26

第3章 词法分析28


3.1 词法分析器概述28

3.1.1 词法分析器的功能28

3.1.2 单词的类型和内部表示29

3.2 词法分析器的设计30

3.2.1 总体设计30

3.2.2 详细设计31

3.2.3 状态转换图33

3.2.4 L语言词法分析器的设计与实现34

3.3 正规表达式与有限自动机37

3.3.1 正规式与正规集37

3.3.2 确定有限自动机（DFA）38

3.3.3 不确定有限自动机（NFA）39

3.3.4 正规文法与有限自动机的等价性42

3.3.5 正规式与有限自动机的等价性43

3.3.6 DFA的化简46

3.3.7 化简的DFA到程序的表示48

3.4 词法分析器的自动生成50

3.4.1 LEX概述50

3.4.2 LEX语言规范50

3.4.3 使用LEX自动生成L语言的词法分析器53

3.5 本章小结54

3.6 习题54


第4章 自上而下语法分析55


4.1 概述55

4.2 自上而下分析基本思想55

4.3 LL(1) 分析57

4.3.1 消除左递归57

4.3.2 FIRST集、提取左因子60

4.3.3 FOLLOW集63

4.3.4 LL(1) 文法64

4.4 递归下降分析法64

4.4.1 基本思路64

4.4.2 流程设计65

4.4.3 程序实现67

4.4.4 L语言设计与实现68

4.5 预测分析法70

4.5.1 预测分析过程70

4.5.2 预测分析表的构造72

4.6 LL(1) 分析中的错误处理74

4.7 本章小结76

4.8 习题76

第5章 自下而上语法分析78


5.1 移进-归约方法78

5.2 规范归约79

5.2.1 规范归约和句柄79

5.2.2 短语79

5.2.3 LR分析80

5.3 算符优先分析83

5.3.1 算符优先文法83

5.3.2 算符优先关系表84

5.3.3 算符优先分析算法86

5.3.4 优先函数88

5.3.5 算符优先分析中的出错处理91

5.4 LR分析92

5.4.1 规范句型的活前缀92

5.4.2 LR(0)分析93

5.4.3 SLR(1) 分析97

5.4.4 LR(1) 分析100

5.4.5 LALR(1)分析103

5.4.6 二义文法的应用105

5.4.7 LR分析中的出错处理106

5.5 语法分析器的自动产生工具YACC108

5.6 本章小结111

5.7 习题111

第6章 语义分析与中间代码生成114


6.1 属性文法114

6.1.1 综合属性116

6.1.2 继承属性116

6.2 语法制导翻译方法117

6.2.1 依赖图118

6.2.2 树遍历的属性计算方法119

6.2.3 一遍扫描的处理方法120

6.2.4 两类特殊的属性文法121

6.3 中间代码的形式123

6.3.1 后缀式123

6.3.2 图表示法124

6.3.3 三地址代码125

6.4 说明语句的翻译127

6.4.1 变量说明语句的翻译128

6.4.2 L语言变量说明语句的翻译130

6.5 赋值语句的翻译132

6.5.1 简单算术表达式及赋值语句的翻译132

6.5.2 数组元素的引用133

6.5.3 L语言赋值语句的翻译136

6.6 布尔表达式的翻译140

6.6.1 数值计算法140

6.6.2 优化计算法141

6.6.3 L语言布尔表达式的翻译144

6.7 控制语句的翻译148

6.7.1 典型控制语句的翻译148

6.7.2 L语言控制语句的翻译150

6.8 本章小结155

6.9 习题155

第7章 符号表与运行时存储空间组织157


7.1 符号表的内容与组织157

7.1.1 符号表的作用157

7.1.2 符号表的内容158

7.1.3 符号表的组织方式158

7.2 符号表的整理与查找160

7.2.1 线性表160

7.2.2 对折查找与二叉树161

7.2.3 杂凑法161

7.3 目标程序运行时的活动163

7.3.1 过程的活动163

7.3.2 参数传递163

7.4 运行时存储器的组织165

7.4.1 运行时存储器的划分165

7.4.2 活动记录166

7.4.3 存储分配策略167

7.5 静态存储分配167

7.5.1 静态存储分配的性质167

7.5.2 静态存储分配的实现168

7.5.3 临时变量的地址分配169

7.6 栈式存储分配169

7.6.1 简单的栈式存储分配169

7.6.2 嵌套过程语言的栈式存储分配171

7.7 堆式存储分配174

7.7.1 堆式存储分配的实现175

7.7.2 隐式存储回收175

7.8 本章小结176

7.9 习题176

第8章 优化178


8.1 概述178

8.1.1 优化的原则178

8.1.2 优化的种类178

8.1.3 基本块与流图179

8.2 局部优化181

8.2.1 删除公共子表达式181

8.2.2 复写传播185

8.2.3 删除无用代码186

8.2.4 对程序进行代数恒等变换188

8.2.5 利用基本块的DAG进行优化190

8.3 循环优化192

8.3.1 找出循环193

8.3.2 代码外提194

8.3.3 强度削弱196

8.3.4 删除归纳变量196

8.3.5 循环展开197

8.4 本章小结197

8.5 习题197

第9章 目标代码生成200


9.1 概述200

9.2 目标机器模型202

9.3 一个简单的代码生成器203

9.3.1 待用信息与活跃信息204

9.3.2 寄存器描述和地址描述205

9.3.3 简单代码生成算法206

9.4 寄存器分配208

9.4.1 全局寄存器分配209

9.4.2 图着色方法分配寄存器211

9.5 DAG的目标代码213

9.6 窥孔优化215

9.7 本章小结216

9.8 习题217

参考文献219

编译的精髓在于做到原理、技术与实践方法的融会贯通，本书正是这样一部综合、全面、实用的编译技术教材。本着知识与能力相结合、理论与实用并重的指导思想，以贯穿全书的样本语言编译器的开发为例，在简要介绍编译技术所涉及的基本知识和不错语言的语法描述方法之后，按照编译程序的工作过程逐步介绍编译各个阶段的主要内容，具体包括：词法分析、语法分析、语义分析与中间代码生成、符号表与运行时存储空间组织、代码优化以及目标代码生成等。通过本书的学习能够使读者系统而全面地掌握编译各个阶段的基本原理、技术和实践方法，并且运用所学技术进行编译程序的设计与开发。本书可用作高等学校计算机及其相关学科各专业本科生的教材或教学参考书，也可供其他技术开发人员参考。