第1部分 基础 3
第1章 引言 5
1.1语言设计的艺术 7
1.2程序设计语言的谱系 10
1.3为什么要研究程序设计语言？ 14
1.4编译和解释 16
1.5程序设计环境 24
1.6编译概览 25
1.6.1词法和语法分析 27
1.6.2语义分析和中间代码生成 29
1.6.3目标代码生成 33
1.6.4代码改进 33
1.7总结和注记 35
1.8练习 36
1.9探索 37
1.10有关参考文献 39
第2章 程序设计语言的语法 41
2.1描述语法：正则表达式和上下文无关文法 42
2.1.1单词和正则表达式 43
2.1.2上下文无关文法 46
2.1.3推导和语法分析树 48
2.2扫描 51
2.2.1生成一个有穷自动机 55
2.2.2扫描器代码 60
2.2.3表格驱动的扫描 63
2.2.4词法错误 63
2.2.5编译指示 65
2.3语法分析 67
2.3.1递归下降 70
2.3.2表格驱动的自上而下语法分析 76
2.3.3自下而上的语法分析 87
2.3.4语法错误 99
2.4理论基础 100
2.4.1有穷自动机 100
2.4.2下推自动机 100
2.4.3文法和语言类 100
2.5总结和注记 101
2.6练习 102
2.7探索 108
2.8有关参考文献 109
第3章 名字、作用域和约束 111
3.1约束时间的概念 112
3.2对象生存期和存储管理 114
3.2.1静态分配 115
3.2.2基于栈的分配 117
3.2.3基于堆的分配 118
3.2.4废料收集 120
3.3作用域规则 121
3.3.1静态作用域 123
3.3.2嵌套子程序 124
3.3.3声明的顺序 127
3.3.4模块 132
3.3.5模块类型和类 136
3.3.6动态作用域 139
3.4作用域的实现 143
3.4.1符号表 143
3.4.2关联表和中心引用表 143
3.5作用域中名字的含义 144
3.5.1别名 144
3.5.2重载 146
3.5.3多态性及相关概念 148
3.6引用环境的约束 151
3.6.1子程序闭包 153
3.6.2一级值和非受限生存期 154
3.6.3对象闭包 157
3.7宏扩展 159
3.8分别编译 161
3.8.1 C的分别编译 161
3.8.2包和自动头文件推理 161
3.8.3模块分层结构 161
3.9总结和注记 162
3.10练习 163
3.11探索 171
3.12有关参考文献 172
第4章 语义分析 175
4.1语义分析器所扮演的角色 176
4.2属性文法 180
4.3属性求值 182
4.4动作例程 191
4.5属性的空间管理 196
4.5.1自下而上求值 196
4.5.2自上而下求值 196
4.6语法树的标注 197
4.7总结和注记 204
4.8练习 205
4.9探索 209
4.10有关参考文献 210
第5章 目标机体系结构 213
5.1存储器层次结构 213
5.2数据表示 213
5.2.1整数算术 213
5.2.2浮点数算术 213
5.3指令集体系结构 213
5.3.1寻址模式 213
5.3.2条件和分支 213
5.4体系结构和实现 213
5.4.1微程序设计 213
5.4.2微处理器 213
5.4.3 RISC 213
5.4.4多线程和多核 213
5.4.5两个示例体系结构：x86和MIPS 213
5.5为新型处理器做编译 213
5.5.1保持流水线满 213
5.5.2寄存器分配 213
5.6总结和注记 213
5.7练习 213
5.8探索 213
5.9有关参考文献 213
第2部分 语言设计的核心问题 217
第6章 控制流 219
6.1表达式求值 220
6.1.1优先级和结合性 222
6.1.2赋值 224
6.1.3初始化 233
6.1.4表达式中的顺序问题 235
6.1.5短路求值 238
6.2结构化和非结构化的流程 241
6.2.1 goto的结构化替代品 242
6.2.2继续 245
6.3顺序执行 246
6.4选择 247
6.4.1短路条件 248
6.4.2 Case/Switch语句 251
6.5迭代 256
6.5.1枚举控制的循环 256
6.5.2组合循环 261
6.5.3迭代器 262
6.5.4 Icon的生成器 268
6.5.5逻辑控制的循环 268
6.6递归 270
6.6.1迭代和递归 271
6.6.2应用序和正则序求值 275
6.7非确定性 277
6.8总结和注记 278
6.9练习 279
6.10探索 285
6.11有关参考文献 287
第7章 数据类型 289
7.1类型系统 290
7.1.1类型检查 291
7.1.2多态性 291
7.1.3“类型”的含义 293
7.1.4类型的分类 294
7.1.5正交性 301
7.2类型检查 303
7.2.1类型等价 303
7.2.2类型相容性 310
7.2.3类型推理 314
7.2.4 ML类型系统 316
7.3记录（结构）与变体（联合） 317
7.3.1语法和运算 318
7.3.2存储布局及其影响 319
7.3.3 with语句 323
7.3.4变体记录（联合） 324
7.4数组 325
7.4.1语法和操作 326
7.4.2维数、上下界和分配 330
7.4.3内存布局 335
7.5字符串 342
7.6集合 344
7.7指针和递归类型 345
7.7.1语法和操作 346
7.7.2悬空引用 356
7.7.3废料收集 357
7.8表 364
7.9文件和输入/输出 367
7.9.1交互式I/O 367
7.9.2基于文件的I/O 367
7.9.3正文I/O 367
7.10相等检测和赋值 368
7.11总结和注记 371
7.12练习 373
7.13探索 379
7.14有关参考文献 380
第8章 子程序和控制抽象 383
8.1回顾栈的布局 384
8.2调用序列 386
8.2.1区头向量 389
8.2.2案例研究：在MIS上实现C，在x86上实现Pascal 389
8.2.3寄存器窗口 390
8.2.4内联展开 391
8.3参数传递 393
8.3.1参数模式 394
8.3.2名字调用 402
8.3.3特殊目的的参数 403
8.3.4函数返回 408
8.4泛型子程序和模块 410
8.4.1不同的实现方法 412
8.4.2泛型参数的约束条件 414
8.4.3隐式实例化 416
8.4.4 C++、Java和C#中的泛型 417
8.5异常处理 418
8.5.1异常的定义 421
8.5.2异常的传播 423
8.5.3异常的实现 425
8.6协作程序 428
8.6.1栈分配 430
8.6.2转移 432
8.6.3迭代器的实现 433
8.6.4离散事件模拟 433
8.7事件 434
8.7.1顺序处理程序 434
8.7.2基于线程的处理程序 436
8.8总结和注记 438
8.9练习 439
8.10探索 446
8.11有关参考文献 447
第9章 数据抽象和面向对象 449
9.1面向对象程序设计 451
9.2封装和继承 460
9.2.1模块 460
9.2.2类 463
9.2.3嵌套（内层类） 465
9.2.4类型扩展 466
9.2.5不使用继承扩展 468
9.3初始化和终结处理 469
9.3.1构造函数的选择 470
9.3.2引用和值 472
9.3.3执行顺序 475
9.3.4废料收集 477
9.4动态方法约束 478
9.4.1虚方法和非虚方法 480
9.4.2抽象类 482
9.4.3成员查找 482
9.4.4多态性 486
9.4.5对象闭包 489
9.5多重继承 491
9.5.1语义歧义性 491
9.5.2复本式继承 491
9.5.3共享继承 491
9.5.4混入式继承 491
9.6重温面向对象的程序设计 492
9.6.1 Smalltalk的对象模型 493
9.7总结和注记 494
9.8练习 495
9.9探索 498
9.10有关参考文献 499
第3部分 其他程序设计模型 503
第10章 函数式语言 505
10.1历史渊源 506
10.2函数式程序设计的概念 507
10.3 Scheme回顾/简介 509
10.3.1约束 512
10.3.2表和数 513
10.3.3相等检测和检索 514
10.3.4控制流和赋值 515
10.3.5程序作为表 517
10.3.6一个扩展的实例：DFA模拟 519
10.4重温求值顺序 521
10.4.1严格求值和惰性求值 523
10.4.2 I/O：流和单体 525
10.5高阶函数 530
10.6理论基础 534
10.6.1 lambda演算 534
10.6.2控制流 534
10.6.3结构 534
10.7函数式程序设计展望 534
10.8总结和注记 537
10.9练习 538
10.10探索 542
10.11有关参考文献 543
第11章 逻辑式语言 545
11.1逻辑式程序设计的概念 546
11.2 Prolog 547
11.2.1归结和合一 549
11.2.2表 550
11.2.3算术 551
11.2.4搜索/执行顺序 552
11.2.5一个较大的实例：九宫棋 554
11.2.6命令式控制流 557
11.3理论基础 566
11.3.1子句形式 566
11.3.2局限性 566
11.3.3 Skolem 566
11.4逻辑式程序设计的展望 566
11.4.1没有覆盖的逻辑部分 566
11.4.2执行顺序 567
11.4.3否定和“闭世界”假设 568
11.5总结和注记 570
11.6练习 571
11.7探索 573
11.8有关参考文献 573
第12章 并发 575
12.1基础和动力 576
12.1.1多线程程序的各种情况 579
12.1.2多处理器体系结构 581
12.2并发程序设计基础 586
12.2.1通信和同步 587
12.2.2语言和库 588
12.2.3创建线程的语法 589
12.2.4线程的实现 598
12.3实现 603
12.3.1忙等待同步 604
12.3.2非阻塞算法 607
12.3.3内存一致模型 610
12.3.4调度器的实现 613
12.3.5信号量 617
12.4语言级机制 619
12.4.1管程 619
12.4.2条件临界区域 624
12.4.3 Java中的同步 626
12.4.4事务存储 629
12.4.5隐式同步 633
12.5消息传递 637
12.5.1通信对方的命名 637
12.5.2发送 637
12.5.3接收 637
12.5.4远程过程调用 637
12.6 总结和注记 638
12.7练习 640
12.8探索 645
12.9有关参考文献 647
第13章 脚本语言 649
13.1什么是脚本语言？ 650
13.1.1公共特性 652
13.2问题领域 655
13.2.1外壳（命令）语言 655
13.2.2文字处理和报表生成 663
13.2.3数学和统计 667
13.2.4“粘结”语言和通用脚本 668
13.2.5扩充语言 676
13.3万维网脚本 680
13.3.1 CGI脚本 680
13.3.2嵌入式服务器端脚本 681
13.3.3客户端脚本 686
13.3.4 Java小程序 686
13.3.5 XSLT 689
13.4新特征 691
13.4.1名字和作用域 691
13.4.2串和模式匹配 696
13.4.3数据类型 704
13.4.4面向对象 710
13.5总结和注记 717
13.6练习 718
13.7探索 723
13.8有关参考文献 724
第4部分 对实现的近距离考查 727
第14章 构造可运行的程序 729
14.1后端编译器结构 729
14.1.1一种可行的多阶段组织 730
14.1.2阶段和遍 734
14.2中间形式 734
14.2.1 Diana 734
14.2.2 gcc中间形式 734
14.2.3基于栈的中间形式 736
14.3代码生成 738
14.3.1一个属性文法实例 738
14.3.2寄存器分配 741
14.4地址空间组织 744
14.5汇编 746
14.5.1指令发射 748
14.5.2为名字指定地址 749
14.6连接 750
14.6.1重定位和名字解析 751
14.6.2类型检查 751
14.7动态连接 754
14.7.1与定位无关的代码 754
14.7.2完全动态连接（惰性连接） 754
14.8总结和注记 755
14.9练习 756
14.10探索 758
14.11有关参考文献 759
第15章 运行时程序管理 761
15.1虚拟机 764
15.1.1 Java虚拟机 766
15.1.2公共语言基础架构 775
15.2机器码的迟绑定 784
15.2.1即时和动态编译 785
15.2.2二进制翻译 791
15.2.3二进制重写 795
15.2.4移动代码和沙箱 797
15.3审查/自反 799
15.3.1自反 799
15.3.2符号调试 806
15.3.3性能分析 809
15.4总结和注记 811
15.5练习 812
15.6探索 815
15.7有关参考文献 816
第16章 代码改进 817
16.1代码改进的阶段 817
16.2窥孔优化 817
16.3基本块内的冗余删除 817
16.3.1一直使用的实例 817
16.3.2值编号 817
16.4全局冗余删除和数据流分析 817
16.4.1 SSA（静态单赋值）形式和全局值编号 817
16.4.2全局公共子表达式删除 817
16.5循环改进Ⅰ 817
16.5.1循环不变量 817
16.5.2归纳变量 817
16.6指令调度 817
16.7循环改进Ⅱ 817
16.7.1循环展开和软件流水线 817
16.7.2循环重排 817
16.8寄存器分配 817
16.9总结和注记 817
16.10练习 817
16.11探索 817
16.12有关参考文献 817
附录A 本书中提到的程序设计语言 819
附录B 语言设计和语言实现 831
附录C 编号示表 835