本书是作者多年来在编译器领域中钻研、教学的成果，并以在该学科领域与学生的交流以及他们的反馈和研究作为

依据。本书全面介绍了编译器设计中的原理和技术，阐述了编译领域中的难点，并详细描述了编译器设计的各个阶段。

　　因为编译器的设计过程是将自动机理论、数据结构、算法、计算机体系结构和操作系统等领域知识进行综合的过

程，所以编译器设计者必须要有较好的计算机科学理论的背景。本书详细描述了各种类型的解析器，从最简单的递归

下降和LL解析器到复杂的LR、规范LR和LALR解析器，尤其强调了LR解析器。

　　本书主要用于计算机科学专业的本科生和研究生一个学期的教材，该书也可供专业人员作为参考书。

　　本书源于笔者多年来对编译器的学习和教学经验，并以在该学科领域与学生的交流以及他们的反馈和研究作为依据。编译器的设计过程是将自动机理论、数据结构、算法、计算机体系机构和操作系统等领域知识进行综合的过程。编译器设计者必须要有较好的计算机科学理论的背景。同时，还应能掌握各种可用的软硬件平台。因此，任何编译器的书籍都应强调这些领域的作用，并向读者介绍编译领域中的难点和技术。同时，书籍应足够精炼，以便能在一个学期内完成课程。另外，还需要介绍编译器设计中各种可用的工具。本书涵盖了编译器中所有应掌握的主题，一共分为9章。

　　第1章介绍了编译器及其应用，并着重介绍了大量的应用领域，以使读者能理解该领域的范围。然后介绍了编译器的各个阶段，列举了各个阶段的任务。依据机器中软/硬件的功能和用户的需求，详细介绍了编译器设计的难点。本章以一个示例结束。

　　第2章展示了编译器中词法分析阶段的理论和设计。在介绍完正式的表示法如正则表达式、非确定和确定的有限自动机后，本书详细描述了使用正则表达式开始表示语言中单词规范的方式，并依据正则表达式构造识别器来标识输入流中语言的合法单词。最后，介绍了轻松生成词法分析器的自动化工具—— Lex。

　　第3章介绍了语法分析。首先明确了在指定的语言中文法的作用、文法的符号约定以及相关定义。本章详细描述了各种不同类型的解析器，首先介绍了最简单的自上而下分析，如递归下降和LL。然后介绍了先进的自下而上分析，如LR、规范LR和LALR。因为大多数编译器使用LR解析器，所以主要强调了LR分析，并介绍了工具yacc，用于自动生成LALR解析器。本章最后介绍了使用解析器来执行输入流的各种语法制导翻译的方式。

　　第4章介绍了类型检查，并介绍了类型检查的相关问题，以及使用这些理论检查类型等价的方式。最后介绍了类型转换，用于展示编译器自动推断必要的类型转换的方式。

　　第5章介绍了编译器中符号表的用法。根据语言的作用域规则，介绍了各种不同的数据结构来存储标识符，因此，编译器能有效地使用这些信息。

　　第6章介绍了编译器在程序执行时维持运行环境的职责，然后介绍了活动记录，并展示了使用不同而有效的数据结构维护活动记录的方式。

　　第7章详细介绍了中间代码的生成。这是编译器中的可选阶段，有助于将代码重定向到不同的体系结构中。首先介绍中间代码不同的表现方式，然后使用语法制导模式将常用的编程语言结构翻译成中间代码的形式。

　　第8章列举了目标代码的生成技术。在讨论完影响代码生成的因素后，介绍了使用基本的代码块表示中间语言程序的方式，然后从基本的代码块生成目标代码。同时也讨论了寄存器分配、缓存管理的问题及相应的解决策略。

　　第9章是代码优化阶段。在讨论完优化阶段必要且相关的问题后，介绍了优化的分类。然后介绍了不同的优化变换，如编译时计算、公共子表达式消除等。接下来介绍了全局优化和数据流问题。最后根据建立和求解数据流等式的技术解决一些数据流问题。

　　本书提供了编译器设计领域中的所有要点，适合作为本科生一个学期的学习内容。如果能有效地使用本书，将会得到很大的收获。同时欢迎读者给出任何对内容有改进的建设性意见。

　　

　　

　　

　　

　　 Santanu Chattopadhyay

　　

　　

　　

　　

　　

　　

　　

第1章  引言 1

1.1  编译器的定义 1

1.2  编译器应用 2

