第一章 编译程序概述 1
1．1 编译程序和解释程序 1
1．2 编译程序的功能分解和组织结构 3
1．3 编译程序的复杂性 5
1．4 编译程序的设计实现 6
1．5 编译程序的测试与维护 7
1．6 几个经典编译程序 8
第二章 一个微小编译器 11
2．1 微小语言Micro 11
2．2 Micro的词法分析 12
2．3 Micro的语法分析 16
2．4 Micro的语义分析 19
2．5 Micro的目标代码 22
练习题 26
第三章 有限自动机与词法分析器 28
3．1 词法分析 28
3．1．1 词法分析器的功能 28
3．1．2 单词的内部表示 29
3．1．3 保留字 30
3．1．4 空格符、制表符和换行符 31
3．1．5 括号类配对预检 32
3．1．6 向前看多个字符的处理 32
3．1．7 字符串空间 34
3．1．8 词法错误校正 34
3．1．9 词法分析的结束 36
3．2 正则表达式 36
3．2．1 基本概念 36
3．2．2 正则表达式及其一些性质 37
3．2．3 正则定义 38
3．2．4 正则表达式的局限性 39
3．3 有限自动机（FA） 39
3．3．1 确定有限自动机（DFA） 39
3．3．2 确定有限自动机的实现 42
3．3．3 非确定有限自动机（NFA） 43
3．3．4 NFA到DFA的转换 44
3．3．5 确定有限自动机的化简 47
3．3．6 正则表达式到DFA的转换 50
3．4 词法分析器的构造 51
3．4．1 用DFA人工构造词法分析器 51
3．4．2 使用词法分析器的生成器ScanGen 54
3．4．3 Lex 56
练习题 58
第四章 文法与语法分析 60
4．1 语法分析的功能 60
4．1．1 语法分析器和识别器 60
4．1．2 语法分析器的输入 60
4．1．3 语法错误类别及关键性错误 61
4．1．4 语法错误处理 61
4．2 上下文无关文法 62
4．2．1 文法和语言 62
4．2．2 最左推导和最右推导 65
4．2．3 语法分析树与二义性 66
4．2．4 文法分析算法 68
4．2．5 自顶向下方法概述 72
4．2．6 自底向上方法概述 73
4．3 递归下降法——自顶向下分析 74
4．3．1 递归下降法原理 74
4．3．2 消除公共前缀 76
4．3．3 消除左递归 77
4．4 LL分析方法——自顶向下分析 80
4．4．1 LL（1）文法 80
4．4．2 LL（1）分析表 83
4．4．3 LL（1）分析的驱动器 84
4．4．4 LL（1）中的if-then-else问题 86
4．4．5 LL（1）分析器的自动生成器LLGen 88
4．5 LR方法——自底向上分析 89
4．5．1 句柄 89
4．5．2 活前缀和归约活前缀 90
4．5．3 线性正则式的状态机 91
4．5．4 LR状态机的构造 93
4．5．5 LR（0）和SLR（1）文法 97
4．5．6 LR（1）文法 103
4．5．7 LALR（1）文法 109
4．5．8 二义性文法的处理 116
4．5．9 另一种Shift-Reduce分析技术 118
4．5．10 LL（1）与LALR（1）的比较 119
4．6 LR分析器的生成器 121
4．6．1 LALR分析器的生成器Yacc 121
4．6．2 LALR分析器的生成器LALRGen 122
4．7 语法错误处理 122
4．7．1 错误恢复和错误修复 122
4．7．2 递归下降分析的错误恢复 123
4．7．3 LL分析的错误恢复 126
4．7．4 LR分析的错误恢复 128
练习题 129
第五章 语义分析 133
5．1 语义分析基础 133
5．1．1 语义分析内容 133
5．1．2 标识符的内部表示 134
5．1．3 类型的内部表示 138
5．1．4 值的内部表示 143
5．2 符号表 144
5．2．1 表处理技术 145
5．2．2 符号表的局部化 151
5．2．3 二叉式局部符号表 152
5．2．4 散列式全局符号表 154
5．2．5 嵌套式局部符号表 155
5．2．6 符号表界面 157
5．3 类型表达式 159
5．3．1 类型的等价性和相容性 159
5．3．2 类型的分析 160
5．3．3 枚举类型——EnumTYPE 162
5．3．4 子界类型——SubRangeTYPE 163
5．3．5 数组类型——ArrayTYPE 163
5．3．6 集合类型——SetTYPE 164
5．3．7 文件类型——FileTYPE 165
5．3．8 指针类型——PointerTYPE 165
5．3．9 记录类型——RecordTYPE 166
5．4 声明的语义分析 169
5．4．1 标号声明部分——LabelDecPart 170
5．4．2 常量声明部分——ConstDecPart 172
5．4．3 类型声明部分——TypeDecPart 173
5．4．4 变量声明部分——VarDecPart 174
5．4．5 子程序首部——RoutHead 176
5．4．6 过程/函数的向前声明 179
5．5 执行体Body的语义分析 180
5．5．1 表达式分析 181
5．5．2 定位性标号和使用性标号 183
5．5．3 赋值语句和调用语句分析 184
5．5．4 结构语句分析 188
练习题 190
第六章 运行时的存储空间 192
6．1 运行时的存储空间结构 192
6．2 运行时的存储空间分配 193
6．2．1 静态区的存储分配 193
6．2．2 栈区的存储分配 194
6．2．3 堆区的存储分配 197
6．2．4 堆区空间管理 199
6．3 运行时的过程活动记录与栈区的组织结构 201
6．3．1 过程活动记录（Activation Record） 201
6．3．2 动态链（Dynamic Chain） 204
6．3．3 活跃活动记录 206
6．4 运行时的变量访问 206
6．4．1 变量的访问环境 206
6．4．2 局部Display表方法 209
6．4．3静态链方法（Static Chain） 211
6．4．4 全局Display表方法和寄存器方法 213
6．5 非正常出口和形式过程语句 215
6．5．1 非正常出口的动态链和Display表 215
6．5．2 形式过程语句和Display表 216
6．5．3 奇特型调用和Display表 217
6．6 分程序记录和动态数组空间 218
6．6．1 分程序的记录 218
6．6．2 动态数组的分配 220
练习题 224
第七章 动作文法和属性文法 225
7．1 动作方法（Action Grammar） 225
7．1．1 动作符（Action Symbol） 225
7．1．2 动作文法（Action Grammar） 225
7．1．3 尾动作文法 227
7．1．4 抽象动作文法 228
7．2 动作文法的实现 230
7．2．1 动作文法的LL实现 230
7．2．2 动作文法的LR实现 236
7．2．3 Yacc——LALR分析器的生成器 241
7．3 属性文法 244
7．3．1 属性文法的定义 244
7．3．2 继承属性和综合属性 246
7．3．3 属性规则 246
7．3．4 属性树和属性依赖图 248
7．3．5 属性求值 248
7．3．6 拷贝型属性文法 250
7．4 属性文法在编译器设计中的应用 251
7．4．1 类型分析的属性文法描述 251
7．4．2 声明分析的属性文法描述 253
7．4．3 语句分析的属性文法描述 254
7．5 S——属性文法及其属性求值 256
7．5．1 S——属性文法 256
7．5．2 S——属性文法的递归实现——自顶向下求值 256
7．5．3 S——属性文法的LL实现——自顶向下求值 258
7．5．4 S——属性文法的LR实现——自底向上求值 259
7．6 L——属性文法及其属性求值 260
7．6．1 L——属性文法 260
7．6．2 LL——L属性文法的递归实现——自顶向下求值 261
7．6．3 LL——L属性文法的LL实现——自顶向下求值 262
7．6．4 L——属性文法的栈式遍历树实现 262
7．6．5 LR——L属性文法的LR实现——自底向下求值 263
7．6．6 LALR分析器的生成器LALRGen 267
练习题 271
第八章 中间代码生成 273
8．1 中间语言 273
8．1．1 中间语言设置和直接代码生成 273
8．1．2 栈式中间代码——后缀式 274
8．1．3 三地址中间代码 275
8．1．4 抽象语法树和DAG 276
8．1．5 多元式中间代码 277
8．2 简单表达式的中间代码生成 279
8．2．1 表达式的语义信息 279
8．2．2 表达式的中间代码结构 282
8．2．3 类型转换 284
8．2．4 表达式中间代码的生成 285
8．2．5 布尔表达式的短路中间代码 289
8．2．6 变量的中间代码 292
8．3 多维下标变量的中间代码生成 299
8．3．1 多维下标变量 299
8．3．2 多维下标变量的地址公式 299
8．3．3 多维下标变量的中间代码结构 301
8．4 原子语句的中间代码 303
8．4．1 输入输出语句的中间代码 303
8．4．2 赋值语句的中间代码 303
8．4．3 过程调用和函数调用的中间代码 304
8．4．4 GOTO语句和标号定位的中间代码 310
8．5 结构语句的中间代码 311
8．5．1 条件语句的中间代码 311
8．5．2 While语句的中间代码 312
8．5．3 Repeat语句的中间代码 313
8．5．4 For语句的中间代码 314
8．5．5 Case语句的中间代码 316
8．6 声明的中间代码 321
8．6．1 变量声明的中间代码 321
8．6．2 过程和函数的中间代码 321
练习题 322
第九章 中间代码优化 324
9．1 引言 324
9．1．1 优化目标和要求 324
9．1．2 优化的必要性 325
9．1．3 优化内容和难点 325
9．1．4 局部优化和全局优化 327
9．1．5 基本块和程序流图 328
9．2 常量表达式优化 329
9．2．1 常量表达式的局部优化 329
9．2．2 基于常量定值分析的常量表达式全局优化 330
9．2．3 可用常量定值的数据流分析 331
9．3 公共表达式优化 333
9．3．1 基于相似性的公共表达式局部优化 333
9．3．2 基于值编码的公共表达式局部优化 335
9．3．3 基于DAG的公共表达式局部优化 338
9．3．4 基于可用表达式分析的公共表达式全局优化 339
9．3．5 可用表达式定值的数据流分析 340
9．4 循环不变表达式外提 341
9．4．1 循环识别 341
9．4．2 外提对象和安全性 342
9．4．3 不变式外提的实现原理 343
9．4．4 过程/函数的副作用分析 346
9．4．5 一种简单的外提优化 349
9．4．6 循环必经点分析 350
9．5 循环内归纳表达式的优化 351
9．5．1 归纳变量和归纳表达式 351
9．5．2 归纳表达式的优化原理 352
9．5．3 乘法运算的强度削减优化 355
练习题 356
第十章 目标代码生成 358
10．1 目标代码 358
10．1．1 虚拟目标代码 358
10．1．2 实际目标代码 359
10．1．3 窥孔优化 361
10．2 临时变量 361
10．2．1 临时变量的特点 361
10．2．2 临时变量的存储空间 362
10．2．3 变量的状态描述 364
10．3 寄存器 365
10．3．1 寄存器分类 365
10．3．2 寄存器的状态描述 365
10．3．3 寄存器的分配 368
10．3．4 寄存器的释放代价 370
10．4 基于多元式的代码生成 371
10．4．1 编址模式（Addressing Mode） 371
10．4．2 间接编址模式的转换 372
10．4．3 目标代码生成基本技术 373
10．4．4 其他寄存器的状态追踪 379
10．5 基于树结构的代码生成 380
10．5．1 多元式到树的转换 380
10．5．2 计算寄存器个数 381
10．5．3 从带寄存器个数标记的树生成代码 382
10．6 基于DAG的代码生成 385
10．6．1 从树构造DAG 385
10．6．2 给DAG结点标上序号和虚寄存器 388
10．6．3 从带排序和虚寄存器标记的DAG生成代码 389
10．7 代码生成器的生成器 391
10．7．1 代码生成器的自动化 391
10．7．2 基于指令模板匹配的代码生成技术 391
10．7．3 基于语法分析的代码生成技术 394
10．8 其他 396
10．8．1 标号和GOTO的代码生成 396
10．8．2 过程/函数调用的代码生成 396
练习题 398
参考文献 400