第1章 编译引论 1
1.1程序设计语言与编译程序 1
1.1.1编译程序鸟瞰 1
1.1.2源程序的执行 2
1.2编译程序的表示与分类 2
1.2.1 T型图 2
1.2.2编译程序的分类 3
1.3编译程序的结构与编译过程 4
1.3.1编译程序的结构与编译过程 4
1.3.2编译程序结构的公共功能与编译程序的组织 9
1.4语言开发环境中的伙伴程序 10
1.5编译程序结构的实例模型 11
1.5.1一遍编译程序结构 11
1.5.2 PRIME机上AHPL语言的两遍编译程序 11
1.5.3 PDP-11计算机上C语言的三遍编译程序 11
1.5.4 Tiger编译程序结构 12
1.5.5 GCC编译程序结构框架 13
1.6编译程序的构造与实现 14
1.6.1如何构造一个编译程序 14
1.6.2编译程序的生成方式 15
1.6.3编译程序的构造工具 15
习题1 16
第2章 形式语言与自动机理论基础 18
2.1文法和语言 18
2.1.1语言的语法和语义 18
2.1.2文法和语言的定义 19
2.1.3文法的表示方法 25
2.1.4语法分析树与二义性 26
2.1.5文法和语言的类型 29
2.2有限自动机 30
2.2.1确定的有限自动机 31
2.2.2非确定的有限自动机 33
2.2.3确定的有限自动机与非确定的有限自动机的等价 35
2.2.4确定的有限自动机的化简 38
2.3正规式与有限自动机 42
2.3.1有限自动机与正则文法 42
2.3.2正规式与正规集 43
2.3.3正规式与有限自动机 44
习题2 52
第3章 词法分析 58
3.1词法分析与词法分析程序 58
3.2词法分析程序设计与实现 59
3.2.1词法分析程序的输入与输出 59
3.2.2源程序的输入与预处理 60
3.2.3单词的识别 61
3.2.4词法分析程序与语法分析程序的接口 62
3.2.5词法分析器的设计与实现 62
3.3词法分析程序的自动生成 68
3.3.1词法分析自动实现思想与自动生成器——Lex/Flex 68
3.3.2 Lex运行与应用过程 68
3.3.3 Lex语言 69
3.3.4词法分析器产生器的实现 73
3.3.5 Lex应用 74
习题3 78
第4章 语法分析——自上而下分析 79
4.1语法分析综述 79
4.1.1语法分析程序的功能 79
4.1.2语法分析方法 80
4.2不确定的自上而下语法分析 81
4.2.1一般自上而下分析 81
4.2.2不确定性的原因与解决方法 82
4.2.3消除回溯 85
4.3递归下降分析法与递归下降分析器 86
4.3.1递归下降分析器的实现 86
4.3.2递归下降分析器设计工具——状态转换图 87
4.4 LL（1）分析法与LL（1）分析器 89
4.4.1 LL （1）分析器的逻辑结构与动态实现 89
4.4.2 LL（1）分析表的构造 91
4.4.3关于LL（1）文法 94
习题4 95
第5章 语法分析——自下而上分析 99
5.1基于“移进-归约”的自下而上分析 99
5.1.1“移进-归约”分析 99
5.1.2规范归约与句柄 101
5.2算符优先分析法与算符优先分析器 103
5.2.1直观的算符优先分析法 103
5.2.2算符优先文法和算符优先分析表的构造 106
5.2.3算符优先分析法实现的理论探讨 109
5.2.4优先函数表的构造 112
5.3 LR分析 114
5.3.1 LR分析法与LR文法 114
5.3.2 LR（0）分析及LR（0）分析表的构造 119
5.3.3 SLR（1）分析及SLR（1）分析表的构造 128
5.3.4 LR（1）分析及LR（1）分析表的构造 130
5.3.5 LALR（1）分析及LALR（1）分析表的构造 135
5.4 LR分析对二义文法的应用 138
5.5 LR分析的错误处理与恢复 140
5.6语法分析程序自动生成器 142
5.6.1 YACC综述与应用 143
5.6.2 YACC语言 144
5.6.3 YACC处理二义文法 145
5.6.4 YACC的错误恢复 147
5.6.5 YACC应用 148
习题5 158
第6章 语义分析与中间代码生成 163
6.1语法制导翻译 163
6.1.1语法制导定义 164
6.1.2综合属性 165
6.1.3继承属性 166
6.1.4依赖图 166
6.1.5语法树的构造 168
6.1.6 S_属性定义与自下而上计算 168
6.1.7 L_属性定义与翻译模式 169
6.2符号表 172
6.2.1符号表的组织 173
6.2.2分程序结构的符号表 174
6.3类型检查 177
6.3.1类型体制 177
6.3.2一个简单的类型检查程序 179
6.4中间语言 183
6.4.1逆波兰表示法 183
6.4.2 N-元式表示法 184
6.4.3图表示法 186
6.5中间代码生成 186
6.5.1说明类语句的翻译 186
6.5.2赋值语句与表达式的翻译 189
6.5.3控制流语句的翻译 190
6.5.4数组说明和数组元素引用的翻译 196
6.5.5过程、函数说明和调用的翻译 198
习题6 199
第7章 运行环境 203
7.1程序运行时的存储组织与分配 203
7.1.1关于存储组织 203
7.1.2过程的活动记录 204
7.1.3存储分配策略 205
7.2静态运行时环境与存储分配 206
7.3基于栈的运行时环境的动态存储分配 208
7.3.1简单的栈式存储分配的实现 208
7.3.2嵌套过程语言的栈式存储分配的实现 210
7.4基于堆的运行时环境的动态存储分配 212
7.4.1基于堆的运行时环境的动态存储分配的实现 212
7.4.2关于悬空引用 214
习题7 216
第8章 代码优化 221
8.1代码优化概述 221
8.1.1代码优化的概念 221
8.1.2优化技术分类 222
8.1.3优化编译程序的组织 227
8.2局部优化 227
8.2.1基本块的定义与划分 227
8.2.2程序的控制流图 228
8.2.3基本块的DAG表示及应用 229
8.3控制流分析与循环查找 236
8.4数据流分析 239
8.4.1程序中的点与通路 239
8.4.2到达-定值数据流方程及其方程求解 239
8.4.3引用-定值链（ud链） 242
8.4.4活跃变量与数据流方程 242
8.4.5定值-引用链（du链）与du链数据流方程 243
8.4.6可用表达式数据流方程 244
8.5循环优化 244
8.5.1代码外提 245
8.5.2强度削弱 247
8.5.3变换循环控制变量（删除归纳变量） 247
习题8 249
第9章 代码生成 253
9.1代码生成器设计中的要点 253
9.1.1代码生成器的输入与输出 253
9.1.2指令的选择 254
9.1.3寄存器分配 255
9.1.4存储管理 256
9.2简单代码生成器的构造 256
9.3目标代码的窥孔优化 258
9.3.1冗余指令序列 259
9.3.2控制流优化 260
9.3.3代数化简 261
9.3.4窥孔优化实例 261
习题9 264
第10章 编译程序实现范例 265
10.1 PL/0语言描述 265
10.2 PL/0编译程序的结构 266
10.3 PL/0编译程序的词法分析 268
10.4 PL/0编译程序的语法分析 270
10.5 PL/0编译程序的目标代码结构和代码生成 274
10.6 PL/0编译程序的语法错误处理 276
10.7 PL/0编译程序的目标代码解释执行时的存储分配 279
10.8 PL/0编译程序文本 281
习题10 301
第11章 编译技术高级专题 303
11.1面向对象语言的翻译 303
11.1.1面向对象程序设计语言的概念 303
11.1.2面向对象语言的翻译 305
11.1.3面向对象语言中的动态存储 308
11.2高性能计算机体系结构及发展趋势 309
11.2.1支持指令级并行的处理器简介 310
11.2.2支持线程级并行的处理器简介 313
11.2.3高性能体系结构对编译器的挑战 316
11.3关于并行优化技术 316
11.3.1指令相关与指令并行化 316
11.3.2循环展开与优化 319
11.3.3 VLIW指令调度 322
11.4存储层次及其优化技术 323
11.4.1存储层次与Cache组织结构 323
11.4.2 Cache预取 324
11.4.3循环交换 325
11.4.4循环分块 327
11.5 关于GLR分析法 329
习题11 335
参考文献 337