目 录 1
第1章导论 1
1.1 为什么学习编译程序构造 4
1.1.1编译程序构造是非常成功的 4
1.1.2编译程序构造的广泛应用 6
1.1.3编译程序包含普遍适用的算法 6
1.2一个简单的传统的模块化编译程序／解释程序 6
1.2.1抽象语法树 7
1.2.2范例编译程序的结构 8
1.23 范例编译程序的语言 9
1.2.4 范例编译程序的词法分析 10
1.2.5范例编译程序的语法分析 11
1.2.6范例编译程序的上下文处理 14
1.2.7范例编译程序的代码生成 14
1.2.8范例编译程序的解释程序 15
1.3一个更接近于实际的编译程序的结构 16
1.3.1结构 17
1.3.2运行时系统 18
1.3.3捷径 18
1.4编译程序体系结构 18
1.4.1编译程序的宽度 19
1.4.2谁主控 20
1.5一个优秀编译程序的特性 22
1.6可移植性和可重定目标性 23
1.7优化的位置和效用 23
1.8编译程序构造简史 24
1.8.1 1945～1960年：代码生成 24
1.8.2 1960～1975年：分析 24
1.8.3 1975年至今：代码生成和代码优化；范型 24
1.9.2产生式过程 25
1.9.1 文法形式 25
1.9文法 25
1.9.3文法的扩展形式 27
1.9.4文法特性 27
1.9.5文法形式化方法 28
1.10闭包算法 29
1.10.1 闭包算法的迭代实现 31
1.11 本书使用的概要代码 33
1.12小结 33
第2章从程序文本到抽象语法树 38
2.1 从程序文本到记号——词法结构 41
2.1.1读程序文本 41
2.1.2词法分析与语法分析 42
2.1.3正则表达式和正则描述 43
2.1.4词法分析 44
2.1.5手动产生词法分析程序 45
2.1.6 自动产生词法分析程序 50
2.1.7转换表压缩 63
2.1.8词法分析程序的错误处理 68
2.1.9一个传统的词法分析程序产生器——lex 69
2.1.10记号的词法识别 70
2.1.11 符号表 72
2.1.12宏处理和文件包含 76
2.1.13小结 80
2.2从记号到语法树——语法分析 81
2.2.1 语法分析的两种方法 82
2.2.2错误检测和错误恢复 84
2.2.3手工生成一个自顶向下的语法分析程序 86
2.2.4 自动生成一个自顶向下的语法分析程序 88
2.2.5自动创建一个自底向上的语法分析程序 111
2.3小结 132
第3章注释抽象语法树——上下文 142
3.1属性文法 143
3.1.1依赖图 146
3.1.2属性计算 147
3.1.3循环处理 153
3.1.4属性分配 158
3.1.5多次访问属性文法 158
3.1.6属性文法类型的总结 167
3.1.7 L－属性文法 167
3.1.8 S－属性文法 170
3.1.9 L－属性文法与S－属性文法的等价性 171
3.1.10扩展的文法符号和属性文法 172
3.1.1 1 小结 173
3.2手工方法 173
3.2.1线性化AST 174
3.2.2符号解释 178
3.2.3数据流方程 184
3.2.4过程间的数据流分析 188
3.2.5上传信息流——活跃分析 189
3.2.6符号解释和数据流方程的比较 194
3.3小结 194
第4章处理中间代码 202
4.1解释 203
4.1.1递归解释 203
4.1.2迭代解释 207
4.2代码生成 210
4.2.1 避免完全的代码生成 213
4.2.2开始点 214
4.2.3直接代码生成 214
4.2.4简单代码生成 218
4.2.5基本块的代码生成 230
4.2.6 BURS代码生成和动态程序设计 241
4.2.7通过图着色的寄存器分配 255
4.2.8超级编译 259
4.2.9代码生成技术的评价 261
4.2.10代码优化器的调试 261
4.2.11 预处理中间代码 262
4.2.12后处理目标代码 265
4.2.13机器代码生成 267
4.3汇编程序、连接程序和装入程序 268
4.3.1 汇编程序设计问题 270
4.3.2连接程序设计问题 272
4.4小结 273
第5章存储管理 283
5.1 显式回收的数据空间分配 284
5.1.1基本存储空间分配 285
5.1.2链表 288
5.1.3可扩展数组 290
5.2隐式回收的数据空间分配 291
5.2.1基本垃圾收集算法 291
5.2.2背景预备 292
5.2.3引用计数 297
5.2.4标记和扫描 300
5.2.5两空间复制 303
5.2.6紧缩 306
5.2.7世代垃圾收集 307
5.3小结 307
第6章命令式和面向对象程序 313
6.1上下文处理 314
6.1.1 识别 315
6.1.2类型检查 321
6.2源语言数据表示和处理 328
6.1.3小结 328
6.2.1基本类型 329
6.2.2枚举类型 329
6.2.3指针类型 329
6.2.4记录类型 332
6.2.5共用体类型 333
6.2.6数组类型 334
6.2.7集合类型 336
6.2.8例程类型 336
6.2.9对象类型 337
6.2.10接口类型 344
6.3例程及其活动 345
6.3.1 活动记录 345
6.3.2 列程 347
6.3.3例程上的操作 348
6.3.4非嵌套例程 350
6.3.5嵌套例程 352
6.3.6 Lambda提升 357
6.3.7迭代器和协作例程 358
6.4控制流语句的代码生成 359
6.4.1局部控制流 359
6.4.2例程调用 366
6.4.3运行时错误处理 372
6.5模块的代码生成 374
6.5.1名字生成 375
6.5.2模块初始化 375
6.5.3泛型的代码生成 376
6.6小结 377
第7章函数式程序 386
7.1.1越位规则 387
7.1 Haskell简介 387
7.1.3列表内涵 388
7.1.2列表 388
7.1.4模式匹配 389
7.1.5多态类型 390
7.1.6引用透明性 391
7.1.7高阶函数 391
7.1.8惰性计算 392
7.2编译函数式语言 393
7.2.1函数核 394
7.3多态类型检查 395
7.3.1 多态函数应用 396
7.4.1列表的翻译 397
7.4.2模式匹配的翻译 397
7.4脱糖 397
7.4.3列表内涵的翻译 399
7.4.4嵌套函数的翻译 401
7.5图归约 402
7.5.1归约顺序 405
7.5.2归约引擎 406
7.6函数核程序的代码生成 409
7.6.1 避免一些应用框架的构造 411
7.7优化函数核 412
7.7.1严格性分析 413
7.7.2装箱分析 417
7.7.3尾部调用 417
7.7.4累加器转换 419
7.7.5局限性 420
7.8.2指针标记 421
7.8.3聚集结点分配 421
7.8.1 可变长度结点 421
7.8高级图处理 421
7.8.4向量应用结点 422
7.9小结 422
第8章逻辑式程序 427
8.1逻辑式程序设计模型 428
8.1.1构建模块 428
8.1.2推理机制 430
8.2解释的通用实现模型 431
8.2.1解释程序指令 432
8.2.2避免冗余目标列表 434
8.2.3避免复制目标列表尾部 434
8.3合一 435
8.3.1 结构、列表和集合的合一 435
8.3.2合一的实现 437
8.3.3 两个自由变量的合一 440
8.3.4小结 441
8.4编译的通用实现模型 441
8.4.1列表程序 442
8.4.2编译子句的搜索和合一 444
8.4.3 WAM中的优化子句选择 448
8.4.4应用“cut”机制 450
8.4.5谓词assert和retract的实现 452
8.5合一的编译代码 455
8.5.1 WAM中的合一指令 456
8.5.2通过手工局部计算得到合一指令 457
8.5.3 WAM中的结构合一 462
8.5.4一种优化：读／写模式 464
8.5.5 WAM中合一结构的进一步优化 466
8.5.6小结 467
第9章并行和分布式程序 472
9.1.1共享变量和管程 474
9.1并行程序设计模型 474
9.1.2消息传递模型 476
9.1.3面向对象语言 477
9.1.4 Linda元组空间 477
9.1.5数据并行语言 478
9.2进程和线程 479
9.3共享变量 481
9.3.1锁 481
9.3.2管程 481
9.4消息传递 482
9.4.1接收方定位 483
9.4.2编组 483
9.4.3消息的类型检查 484
9.4.4消息选择 484
9.5.1对象定位 485
9.5并行的面向对象语言 485
9.5.2对象迁移 486
9.5.3对象复制 487
9.6元组空间 488
9.6.1避免关联寻址的开销 488
9.6.2元组空间的分布实现 490
9.7自动并行 492
9.7.1 自动地使用并行性 492
9.7.2数据依赖 494
9.7.3循环转换 495
9.7.4分布式存储器的自动并行 496
9.8小结 498
附录A一个简单的面向对象编译程序／解释程序 502
附录B练习答案 509
附录C参考文献 519
附录D术语表 527