程序设计语言：实践之路

前言 xvii
第1章 引言 1
1.1 语言设计的艺术 3
1.2 程序设计语言的谱系 5
1.3 为什么研究程序设计语言 7
1.4 编译和解释 9
1.5 程序设计环境 14
1.6 编译概览 15
1.6.1 词法和语法分析 16
1.6.2 语义分析和中间代码生成 18
1.6.3 目标代码生成 22
1.6.4 代码改进 24
1.7 总结和注记 24
1.8 复习 25
1.9 练习 26
1.10 有关参考文献 28
第2章 程序设计语言的语法 31
2.1 描述语法：正则表达式和上下文无关文法 32
2.1.1 单词和正则表达式 33
2.1.2 上下文无关文法 34
2.1.3 推导和语法分析树 36
2.2 识别语法：扫描器和语法分析器 39
2.2.1 扫描 40
2.2.2 自上而下和自下而上的语法分析 48
2.2.3 递归下降 51
2.2.4 语法错误 57
2.2.5 表格驱动的自上而下语法分析 62
2.2.6 自下而上的语法分析 75
2.3* 理论基础 87
2.3.1 有穷自动机 88
2.3.2 下推自动机 92
2.3.3 文法和语言类 93
2.4 总结和注记 94
2.5 复习 97
2.6 练习 98
2.7 有关参考文献 102
第3章 名字、作用域和约束 105
3.1 约束时间的概念 106
3.2 对象生存期和存储管理 108
3.2.1 基于堆栈的分配 111
3.2.2 堆分配 113
3.2.3 废料收集 114
3.3 作用域规则 115
3.3.1 静态作用域 116
3.3.2 动态作用域 129
3.3.3 符号表 132
3.3.4 关联表和中心引用表列 137
3.4 引用环境的约束 139
3.4.1 子程序闭包 141
3.4.2 一级和二级子程序 143
3.5 重载和相关概念 144
3.6 语言设计中与名字有关的缺陷 149
3.6.1 作用域规则 149
3.6.2 分别编译 151
3.7 总结和注记 155
3.8 复习 157
3.9 练习 158
3.10 有关参考文献 162
第4章 语义分析 165
4.1 语义分析器所扮演的角色 166
4.2 属性文法 168
4.3 属性流 170
4.4 动作例程 179
4.5 属性的空间管理 180
4.5.1 自下而上求值 181
4.5.2 自上而下求值 186
4.6 语法树的标注 191
4.7 总结和注记 197
4.8 复习 198
4.9 练习 199
4.10 有关参考文献 202
第5章 汇编层计算机体系结构 203
5.1 工作站的微体系结构 204
5.2 存储器层次结构 207
5.3 数据表示 209
5.3.1 整数算术 211
5.3.2 浮点算术 212
5.4 指令集的体系结构 214
5.4.1 寻址模式 215
5.4.2 条件分支 217
5.5 处理器体系结构的演化 218
5.5.1 两个实例体系结构：680x0和MIPS 220
5.5.2 伪汇编记法形式 225
5.6 为新型处理器做编译 227
5.6.1 维持流水线满 227
5.6.2 寄存器分配 234
5.7 总结和注记 242
5.8 复习 243
5.9 练习 244
5.10 有关参考文献 247
第6章 控制流 249
6.1 表达式求值 250
6.1.1 优先级和结合性 251
6.1.2 赋值 254
6.1.3 表达式里的顺序 262
6.1.4 短路求值 265
6.2 结构化和非结构化的流程 267
6.3 顺序复合 270
6.4 选择 271
6.4.1 短路条件 272
6.4.2 分情况/开关语句 275
6.5 迭代 280
6.5.1 枚举控制的循环 280
6.5.2 组合循环 286
6.5.3 迭代器 287
6.5.4 逻辑控制的循环 294
6.6 递归 297
6.6.1 迭代和递归 297
6.6.2 应用序和正则序求值 301
6.7 非确定性 303
6.8 总结和注记 308
6.9 复习 310
6.10 练习 311
6.11 有关参考文献 316
第7章 数据类型 319
7.1 类型系统 320
7.1.1 类型的定义 322
7.1.2 类型的分类 323
7.2 类型检查 330
7.2.1 类型等价 330
7.2.2 类型变换和转换 334
7.2.3 类型相容和强制 337
7.2.4 类型推理 341
7.2.5 ML的类型系统 344
7.3 记录（结构）与变体（联合） 351
7.3.1 语法和操作 351
7.3.2 存储布局和紧缩 353
7.3.3 With语句 355
7.3.4 变体记录 358
7.4 数组 365
7.4.1 语法和操作 365
7.4.2 维数、上下界和分配 369
7.4.3 数组的布局 373
7.5 字符串 379
7.6 集合 381
7.7 指针和递归类型 382
7.7.1 语法和操作 383
7.7.2 悬空引用 391
7.7.3 废料收集 395
7.8 表 401
7.9 文件和输入/输出 403
7.9.1 交互式I/O 404
7.9.2 基于文件的I/O 405
7.9.3 正文I/O 407
7.10 相等检测和赋值 414
7.11 总结和注记 416
7.12 复习 418
7.13 练习 420
7.14 有关参考文献 425
第8章 子程序和控制抽象 427
8.1 重温堆栈布局 428
8.2 调用序列 431
8.2.1 实例研究：在MIPS上实现C 434
8.2.2 实例研究：在680x0上实现Pascal 437
8.2.3 在线展开 441
8.3 参数传递 442
8.3.1 参数模式 443
8.3.2 专用的参数 453
8.3.3 函数返回 457
8.4 通用型过程和模块 459
8.5 异常处理 464
8.5.1 异常的定义 466
8.5.2 异常的传播 468
8.5.3 实例：递归下降语法分析中的短语层恢复 470
8.5.4 异常的实现 471
8.6 协作程序 474
8.6.1 堆栈分配 476
8.6.2 转移 478
8.6.3 迭代器 479
8.6.4 实例：离散事件模拟 480
8.7 总结和注记 484
8.8 复习 485
8.9 练习 486
8.10 有关参考文献 489
第9章 构造可运行程序 491
9.1 后端编译器结构 491
9.1.1 一个实例 492
9.1.2 阶段和遍 496
9.2 中间形式 496
9.2.1 Diana 498
9.2.2 GNU的RTL 499
9.3 代码生成 503
9.3.1 一个属性文法实例 504
9.3.2 寄存器分配 504
9.4 地址空间组织 507
9.5 汇编 510
9.5.1 指令发射 511
9.5.2 为名字指定地址 514
9.6 连接 515
9.6.1 重定位和名字解析 515
9.6.2 类型检查 516
9.7 动态连接 518
9.7.1 与定位无关的代码 519
9.7.2 完全动态连接（惰性连接） 521
9.8 总结和注记 522
9.9 复习 523
9.10 练习 524
9.11 有关参考文献 527
第10章 数据抽象和面向对象 529
10.1 面向对象的程序设计 530
10.2 封装和继承 539
10.2.1 模块 539
10.2.2 类 542
10.2.3 类型扩展 544
10.3 初始化和终结处理 546
10.3.1 构造函数的选择 547
10.3.2 引用和值 550
10.3.3 执行顺序 551
10.3.4 废料收集 553
10.4 动态方法约束 554
10.4.1 虚函数和非虚函数 555
10.4.2 抽象类 557
10.4.3 成员查找 557
10.4.4 相关概念 561
10.5 多重继承 564
10.5.1 语义歧义性 568
10.5.2 复本式继承 570
10.5.3 共享继承 572
10.5.4 混入式继承 573
10.6 重温面向对象的程序设计 574
10.6.1 Smalltalk的对象模型 577
10.7 总结和注记 580
10.8 复习 582
10.9 练习 583
10.10 有关参考文献 586
第11章 非命令式程序设计模型：函数式和逻辑式语言 589
11.1 历史渊源 590
11.2 函数式程序设计 592
11.2.1 Scheme简介 594
11.2.2 重温求值顺序 604
11.2.3 高阶函数 609
11.2.4 理论基础 612
11.2.5 函数式程序设计展望 622
11.3 逻辑式程序设计 624
11.3.1 Prolog 625
11.3.2 理论基础 641
11.3.3 逻辑式程序设计的展望 646
11.4 总结和注记 648
11.5 复习 650
11.6 练习 651
11.7 有关参考文献 657
第12章 并发 659
12.1 基础和动力 660
12.1.1 简单历史 660
12.1.2 多线程程序的不同情况 663
12.1.3 多处理器体系结构 667
12.2 并发程序设计基础 670
12.2.1 通信和同步 671
12.2.2 语言和库 672
12.2.3 创建线程的语法 673
12.2.4 线程的实现 682
12.3 共享存储器 687
12.3.1 忙等待同步 688
12.3.2 调度器的实现 692
12.3.3 基于调度的同步 694
12.3.4 隐式同步 703
12.4 消息传递 706
12.4.1 通信对方的命名 706
12.4.2 传送 710
12.4.3 接收 714
12.4.4 远程过程调用 719
12.5 总结和注记 722
12.6 复习 724
12.7 练习 725
12.8 有关参考文献 730
第13章 代码改进 733
13.1 代码优化的阶段 735
13.2 窥孔优化 737
13.3 基本块内的冗余删除 740
13.4 全局冗余删除和数据流分析 745
13.4.1 静态单赋值形式和全局值编号 746
13.4.2 全局公共子表达式删除 750
13.5 循环改进 I 755
13.5.1 循环不变量 755
13.5.2 归纳变量 756
13.6 指令调度 759
13.7 循环改进 II 763
13.7.1 循环展开和软件流水线 763
13.7.2 循环重排 767
13.8 寄存器分配 775
13.9 总结和注记 778
13.10 复习 780
13.11 练习 781
13.12 有关参考文献 785
附录A 本书中提到的程序设计语言 787
附录B 语言设计和语言实现 795
参考书目 801
索引 827