编译器设计

第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