第1章 编译器概述 1
1.1 为什么要学习编译技术 1
1.2 编译器和解释器 1
1.3 编译器的功能分解和组织结构 3
1.4 编译器的伙伴 4
1.5 编译器的复杂性 5
1.6 编译器的设计与实现 6
1.7 编译器的测试与维护 7
第2章 一个微型编译器 9
2.1 基础知识 9
2.2 ToyL语言 13
2.3 ToyL语言词法分析器 13
2.4 ToyL语言语法分析器 18
2.5 ToyL语言解释器 19
2.6 ToyL语言编译器 24
第3章 有穷自动机与词法分析 29
3.1 词法分析基础 29
3.1.1 词法分析器的功能 29
3.1.2 单词识别 31
3.1.3 词法分析的复杂性 31
3.1.4 字符串 32
3.1.5 保留字处理 32
3.1.6 空格符、回车符、换行符 33
3.1.7 括号类配对预检 34
3.1.8 词法错误修正 34
3.1.9 词法分析独立化的意义 35
3.2 有穷自动机 36
3.2.1 确定有穷自动机的定义 36
3.2.2 确定有穷自动机的实现 38
3.2.3 非确定有穷自动机 40
3.2.4 NFA到DFA的转换 40
3.2.5 确定有穷自动机的极小化 43
3.2.6 自动机状态转换表的实现 44
3.3 正则表达式 46
3.3.1 正则符号串集 46
3.3.2 正则表达式的定义 47
3.3.3 正则表达式的局限性 49
3.3.4 正则定义 49
3.3.5 正则表达式到有穷自动机的转换 50
3.4 词法分析器的构造 54
3.4.1 用DFA人工构造词法分析器 55
3.4.2 词法分析器的生成器Lex 58
练习 60
第4章 文法与语法分析 63
4.1 语法分析 63
4.1.1 语法分析器的输入 63
4.1.2 语法分析的任务 63
4.1.3 语法分析方法分类 64
4.2 文法和文法分析 64
4.2.1 上下文无关文法和语言 64
4.2.2 最左推导和最右推导 69
4.2.3 语法分析树与二义性 70
4.2.4 文法分析算法 72
4.2.5 自顶向下方法概述 76
4.2.6 自底向上方法概述 79
4.3 递归下降法——自顶向下分析 80
4.3.1 递归下降法原理 80
4.3.2 消除公共前缀 85
4.3.3 代入 86
4.3.4 消除左递归 87
4.4 LL分析方法——自顶向下分析 89
4.4.1 LL（1）文法 89
4.4.2 LL（1）分析表 91
4.4.3 LL（1）分析的驱动器 93
4.4.4 LL（1）中的If-Then-Else问题 94
4.4.5 LL（1）分析器的自动生成器LLGen 96
4.4.6 LL（1）分析法与递归下降法的比较 97
4.4.7 正则文法 99
4.5 LR方法——自底向上分析 101
4.5.1 句柄 102
4.5.2 活前缀 103
4.5.3 归约活前缀识别器——LR（0）自动机 105
4.5.4 LR（0）文法及其分析算法 115
4.5.5 SLR（1）文法及其分析算法 118
4.5.6 LR（1）文法 123
4.5.7 LALR（1）文法 127
4.5.8 二义性文法的处理 133
4.5.9 另一种Shift-Reduce分析技术：简单优先法 134
4.5.10 LL（1）和LALR（1）方法比较 137
4.6 LR分析器的生成器 138
4.6.1 LALR分析器的生成器YACC 138
4.6.2 LALR分析器的生成器LALRGen 139
4.7 语法错误处理 139
4.7.1 错误恢复和修复 139
4.7.2 递归下降分析的错误恢复 141
4.7.3 LL分析的错误恢复 143
4.7.4 LR分析的错误恢复 144
练习 145
第5章 语义分析 150
5.1 语义分析基础 150
5.1.1 语义分析内容 150
5.1.2 标识符信息的内部表示 151
5.1.3 类型信息的内部表示 155
5.1.4 运行时值的表示 159
5.2 符号表 160
5.2.1 符号表查找技术 160
5.2.2 符号表的局部化 164
5.2.3 二叉式局部符号表 165
5.2.4 散列式全局符号表 167
5.2.5 嵌套式全局符号表 168
5.2.6 符号表界面函数 169
5.3 类型分析 170
5.3.1 类型的等价性和相容性 170
5.3.2 类型分析的总控算法 171
5.3.3 类型名分析 172
5.3.4 枚举类型分析 173
5.3.5 数组类型分析 174
5.3.6 记录类型分析 175
5.3.7 联合类型分析 177
5.3.8 指针类型分析 178
5.3.9 递归类型分析 179
5.4 声明的语义分析 180
5.4.1 声明的语法结构 180
5.4.2 标号声明部分的语义分析 181
5.4.3 常量声明部分的语义分析 182
5.4.4 类型声明部分的语义分析 184
5.4.5 变量声明部分的语义分析 186
5.4.6 过程、函数声明的语义分析 189
5.5 执行体的语义分析 196
5.5.1 执行体的语义分析 196
5.5.2 带标号语句和转向语句的语义分析 197
5.5.3 赋值语句的语义分析 199
5.5.4 条件语句的语义分析 200
5.5.5 while循环语句的语义分析 200
5.5.6 for循环语句的语义分析 201
5.5.7 过程调用语句的语义分析 201
5.5.8 表达式的语义分析 204
5.5.9 变量的语义分析 206
练习 208
第6章 运行时的存储环境 210
6.1 运行时的存储空间结构与分配 210
6.1.1 运行时的存储空间基本结构 210
6.1.2 静态区的存储分配 210
6.1.3 栈区的存储分配 211
6.1.4 堆区的存储分配 212
6.1.5 堆区空间管理 214
6.2 过程活动记录与栈区组织结构 215
6.2.1 过程活动记录 216
6.2.2 活动记录的填写 218
6.2.3 栈区组织结构——AR链 219
6.3 运行时的变量访问环境 219
6.3.1 可访问活动记录 220
6.3.2 局部Display表方法 221
6.3.3 静态链方法 222
6.3.4 全局Display表方法和寄存器方法 224
6.3.5 无嵌套时的AR及访问环境 226
6.4 分程序和动态数组空间 226
6.4.1 无动态数组时的分程序空间 227
6.4.2 动态数组空间 230
练习 236
第7章 面向语法的语义描述 237
7.1 动作文法 237
7.1.1 动作文法定义 237
7.1.2 动作文法的递归实现 239
7.1.3 动作文法的LL实现 240
7.1.4 动作文法的LR实现 241
7.2 动作文法应用 246
7.2.1 用动作文法描述表达式计算 246
7.2.2 用动作文法描述表达式抽象树的构造 248
7.2.3 用动作文法描述语句抽象树的构造 250
7.3 抽象动作文法及其应用 252
7.3.1 抽象变量 252
7.3.2 抽象动作文法 253
7.3.3 栈式LL动作文法驱动器 254
7.3.4 抽象动作文法到栈式LL动作文法的转换 255
7.3.5 栈式LR动作文法驱动器 256
7.3.6 抽象动作文法到栈式LR动作文法的转换 259
7.4 属性文法 260
7.4.1 属性文法定义 260
7.4.2 属性语法树和属性依赖图 263
7.4.3 计算顺序 265
7.4.4 属性值的计算方法 266
7.4.5 拷贝型属性文法 268
7.5 属性文法在编译器设计中的应用 269
7.5.1 类型树的属性文法描述 269
7.5.2 表达式中间代码的属性文法描述 272
7.5.3 变量中间代码的属性文法描述 273
7.5.4 语句中间代码的属性文法描述 276
7.5.5 正则表达式到自动机转换的属性文法描述 278
7.6 S-属性文法及其属性计算 279
7.6.1 S-属性文法 279
7.6.2 S-属性文法的递归实现 279
7.6.3 S-属性文法的LR实现 281
7.7 L-属性文法及其属性计算 282
7.7.1 L-属性文法 282
7.7.2 L-属性文法的递归实现 283
7.7.3 L-属性文法的LR（1）实现 284
7.8 语义分析器的自动生成系统 287
7.8.1 YACC 287
7.8.2 LALRGen 291
7.8.3 Accent系统 294
练习 297
第8章 中间代码生成 299
8.1 中间代码 299
8.1.1 中间代码的种类 299
8.1.2 后缀式中间代码 300
8.1.3 三地址中间代码 301
8.1.4 抽象语法树和无环有向图 303
8.1.5 多元式中间代码 304
8.1.6 中间代码分量ARG结构 305
8.2 表达式的中间代码生成 309
8.2.1 表达式的语义信息 309
8.2.2 表达式的中间代码 309
8.2.3 变量的中间代码 311
8.2.4 表达式的中间代码生成 314
8.2.5 变量的中间代码生成 318
8.2.6 布尔表达式的短路中间代码 319
8.3 原子语句的中间代码生成 321
8.3.1 输入／输出语句的中间代码生成 321
8.3.2 goto语句和标号定位语句的中间代码生成 322
8.3.3 return语句的中间代码生成 322
8.3.4 赋值语句的中间代码生成 323
8.3.5 函数（过程）调用的中间代码生成 324
8.4 结构语句的中间代码生成 333
8.4.1 条件语句的中间代码生成 333
8.4.2 while语句的中间代码生成 336
8.4.3 repeat语句的中间代码生成 337
8.4.4 for语句的中间代码生成 338
8.4.5 case语句的中间代码生成 340
8.4.6 函数声明的中间代码生成 343
练习 345
第9章 中间代码优化 347
9.1 引言 347
9.1.1 优化的目标和要求 347
9.1.2 优化的必要性 347
9.1.3 优化的内容 348
9.1.4 局部优化和全局优化 350
9.1.5 基本块和程序流图 350
9.2 常表达式优化 352
9.2.1 常表达式的局部优化 352
9.2.2 基于常量定值分析的常表达式全局优化 353
9.2.3 常量定值分析 353
9.3 公共表达式优化 359
9.3.1 基于相似性的公共表达式局部优化 359
9.3.2 基于值编码的公共表达式局部优化 361
9.3.3 基于活跃代码分析的公共表达式全局优化 365
9.3.4 活跃运算代码分析 366
9.4 程序流图循环 369
9.4.1 循环的基本概念 369
9.4.2 支撑结点 372
9.4.3 自然循环 374
9.4.4 可归约程序流图 376
9.4.5 基于文本的循环及其处理 377
9.5 循环不变代码外提 379
9.5.1 代码外提的基本概念 379
9.5.2 循环不变代码的判定 380
9.5.3 循环不变代码外提的条件 381
9.5.4 基于文本循环和定值表的不变代码外提 382
9.5.5 一种简单的外提优化方案 386
9.5.6 别名分析 387
9.5.7 过程与函数的副作用分析 390
9.6 循环内归纳表达式的优化 393
9.6.1 归纳变量 393
9.6.2 归纳变量计算的优化算法原理 395
练习 397
第10章 目标代码生成 400
10.1 目标代码 400
10.1.1 虚拟机代码 400
10.1.2 目标机代码 400
10.1.3 窥孔优化 403
10.2 临时变量 403
10.2.1 临时变量的特点 404
10.2.2 临时变量的存储空间 404
10.2.3 临时变量的存储分配 405
10.2.4 变量状态描述 406
10.3 寄存器 407
10.3.1 寄存器分类及其使用准则 407
10.3.2 寄存器分配单位 408
10.3.3 寄存器状态描述 409
10.3.4 寄存器分配算法 410
10.4 基于三地址中间代码的目标代码生成 412
10.4.1 目标地址生成 412
10.4.2 间接目标地址的转换 413
10.4.3 表达式中间代码的目标代码生成 414
10.4.4 赋值中间代码的目标代码生成 421
10.4.5 其他寄存器分配法 422
10.4.6 标号和goto语句中间代码的目标代码生成 424
10.4.7 return中间代码的目标代码生成 426
10.4.8 变量中间代码的目标代码生成 426
10.4.9 函数调用中间代码的目标代码生成 428
10.5 基于AST的代码生成 435
10.5.1 三地址中间代码到AST的转换 435
10.5.2 标记需用寄存器个数 436
10.5.3 从带寄存器个数标记的AST生成代码 437
10.6 基于DAG的代码生成 438
10.6.1 从AST到DAG的转换 438
10.6.2 DAG排序和虚寄存器 440
10.6.3 从带序号和虚寄存器标记的DAG生成代码 442
10.7 代码生成器的自动生成 443
10.7.1 代码生成器的自动化 443
10.7.2 基于指令模板匹配的代码生成技术 444
10.7.3 基于语法分析的代码生成技术 446
练习 448
第11章 对象式语言的实现 451
11.1 引言 451
11.2 SOOL语法 451
11.2.1 程序 451
11.2.2 分程序 452
11.2.3 类声明 452
11.2.4 类型 453
11.2.5 变量声明 453
11.2.6 函数声明和方法声明 453
11.2.7 语句 454
11.2.8 变量 454
11.2.9 表达式 454
11.2.10 程序示例 455
11.3 SOOL语义 457
11.3.1 声明的作用域 457
11.3.2 Class声明的语义 457
11.3.3 语句的语义 458
11.4 SOOL语义分析 459
11.4.1 标识符的符号表项 459
11.4.2 符号表结构 460
11.4.3 符号表的局部化 462
11.5 SOOL目标代码 462
11.5.1 对象空间 463
11.5.2 当前对象——self 463
11.5.3 活动记录 464
11.5.4 成员变量的目标地址 465
11.5.5 表达式的目标代码 465
11.5.6 Offset原理 466
11.5.7 类的多态性 467
11.5.8 目标代码区 468
11.5.9 方法的动态绑定 468
11.5.10 快速动态绑定目标代码 471
主要参考文献 473