第1章编译简介 1
1.1编译器 1
1.1.1编译的分析－综合模型 1
1.1.2编译器的前驱与后继 3
1.2源程序分析 3
1.2.1词法分析 3
1.2.2语法分析 3
1.2.3语义分析 5
1.2.4文本格式器中的分析 5
1.3编译器的各阶段 6
1.3.1符号表管理 7
1.3.2错误检测与报告 7
1.3.3各分析阶段 7
1.3.4中间代码生成 9
1.3.5代码优化 9
1.3.6代码生成 10
1.4编译器的伙伴 10
1.4.1预处理器 10
1.4.2汇编器 11
1.4.3两遍汇编 12
1.4.4装配器和连接编辑器 12
1.5编译器各阶段的分组 13
1.5.1前端与后端 13
1.5.2编译器的遍 13
1.5.3减少编译的遍数 14
1.6编译器的构造工具 14
参考文献注释 15
第2章简单的一遍编译器 17
2.1概述 17
2.2语法定义 17
2.2.1分析树 19
2.2.2二义性 20
2.2.3操作符的结合规则 20
2.2.4操作符的优先级 21
2.3语法制导翻译 22
2.3.1后缀表示 22
2.3.2语法制导定义 22
2.3.3综合属性 23
2.3.4深度优先遍历 24
2.3.5翻译模式 25
2.3.6翻译的输出 25
2.4语法分析 26
2.4.1自顶向下语法分析 27
2.4.2预测分析法 29
2.4.3何时使用∈产生式 30
2.4.4设计一个预测语法分析器 30
2.4.5左递归 31
2.5简单表达式的翻译器 32
2.5.1抽象语法和具体语法 32
2.5.2调整翻译模式 33
2.5.3非终结符expr、term和rest的过程 33
2.5.4翻译器的优化 35
2.5.5完整程序 35
2.6词法分析 37
2.6.1剔除空白符和注释 37
2.6.2常数 37
2.6.3识别标识符和关键字 37
2.6.4词法分析器的接口 38
2.6.5词法分析器 38
2.7符号表 40
2.7.1符号表接口 40
2.7.2处理保留的关键字 41
2.7.3符号表的实现方法 41
2.8抽象堆栈机 42
2.8.1算术指令 42
2.8.2左值和右值 43
2.8.3堆栈操作 43
2.8.4表达式的翻译 43
2.8.5控制流 44
2.8.6语句的翻译 44
2.8.7输出一个翻译 45
2.9技术的综合 46
2.9.1翻译器的描述 46
2.9.2词法分析器模块lexer.c 47
2.9.3语法分析器模块parser.c 48
2.9.4输出模块emitter.c 48
2.9.5符号表模块symbol.c和init.c 48
2.9.6错误处理模块error.c 48
2.9.7编译器的建立 48
2.9.8程序清单 49
练习 53
编程练习 54
参考文献注释 55
第3章词法分析 57
3.1词法分析器的作用 57
3.1.1词法分析中的问题 58
3.1.2记号、模式、词素 58
3.1.3记号的属性 59
3.1.4词法错误 60
3.2输入缓冲 60
3.2.1双缓冲区 61
3.2.2标志 62
3.3记号的描述 62
3.3.1串和语言 62
3.3.2语言上的运算 63
3.3.3正规表达式 64
3.3.4正规定义 65
3.3.5缩写表示法 66
3.3.6非正规集 66
3.4记号的识别 67
3.4.1状态转换图 68
3.4.2状态转换图的实现 70
3.5词法分析器描述语言 72
3.5.1 Lex说明 72
3.5.2超前扫描操作 75
3.6有穷自动机 76
3.6.1不确定的有穷自动机 77
3.6.2确定的有穷自动机 78
3.6.3从NFA到DFA的变换 79
3.7从正规表达式到NFA 81
3.7.1从正规表达式构造NFA 81
3.7.2 NFA的双堆栈模拟 84
3.7.3时间空间的权衡 85
3.8设计词法分析器的生成器 85
3.8.1基于NFA的模式匹配 86
3.8.2词法分析器的DFA 88
3.8.3实现超前扫描操作 88
3.9基于DFA的模式匹配器的优化 89
3.9.1 NFA的重要状态 89
3.9.2从正规表达式到DFA 89
3.9.3最小化DFA的状态数 93
3.9.4词法分析器的状态最小化 95
3.9.5表压缩方法 95
练习 97
编程练习 103
参考文献注释 103
第4章语法分析 105
4.1语法分析器的作用 105
4.1.1语法错误的处理 106
4.1.2错误恢复策略 108
4.2上下文无关文法 109
4.2.1符号的使用约定 110
4.2.2推导 110
4.2.3分析树和推导 112
4.2.4二义性 113
4.3文法的编写 113
4.3.1正规表达式和上下文无关文法的比较 114
4.3.2验证文法所产生的语言 114
4.3.3消除二义性 115
4.3.4消除左递归 116
4.3.5提取左因子 117
4.3.6非上下文无关语言的结构 118
4.4自顶向下语法分析 120
4.4.1递归下降语法分析法 120
4.4.2预测语法分析器 121
4.4.3预测语法分析器的状态转换图 121
4.4.4非递归的预测分析 123
4.4.5 FIRST和FOLLOW 124
4.4.6预测分析表的构造 125
4.4.7 LL（1）文法 126
4.4.8预测分析的错误恢复 127
4.5自底向上语法分析 128
4.5.1句柄 129
4.5.2句柄裁剪 130
4.5.3用栈实现移动归约分析 131
4.5.4活前缀 133
4.5.5移动归约分析过程中的冲突 133
4.6算符优先分析法 134
4.6.1使用算符优先关系 135
4.6.2从结合律和优先级获得算符优先关系 136
4.6.3处理一元操作符 137
4.6.4优先函数 137
4.6.5算符优先分析中的错误恢复 139
4.7 LR语法分析器 142
4.7.1 LR语法分析算法 142
4.7.2 LR文法 145
4.7.3构造SLR语法分析表 146
4.7.4构造规范LR语法分析表 151
4.7.5构造LALR语法分析表 155
4.7.6 LALR语法分析表的有效构造方法 158
4.7.7 LR语法分析表的压缩 161
4.8二义文法的应用 163
4.8.1使用优先级和结合规则来解决分析动作的冲突 163
4.8.2悬空else的二义性 164
4.8.3特例产生式引起的二义性 165
4.8.4LR语法分析中的错误恢复 167
4.9语法分析器的生成器 168
4.9.1语法分析器的生成器Yacc 169
4.9.2用Yacc处理二义文法 171
4.9.3用Lex建立Yacc的词法分析器 173
4.9.4 Yacc的错误恢复 174
练习 174
参考文献注释 182
第5章语法制导翻译 185
5.1语法制导定义 185
5.1.1语法制导定义的形式 186
5.1.2综合属性 186
5.1.3继承属性 187
5.1.4依赖图 187
5.1.5计算顺序 189
5.2语法树的构造 189
5.2.1语法树 190
5.2.2构造表达式的语法树 190
5.2.3构造语法树的语法制导定义 191
5.2.4表达式的无环有向图 192
5.3自底向上计算S属性定义 194
5.4 L属性定义 195
5.4.1 L属性定义 196
5.4.2翻译模式 196
5.5自顶向下翻译 198
5.5.1从翻译模式中消除左递归 198
5.5.2预测翻译器的设计 201
5.6自底向上计算继承属性 202
5.6.1删除嵌入在翻译模式中的动作 202
5.6.2分析栈中的继承属性 203
5.6.3模拟继承属性的计算 204
5.6.4用综合属性代替继承属性 206
5.6.5一个难计算的语法制导定义 207
5.7递归计算 207
5.7.1从左到右遍历 207
5.7.2其他遍历方法 208
5.8编译时属性值的空间分配 209
5.8.1在编译时为属性分配空间 209
5.8.2避免复制 211
5.9编译器构造时的空间分配 211
5.9.1从文法中预知生存期 212
5.9.2不相重叠的生存期 214
5.10语法制导定义的分析 215
5.10.1属性的递归计算 216
5.10.2强无环的语法制导定义 216
5.10.3环形检测 217
练习 219
参考文献注释 221
第6章类型检查 223
6.1类型系统 224
6.1.1类型表达式 224
6.1.2类型系统 225
6.1.3静态和动态类型检查 226
6.1.4错误恢复 226
6.2一个简单的类型检查器的说明 226
6.2.1一种简单语言 226
6.2.2表达式的类型检查 227
6.2.3语句的类型检查 228
6.2.4函数的类型检查 228
6.3类型表达式的等价 229
6.3.1类型表达式的结构等价 229
6.3.2类型表达式的名字 231
6.3.3类型表示中的环 232
6.4类型转换 233
6.5函数和运算符的重载 234
6.5.1子表达式的可能类型的集合 235
6.5.2缩小可能类型的集合 236
6.6多态函数 237
6.6.1为什么要使用多态函数 237
6.6.2类型变量 238
6.6.3包含多态函数的语言 239
6.6.4代换、实例和合一 240
6.6.5多态函数的检查 241
6.7合一算法 244
练习 247
参考文献注释 251
第7章运行时环境 253
7.1源语言问题 253
7.1.1过程 253
7.1.2活动树 253
7.1.3控制栈 255
7.1.4声明的作用域 256
7.1.5名字的绑定 256
7.1.6一些问题 257
7.2存储组织 257
7.2.1运行时内存的划分 257
7.2.2活动记录 258
7.2.3编译时的局部数据布局 259
7.3存储分配策略 260
7.3.1静态存储分配 260
7.3.2栈式存储分配 262
7.3.3悬空引用 265
7.3.4堆式存储分配 265
7.4对非局部名字的访问 266
7.4.1程序块 267
7.4.2无嵌套过程的词法作用域 268
7.4.3包含嵌套过程的词法作用域 269
7.4.4动态作用域 274
7.5参数传递 275
7.5.1传值调用 275
7.5.2引用调用 276
7.5.3复制－恢复 277
7.5.4传名调用 277
7.6符号表 278
7.6.1符号表表项 278
7.6.2名字中的字符 279
7.6.3存储分配信息 280
7.6.4符号表的线性表数据结构 280
7.6.5散列表 281
7.6.6表示作用域的信息 283
7.7支持动态存储分配的语言措施 285
7.7.1垃圾单元 285
7.7.2悬空引用 286
7.8动态存储分配技术 287
7.8.1固定块的显式分配 287
7.8.2变长块的显式分配 287
7.8.3隐式存储释放 288
7.9 Fortran语言的存储分配 288
7.9.1 COMMON域中的数据 289
7.9.2一个简单的等价算法 290
7.9.3 Fortran语言的等价算法 292
7.9.4映射数据区 294
练习 294
参考文献注释 298
第8章中间代码生成 299
8.1中间语言 299
8.1.1图表示 299
8.1.2三地址码 300
8.1.3三地址语句的类型 301
8.1.4语法制导翻译生成三地址码 302
8.1.5三地址语句的实现 303
8.1.6表示方法比较：间址的使用 305
8.2声明语句 305
8.2.1过程中的声明语句 305
8.2.2跟踪作用域信息 306
8.2.3记录中的域名 308
8.3赋值语句 309
8.3.1符号表中的名字 309
8.3.2临时名字的重用 310
8.3.3寻址数组元素 311
8.3.4数组元素寻址的翻译模式 312
8.3.5赋值语句中的类型转换 314
8.3.6记录域的访问 315
8.4布尔表达式 315
8.4.1翻译布尔表达式的方法 316
8.4.2数值表示 316
8.4.3短路代码 317
8.4.4控制流语句 317
8.4.5布尔表达式的控制流翻译 319
8.4.6混合模式的布尔表达式 321
8.5 case语句 321
8.6回填 323
8.6.1布尔表达式 323
8.6.2控制流语句 326
8.6.3翻译的实现方案 326
8.6.4标号和goto 327
8.7过程调用 328
8.7.1调用序列 328
8.7.2一个简单的例子 328
练习 329
参考文献注释 331
第9章代码生成 333
9.1代码生成器设计中的问题 333
9.1.1代码生成器的输入 333
9.1.2目标程序 334
9.1.3存储管理 334
9.1.4指令选择 334
9.1.5寄存器分配 335
9.1.6计算次序的选择 336
9.1.7代码生成方法 336
9.2目标机器 336
9.3运行时存储管理 338
9.3.1静态分配 339
9.3.2栈式分配 340
9.3.3名字的运行地址 342
9.4基本块和流图 343
9.4.1基本块 343
9.4.2基本块的变换 344
9.4.3保结构变换 344
9.4.4代数变换 345
9.4.5流图 345
9.4.6基本块的表示 345
9.4.7循环 346
9.5下次引用信息 346
9.5.1计算下次引用信息 346
9.5.2临时名字的存储分配 347
9.6一个简单的代码生成器 347
9.6.1寄存器描述符和地址描述符 348
9.6.2代码生成算法 348
9.6.3函数getreg 349
9.6.4为其他类型的语句生成代码 350
9.6.5条件语句 351
9.7寄存器分配与指派 351
9.7.1全局寄存器分配 352
9.7.2引用计数 352
9.7.3外层循环的寄存器指派 353
9.7.4图染色法寄存器分配 354
9.8基本块的dag表示法 354
9.8.1 dag的构造 355
9.8.2 dag的应用 357
9.8.3数组、指针和过程调用 358
9.9窥孔优化 359
9.9.1冗余加载与保存 360
9.9.2不可达代码 360
9.9.3控制流优化 361
9.9.4代数化简 361
9.9.5强度削弱 361
9.9.6机器语言的使用 362
9.10从dag生成代码 362
9.10.1重排序 362
9.10.2对dag的启发式排序 362
9.10.3树的最优排序 363
9.10.4标记算法 364
9.10.5从标记树中产生代码 364
9.10.6多寄存器操作 367
9.10.7代数性质 367
9.10.8公共子表达式 368
9.11动态规划代码生成算法 368
9.11.1一种寄存器计算机 368
9.11.2动态规划的原理 369
9.11.3邻近计算 369
9.11.4动态规划算法 369
9.12代码生成器的生成器 371
9.12.1采用重写树技术的代码生成 371
9.12.2借助语法分析的模式匹配 375
9.12.3用于语义检查的例程 376
练习 376
参考文献注释 378
第10章代码优化 381
10.1引言 381
10.1.1代码改进变换的准则 381
10.1.2性能的提高 382
10.1.3优化编译器的组织 383
10.2优化的主要种类 384
10.2.1保持功能变换 385
10.2.2公共子表达式 386
10.2.3复制传播 387
10.2.4无用代码删除 387
10.2.5循环优化 388
10.2.6代码外提 388
10.2.7归纳变量和强度削弱 388
10.3基本块的优化 390
10.4流图中的循环 392
10.4.1支配节点 392
10.4.2自然循环 393
10.4.3内循环 393
10.4.4前置首节点 394
10.4.5可约流图 394
10.5全局数据流分析介绍 395
10.5.1点和路径 396
10.5.2到达定义 396
10.5.3结构化程序的数据流分析 397
10.5.4对数据流信息的保守估计 399
10.5.5 in和out的计算 400
10.5.6处理循环 401
10.5.7集合的表示 402
10.5.8局部到达定义 403
10.5.9引用－定义链 404
10.5.10计算顺序 404
10.5.11一般控制流 404
10.6数据流方程的迭代解 405
10.6.1到达定义的迭代算法 406
10.6.2可用表达式 408
10.6.3活跃变量分析 410
10.6.4定义－引用链 411
10.7代码改进变换 412
10.7.1全局公共子表达式删除 412
10.7.2复制传播 413
10.7.3循环不变计算的检测 415
10.7.4代码外提 415
10.7.5可选的代码外提方案 417
10.7.6代码外提后对数据流信息的维护 418
10.7.7归纳变量删除 418
10.7.8带有循环不变表达式的归纳变量 421
10.8处理别名 422
10.8.1一种简单的指针语言 422
10.8.2指针赋值的作用 422
10.8.3利用指针信息 424
10.8.4过程间的数据流分析 425
10.8.5带有过程调用的代码模型 425
10.8.6别名的计算 426
10.8.7存在过程调用时的数据流分析 427
10.8.8 change信息的用途 428
10.9结构化流图的数据流分析 429
10.9.1深度优先搜索 429
10.9.2流图的深度优先表示中的边 431
10.9.3流图的深度 431
10.9.4区间 432
10.9.5区间划分 432
10.9.6区间图 433
10.9.7节点分裂 433
10.9.8 T1-T2分析 434
10.9.9区域 434
10.9.10寻找支配节点 435
10.10高效数据流算法 436
10.10.1迭代算法中的深度优先顺序 436
10.10.2基于结构的数据流分析 437
10.10.3对基于结构的算法的一些速度上的改进 440
10.10.4处理不可约流图 441
10.11一个数据流分析工具 441
10.11.1数据流分析框架 442
10.11.2数据流分析框架的公理 443
10.11.3单调性和分配性 444
10.11.4数据流问题的聚合路径解 447
10.11.5流问题的保守解 447
10.11.6通用框架的迭代算法 448
10.11.7一个数据流分析工具 448
10.11.8算法10.18的性质 449
10.11.9算法10.18的收敛性 449
10.11.10初始化的修正 450
10.12类型估计 450
10.12.1处理无穷类型集 451
10.12.2一个简单的类型系统 452
10.12.3前向方案 452
10.12.4后向方案 453
10.13优化代码的符号调试 455
10.13.1基本块中变量值的推断 456
10.13.2全局优化的影响 459
10.13.3归纳变量删除 459
10.13.4全局公共子表达式删除 459
10.13.5代码外提 459
练习 460
参考文献注释 465
第11章编写一个编译器 469
11.1编译器设计 469
11.1.1源语言问题 469
11.1.2目标语言问题 469
11.1.3性能标准 469
11.2编译器开发方法 470
11.3编译器开发环境 472
11.4测试与维护 474
第12章编译器实例 475
12.1数学排版预处理器EQN 475
12.2 Pascal编译器 475
12.3 C编译器 476
12.4 Fortran H编译器 477
12.4.1 Fortran H中的代码优化 478
12.4.2代数优化 478
12.4.3寄存器优化 478
12.5 BLISS/1 1编译器 479
12.6 Modula-2优化编译器 480
附录一个程序设计项目 483
参考文献 489
索引 511