编译原理

编译系统是计算机系统中的系统软件，是软件开发环境的核心组成部分。本书介绍编译系统的结构、工作流程及编译程序各组成部分的设计原理和实现技术。作者遵循CDIO工程教育理念将全书内容分为四篇，第1篇构思（Conceive），包括编译程序概论、文法和语言；第2篇设计（Design），包括词法分析、自顶向下语法分析、自底向上语法分析、语义分析与符号表；第3篇实现（Implement），包括语法制导翻译与中间代码生成、目标程序运行时的存储组织、出错处理、代码优化、目标代码生成；第4篇运作（Operate），包括寄存器分配、垃圾回收、面向对象语言编译器和人工智能编译器。

目录
第1篇 构思(Conceive)
第1章 编译程序概论 3
1.1 编译程序的概念 3
1.1.1 程序设计语言 3
1.1.2 基本概念和术语 4
1.1.3 程序设计语言的翻译 4
1.1.4 高级语言程序的执行 5
1.2 编译过程 6
1.3 编译程序的结构 8
1.3.1 词法分析程序 10
1.3.2 语法分析程序 11
1.3.3 语义分析程序 12
1.3.4 中间代码生成程序 12
1.3.5 代码优化程序 13
1.3.6 目标代码生成程序 14
1.3.7 信息表管理程序 15
1.3.8 错误检查和处理程序 16
1.3.9 编译程序的分遍 17
1.4 解释程序 18
1.5 编译程序的评价指标与构造技术 19
1.5.1 编译程序的评价指标 20
1.5.2 编译程序的构造技术 21
1.6 程序设计语言范型 24
习题 26
第2章 文法和语言 27
2.1 符号和符号串 27
2.2 文法和语言的定义 29
2.3 文法的类型 35
2.4 上下文无关文法及其语法树 37
2.4.1 程序设计语言的语法结构的描述 37
2.4.2 语法树 38
2.4.3 文法的二义性 39
2.5 句型的分析 41
2.5.1 规范推导和规范归约 41
2.5.2 短语和句柄 43
2.6 文法描述语言时的限制与扩充 46
2.6.1 文法描述语言时的限制 46
2.6.2 文法描述语言时的扩充 47
习题 48
第2篇 设计(Design)
第3章 词法分析 53
3.1 词法分析概述 53
3.2 词法分析器的结构 53
3.2.1 词法分析器的工作方式 53
3.2.2 词法分析器的输出 54
3.2.3 词法分析作为一个独立阶段的原因 55
3.3 单词的描述工具 55
3.3.1 正规文法 56
3.3.2 正规式 56
3.3.3 正规文法和正规式的等价性 58
3.4 有限自动机 60
3.4.1 确定的有限自动机(DFA) 60
3.4.2 不确定的有限自动机(NFA) 62
3.4.3 NFA转换为等价的DFA 63
3.4.4 确定有限自动机的化简 66
3.5 正规式和有限自动机的等价性 68
3.6 正规文法和有限自动机的等价性 71
3.7 词法分析器的自动构造工具 73
习题 75
实践项目一 76
第4章 自顶向下语法分析 77
4.1 自顶向下语法分析概述 77
4.2 递归下降分析法 78
4.3 LL(1)预测分析法 80
4.4 非LL(1)文法到LL(1)文法的等价变换 83
4.4.1 提取左公共因子 83
4.4.2 消除左递归 84
4.4.3 消除文法左递归的方法 86
4.5 LL的自动生成工具 88
4.5.1 递归子程序法 88
4.5.2 预测分析方法 90
案例分析 91
习题 93
实践项目二 95
第5章 自底向上语法分析 96
5.1 自底向上语法分析概述 96
5.2 算符优先分析 97
5.2.1 算符优先文法的定义 97
5.2.2 算符优先关系表的构造 99
5.2.3 最左素短语 101
5.2.4 优先函数 103
5.3 LR分析 104
5.3.1 LR分析器概述 105
5.3.2 LR(0)分析 106
5.3.3 SLR(1)分析 113
5.3.4 LR(1)分析 114
5.3.5 LALR(1)分析 114
5.4 LR的自动生成工具 115
案例分析 115
习题 120
实践项目三 121
第6章 语义分析与符号表 122
6.1 语义分析概述 122
6.2 符号表的作用 122
6.3 符号表的内容 123
6.4 符号表的组织 128
6.5 符号表的管理 135
习题 137
第3篇 实现(Implement)
第7章 语法制导翻译与中间代码生成 141
7.1 语法制导翻译 141
7.1.1 属性文法 141
7.1.2 语法翻译概述 141
7.2 中间代码表示 143
7.2.1 逆波兰式 143
7.2.2 三地址代码 144
7.2.3 四元式表示 145
7.2.4 其他表示 146
7.3 简单赋值语句的翻译 146
7.4 布尔表达式的翻译 147
7.5 控制语句的翻译 149
习题 151
实践项目四 153
第8章 目标程序运行时的存储组织 154
8.1 存储组织及管理 154
8.2 静态存储分配策略 155
8.3 动态存储分配 157
8.3.1 过程与活动记录 157
8.3.2 简单的栈式存储分配的实现 159
8.3.3 嵌套过程语言的栈式实现 159
习题 161
第9章 出错处理 163
9.1 错误分类 163
9.1.1 语法错误 163
9.1.2 语义错误 163
9.2 编译程序中参数错误的处理 164
9.2.1 校正法 164
9.2.2 局部化法 165
9.2.3 参数FSYS集合内容的补充 168
9.3 一些语义错误的处理 169
9.3.1 遏止株连错误 169
9.3.2 遏止重复错误 169
习题 170
实践项目五 171
第10章 代码优化 172
10.1 优化技术简介 172
10.1.1 删除多余运算 172
10.1.2 复写传播 173
10.1.3 无用代码删除 173
10.1.4 代码外提 173
10.1.5 强度削弱和基本归纳变量删除 174
10.2 局部优化 175
10.2.1 基本块 175
10.2.2 基本块的有向无环图表示 176
10.2.3 基于基本块的优化 179
10.3 循环优化 180
10.3.1 流图 180
10.3.2 循环 180
10.3.3 循环不变计算及代码外提 183
10.3.4 归纳变量相关的优化 186
10.4 全局优化 188
10.4.1 全局公共子表达式 188
10.4.2 复写传播 188
习题 190
实践项目六 192
第11章 目标代码生成 193
11.1 目标代码生成概述 193
11.1.1 代码生成器的输入 193
11.1.2 目标代码的形式 193
11.1.3 指令选择 194
11.1.4 寄存器分配 194
11.1.5 计算顺序的选择 195
11.2 常用的代码生成器的开发方法 195
11.2.1 解释性代码生成法 195
11.2.2 模式匹配代码生成法 196
11.2.3 表驱动代码生成法 196
习题 197
第4篇 运作(Operate)
第12章 寄存器分配 201
12.1 寄存器分配概述 201
12.2 寄存器分配图染色法 202
12.3 合并 204
12.4 预着色的结点 206
12.5 图着色的实现 207
12.6 针对树的寄存器分配 208
习题 212
第13章 垃圾回收 213
13.1 垃圾收集概述 213
13.2 引用计数 214
13.3 复制式收集 215
13.4 分代收集 217
13.5 增量式收集 218
13.6 编译器接口 219
习题 221
第14章 面向对象语言编译器 222
14.1 面向对象语言概述 222
14.2 类与继承 223
14.3 私有域和私有方法 224
14.4 面向对象语言的翻译 225
14.4.1 单继承的编译方案 225
14.4.2 多继承的编译方案 227
14.5 面向对象语言的编译优化 228
习题 230
第15章 人工智能编译器 231
15.1 人工智能编程语言概述 231
15.1.1 Python 231
15.1.2 R 232
15.1.3 LISP 233
15.1.4 Prolog 233
15.2 Python虚拟机基本原理 233
15.2.1 过程概述 233
15.2.2 关于.pyc文件 234
15.2.3 关于PyCodeObject 234
15.2.4 执行字节码 235
15.2.5 Python字节码 236
15.3 代码自动生成与抽象语法树 237
习题 239
参考文献 240