1.3  编译器的各个阶段 3

1.4  编译器设计的难点 7

1.5  编译过程—— 示例 9

1.6  小结 11

练习 11

第2章  词法分析 13

2.1  词法分析器的任务 13

2.2  记号的规范 14

2.3  记号识别 15

     2.3.1  不确定的有限自动机 17

     2.3.2  确定的有限自动机 17

     2.3.3  NFA到DFA的转换 20

2.4  NFA的正则表达式 22

2.5  词法分析的工具—— Lex 25

2.6  小结 33

练习 33

第3章  语法分析 35

3.1  解析器的功能 35

3.2  错误处理 36

3.3  文法 37

     3.3.1  符号约定 38

     3.3.2  推导 39

     3.3.3  二义性 40

     3.3.4  左递归 42

3.4  自上而下的分析 43

     3.4.1  递归下降分析 43

     3.4.2  递归的预测分析 46

3.4.3  非递归的预测分析

—— LL(k)分析 49

3.5  自下而上的分析 53

     3.5.1  算符优先的分析 56

     3.5.2  建立优先关系 57

     3.5.3  错误恢复 60

3.6  LR分析 60

     3.6.1  LR分析方法 60

     3.6.2  LR分析算法 61

     3.6.3  构造LR分析表 62

     3.6.4  处理LR分析的二义性 74

     3.6.5  LR分析中的错误恢复 77

3.7  LALR解析器的生成器

     —— yacc 78

3.8  语法制导翻译 81

3.9  小结 82

练习 82

第4章  类型检查 85

4.1  静态和动态检查的比较 85

4.2  类型表达式 86

4.3  类型检查 87

4.4  类型等价 88

4.5  类型转换 91

4.6  小结 91

练习 91

第5章  符号表 93

5.1  符号表中的信息 93

5.2  符号表的功能 94

5.3  简单的符号表 95

     5.3.1  线性表 95

     5.3.2  有序列表 96

     5.3.3  树 97

     5.3.4  哈希表 97

5.4  作用域的符号表 98

     5.4.1  嵌套的词法作用域 99

     5.4.2  每个作用域对应一张表 100

5.4.3  所有作用域都在

一张表中 101

5.5  小结 102

练习 103

第6章  运行时环境管理 105

6.1  引言 105

6.2  活动记录 106

     6.2.1  不含局部过程的环境 107

     6.2.2  含有局部过程的环境 109

6.3  display 112

6.4  小结 113

练习 113

第7章  中间代码生成 115

7.1  中间语言 115

7.2  中间语言设计问题 116

7.3  中间表示技术 116

     7.3.1  高级表示 116

     7.3.2  低级表示 118

7.4  三地址代码中的语句 118

7.5  三地址指令的实现 120

7.6  三地址代码生成 121

     7.6.1  数组的代码生成 123

     7.6.2  布尔表达式的翻译 126

     7.6.3  控制流(程)语句的翻译 132

     7.6.4  case语句的翻译 136

     7.6.5  函数调用 137

7.7  小结 139

练习 139

第8章  目标代码生成 141

8.1  影响代码生成的因素 141

8.2  基本块 142

8.3  树的代码生成 145

8.4  寄存器分配 148

8.5  缓存管理 154

8.6  使用动态规划的代码生成 154

8.7  小结 157

练习 157

第9章  代码优化 159

9.1  优化的需求 159

9.2  优化编译器设计问题 160

9.3  优化的分类 161

9.4  影响优化的因素 162

9.5  优化技术背后的主题 163

9.6  优化变换 164

     9.6.1  编译时计算 164

     9.6.2  公共子表达式消除 166

     9.6.3  变量传播 167

     9.6.4  代码迁移优化 167

     9.6.5  强度折减 170

     9.6.6  无效代码消除 171

     9.6.7  循环优化 172

9.7  局部优化 175

9.8  全局优化 177

     9.8.1  控制流分析 177

     9.8.2  数据流分析 178

     9.8.3  获取数据流信息 182

9.9  计算全局数据流信息 183

     9.9.1  汇合路径 183

     9.9.2  数据流等式 185

9.10  建立数据流等式 187

     9.10.1  数据流分析 188

     9.10.2  数据流等式的保守解 189

9.11  迭代数据流分析 190

     9.11.1  可用表达式 191

     9.11.2  有效范围识别 192

9.11.3  降低迭代数据流

   分析的复杂性 192

9.12  小结 194

练习 194