第1章 引言 1
1.1从面向机器的语言到面向人类的语言 1
1.2语言之间的翻译 2
1.3编译器与解释器 3
1.4编译器的工作原理与基本组成 4
1.4.1通用程序设计语言的主要成分 4
1.4.2以阶段划分编译器 5
1.4.3编译器各阶段的工作 6
1.4.4编译器的分析／综合模式 10
1.4.5编译器扫描的遍数 11
1.5编译器的编写 11
1.6本章小结 12
习题 13
第2章 词法分析 14
2.1词法分析中的若干问题 14
2.1.1记号、模式与单词 14
2.1.2记号的属性 15
2.1.3词法分析器的作用与工作方式 16
2.1.4输入缓冲区 17
2.2模式的形式化描述 18
2.2.1字符串与语言 18
2.2.2正规式与正规集 20
2.2.3记号的说明 21
2.3记号的识别——有限自动机 22
2.3.1不确定的有限自动机（Nondeterministic Finite Automata，NFA） 22
2.3.2确定的有限自动机（Deterministic Finite Automata， DFA） 25
2.3.3有限自动机的等价 26
2.4从正规式到词法分析器 27
2.4.1从正规式到NFA 27
2.4.2从NFA到DFA 29
2.4.3最小化DFA 33
2.4.4 DFA的“短路”计算 35
2.4.5由DFA构造词法分析器 42
2.5本章小结 44
习题 45
第3章 语法分析 48
3.1语法分析的若干问题 48
3.1.1语法分析器的作用 48
3.1.2语法错误的处理原则 49
3.2上下文无关文法 50
3.2.1上下文无关文法的定义与表示 50
3.2.2 CFG产生语言的基本方法——推导 52
3.2.3推导、分析树与语法树 53
3.2.4二义性与二义性的消除 54
3.3语言与文法简介 59
3.3.1正规式与上下文无关文法 59
3.3.2上下文有关文法 60
3.3.3形式语言与自动机简介 62
3.4自上而下语法分析 63
3.4.1自上而下分析的一般方法 63
3.4.2消除左递归 64
3.4.3提取左因子 66
3.4.4递归下降分析 67
3.4.5预测分析器 71
3.5自下而上语法分析 77
3.5.1自下而上分析的基本方法 77
3.5.2 LR分析 80
3.6 LR（1）与LALR（1）分析 89
3.6.1 SLR分析器的弱点 89
3.6.2 LR（1）分析器 90
3.6.3 LALR（1）分析器 92
3.6.4 LR（1）与LALR（1）的关系 94
3.6.5 LR（1）与二义文法的关系 96
3.7编译器编写工具 97
3.7.1词法分析器生成器LEX 97
3.7.2语法分析器生成器YACC 109
3.7.3语言识别器生成工具简述 131
3.8本章小结 134
习题 136
第4章 静态语义分析 139
4.1语法制导翻译简介 139
4.1.1语法与语义 139
4.1.2属性与语义规则 140
4.1.3语义规则的两种形式 141
4.1.4 LR分析翻译方案的设计 142
4.1.5递归下降分析翻译方案的设计 144
4.2属性的计算 145
4.2.1综合属性与自下而上分析 145
4.2.2继承属性与自上而下分析 146
4.2.3依赖图与属性计算 148
4.2.4 L_属性的增量分析 151
4.2.5 L_属性的自下而上计算 154
4.2.6属性的空间分配 160
4.2.7 YACC源程序中的语法制导翻译 163
4.3中间代码简介 165
4.3.1后缀式 165
4.3.2三地址码 166
4.3.3图形表示 170
4.4符号表简介 171
4.4.1符号表条目 172
4.4.2构成名字的字符串 173
4.4.3名字的作用域 173
4.4.4线性表 175
4.4.5散列表 175
4.5声明语句的翻译 177
4.5.1变量的声明 177
4.5.2数组变量的声明 179
4.5.3过程的定义与声明 184
4.5.4记录的域名 194
4.6简单算术表达式与赋值句 195
4.6.1简单变量的语法制导翻译 195
4.6.2变量的类型转换 195
4.7数组元素的引用 198
4.7.1数组元素的地址计算 199
4.7.2数组元素引用的语法制导翻译 200
4.8布尔表达式 203
4.8.1布尔表达式的作用与结构 203
4.8.2布尔表达式的计算方法 203
4.8.3数值表示与直接计算的语法制导翻译 204
4.8.4短路计算的语法制导翻译 206
4.8.5拉链与回填 207
4.9控制语句 209
4.9.1标号与无条件转移 210
4.9.2条件转移 211
4.10过程调用 214
4.11类型检查 215
4.11.1类型、类型系统与类型检查 215
4.11.2类型系统 219
4.11.3简单的类型检查 222
4.11.4类型表达式的等价 226
4.11.5多态函数的类型检查 229
4.11.6特定多态的类型检查 235
4.12本章小结 238
习题 240
第5章 运行环境 243
5.1过程的动态特性 243
5.1.1过程与活动 243
5.1.2控制栈与活动记录 245
5.1.3名字的绑定 246
5.2运行时数据空间的组织 247
5.2.1运行时内存的划分与数据空间的存储分配策略 247
5.2.2静态与动态分配简介 248
5.3栈式动态分配 250
5.3.1控制栈中的活动记录 250
5.3.2调用序列与返回序列 251
5.3.3栈式分配中对非本地名字的访问 252
5.3.4参数传递的实现 255
5.4本章小结 257
习题 258
第6章 代码生成 260
6.1代码生成的相关问题 260
6.2简单的计算机模型 260
6.3简单的代码生成器 262
6.3.1基本块、流图与循环 263
6.3.2下次引用信息与活跃信息 266
6.3.3简单的代码生成 267
6.4本章小结 269
习题 269
第7章 代码优化 271
7.1局部优化 271
7.1.1基本块的优化 271
7.1.2窥孔优化 276
7.1.3表达式的优化代码生成 278
7.2独立于机器的优化 281
7.2.1运行实例：快排序 282
7.2.2全局公共子表达式 284
7.2.3复写传播（Copy Propagation） 286
7.2.4死代码消除（Dead-Code Elimination） 286
7.2.5代码外提（Code Motion） 287
7.2.6归纳变量与强度削弱 287
7.3数据流分析简介 289
7.3.1数据流抽象 290
7.3.2数据流分析模式 291
7.3.3基本块上的数据流模式 292
7.3.4到达定值（Reaching Definitions） 292
7.3.5活跃变量（Live Varibale） 296
7.3.6可用表达式（Availabal Expression） 297
7.3.7小结 300
7.4数据流分析的数学基础 300
7.4.1半格（Semilattices） 301
7.4.2转换函数（Transfer Functions） 303
7.4.3通用框架的迭代算法 305
7.4.4数据流解的意义 306
7.5本章小结 308
习题 309
参考文献 311