第1部分  基础.................................................................................... 1

第1章  引  言.. 3

1.1  语言设计的艺术... 5

1.2  程序设计语言的谱系... 8

1.3  为什么研究程序设计语言... 11

1.4  编译和解释... 13

1.5  程序设计环境... 21

1.6  编译概览... 22

1.6.1  词法和语法分析... 23

1.6.2  语义分析和中间代码生成... 25

1.6.3  目标代码生成... 28

1.6.4  代码改进... 30

1.7  总结和注记... 31

1.8  练习... 32

1.9  探索... 33

1.10  有关参考文献... 35

第2章  程序设计语言的语法.. 37

2.1  描述语法：正则表达式和上下文无关文法... 38

2.1.1  单词和正则表达式... 39

2.1.2  上下文无关文法... 42

2.1.3  推导和语法分析树... 43

2.2  扫描... 46

2.2.1  生成一个自动机... 49

2.2.2  扫描器代码... 54

2.2.3  表驱动扫描... 58

2.2.4  词法错误... 58

2.2.5  有意义的注释... 60

2.3  语法分析... 61

2.3.1  递归下降... 64

2.3.2  表格驱动的自上而下语法分析... 70

2.3.3  自下而上的语法分析... 80

2.3.4  语法错误... CD 1·93

2.4  理论基础... CD 13·94

2.4.1  有穷自动机.................................................................................. CD 13

2.4.2  下推自动机.................................................................................. CD 16

2.4.3  文法和语言类.............................................................................. CD 17

2.5  总结和注记... 95

2.6  练习... 96

2.7  探索... 101

2.8  有关参考文献... 101

第3章  名字、作用域和约束.. 103

3.1  约束时间的概念... 104

3.2  对象生存期和存储管理... 106

3.2.1  静态分配... 107

3.2.2  基于栈的分配... 109

3.2.3  堆分配... 111

3.2.4  废料收集... 113

3.3  作用域规则... 114

3.3.1  静态作用域... 115

3.3.2  嵌套子程序... 117

3.3.3  声明的顺序... 119

3.3.4  模块... 124

3.3.5  模块类型和类... 128

3.3.6  动态作用域... 131

3.4  作用域的实现... CD 23·135

3.4.1  符号表........................................................................................ CD 23

3.4.2  关联表和中心引用表................................................................ CD 27

3.5  引用环境的约束... 136

3.5.1  子程序闭包... 138

3.5.2  一级和二级子程序... 140

3.6  作用域里的约束... 142

3.6.1  别名... 142

3.6.2  重载... 143

3.6.3  多态性及相关概念... 145

3.7  分别编译... CD 30·149

3.7.1  C的分别编译............................................................................ CD 30

3.7.2  包和自动头文件推理................................................................ CD 33

3.7.3  模块分层结构............................................................................ CD 35

3.8  总结和注记... 149

3.9  练习... 151

3.10  探索... 157

3.11  有关参考文献... 158

第4章  语义分析.. 161

4.1  语义分析器所扮演的角色... 162

4.2  属性文法... 166

4.3  属性求值... 168

4.4  动作例程... 179

4.5  属性的空间管理... CD 39·181

4.5.1  自下而上求值............................................................................ CD 39

4.5.2  自上而下求值............................................................................ CD 44

4.6  语法树的标注... 182

4.7  总结和注记... 187

4.8  练习... 189

4.9  探索... 193

4.10  有关参考文献... 194

第5章  目标机体系结构.. 195

5.1  存储器层次结构... 196

5.2  数据表示... 199

5.2.1  计算机算术... CD 54·199

5.3  指令集体系结构... 201

5.3.1  寻址模式... 201

5.3.2  条件分支... 202

5.4  体系结构和实现... 204

5.4.1  微程序设计... 205

5.4.2  微处理器... 206

5.4.3  RISC.. 207

5.4.4  两个实例体系结构：x86和MIPS. CD 59·208

5.4.5  伪汇编记法形式... 209

5.5  为新型处理器做编译... 210

5.5.1  维持流水线满... 211

5.5.2  寄存器分配... 216

5.6  总结和注记... 221

5.7  练习... 223

5.8  探索... 226

5.9  有关参考文献... 227

第2部分  语言设计的核心问题....................................................... 231

第6章  控制流.. 233

6.1  表达式求值... 234

6.1.1  优先级和结合性... 236

6.1.2  赋值... 238

6.1.3  初始化... 246

6.1.4  表达式里的顺序问题... 249

6.1.5  短路求值... 252

6.2  结构化和非结构化的流程... 254

6.2.1  goto的结构化替代品... 255

6.2.2  继续... 259

6.3  顺序复合... 260

6.4  选择... 261

6.4.1  短路条件... 262

6.4.2  case/switch语句... 265

6.5  迭代... 270

6.5.1  枚举控制的循环... 271

6.5.2  组合循环... 277

6.5.3  迭代器... 278

6.5.4  Icon的生成器... CD 69·284

6.5.5  逻辑控制的循环... 284

6.6  递归... 287

6.6.1  迭代和递归... 287

6.6.2  应用序和正则序求值... 291

6.7  非确定性... CD 72·295

6.8  总结和注记... 296

6.9  练习... 298

6.10  探索... 304

6.11  有关参考文献... 305

第7章  数据类型.. 307

7.1  类型系统... 308

7.1.1  类型检查... 309

7.1.2  多态性... 309

7.1.3  类型的定义... 311

7.1.4  类型的分类... 312

7.1.5  正交性... 319

7.2  类型检查... 321

7.2.1  类型等价... 321

7.2.2  类型相容... 327

7.2.3  类型推理... 332

7.2.4  ML的类型系统... CD 81·335

7.3  记录（结构）与变体（联合）... 336

7.3.1  语法和操作... 337

7.3.2  存储布局和紧缩... 338

7.3.3  with语句... CD 90·341

7.3.4  变体记录... 341

7.4  数组... 349

7.4.1  语法和操作... 349

7.4.2  维数、上下界和分配... 353

7.4.3  存储布局... 358

7.5  字符串... 366

7.6  集合... 367

7.7  指针和递归类型... 369

7.7.1  语法和操作... 370

7.7.2  悬空引用... 379

7.7.3  废料收集... 383

7.8  表... 389

7.9  文件和输入/输出... CD 93·392

7.9.1  交互式I/O.................................................................................. CD 93

7.9.2  基于文件的I/O.......................................................................... CD 94

7.9.3  正文I/O...................................................................................... CD 96

7.10  相等检测和赋值... 393

7.11  总结和注记... 395

7.12  练习... 398

7.13  探索... 404

7.14  有关参考文献... 405

第8章  子程序和控制抽象.. 407

8.1  重温栈布局... 408

8.2  调用序列... 410

8.2.1  区头向量... CD 107·413

8.2.2  实例研究：在MIPS上实现C，在x86上实现Pascal CD 111·414

8.2.3  寄存器窗口... CD 119·414

8.2.4  在线展开... 415

8.3  参数传递... 417

8.3.1  参数模式... 418

8.3.2  名字调用... CD 122·426

8.3.3  专用的参数... 427

8.3.4  函数返回... 432

8.4  泛型过程和模块... 434

8.4.1  不同的实现方法... 435

8.4.2  泛型参数的约束条件... 437

8.4.3  隐式实例化... 440

8.4.4  C++、Java和C# 的泛型... CD 125·440

8.5  异常处理... 441

8.5.1  异常的定义... 443

8.5.2  异常的传播... 445

8.5.3  实例：递归下降语法分析中的短语层恢复... 448

8.5.4  异常的实现... 449

8.6  协作程序... 453

8.6.1  栈分配... 455

8.6.2  转移... 457

8.6.3  迭代器... CD 135·458

8.6.4  离散事件模拟... CD 139·458

8.7  总结和注记... 459

8.8  练习... 460

8.9  探索... 466

8.10  有关参考文献... 467

第9章  数据抽象和面向对象.. 469

9.1  面向对象的程序设计... 471

9.2  封装和继承... 481

9.2.1  模块... 481

9.2.2  类... 484

9.2.3  类型扩展... 486

9.3  初始化和终结处理... 489

9.3.1  构造函数的选择... 490

9.3.2  引用和值... 491

9.3.3  执行顺序... 495

9.3.4  废料收集... 496

9.4  动态方法约束... 497

9.4.1  虚方法和非虚方法... 500

9.4.2  抽象类... 501

9.4.3  成员查找... 502

9.4.4  多态性... 505

9.4.5  闭包... 508

9.5  多重继承... CD 146·511

9.5.1  语义歧义性.............................................................................. CD 148

9.5.2  复本式继承.............................................................................. CD 151

9.5.3  共享继承.................................................................................. CD 152

9.5.4  混入式继承.............................................................................. CD 154

9.6  重温面向对象的程序设计... 512

9.6.1  Smalltalk的对象模型... CD 158·513

9.7  总结和注记... 513

9.8  练习... 515

9.9  探索... 517

9.10  有关参考文献... 518

第3部分  其他程序设计模型........................................................... 521

第10章  函数式语言.. 523

10.1  历史渊源... 524

10.2  函数式程序设计的概念... 526

10.3  Scheme简介... 528

10.3.1  约束... 530

10.3.2  表和数... 531

10.3.3  相等检测和检索... 532

10.3.4  控制流和赋值... 533

10.3.5  程序作为表... 535

10.3.6  一个扩展的实例：DFA模拟... 537

10.4  重温求值顺序... 539

10.4.1  严格求值和惰性求值... 541

10.4.2  I/O：流和单体... 542

10.5  高阶函数... 545

10.6  理论基础... CD 166·549

10.6.1  Lambda演算.......................................................................... CD 168

10.6.2  控制流.................................................................................... CD 171

10.6.3  结构........................................................................................ CD 173

10.7  函数式程序设计展望... 549

10.8  总结和注记... 552

10.9  练习... 552

10.10  探索... 557

10.11  有关参考文献... 558

第11章  逻辑式语言.. 559

11.1  逻辑式程序设计的概念... 560

11.2  Prolog. 561

11.2.1  归结和合一... 563

11.2.2  表... 564

11.2.3  算术... 565

11.2.4  搜索/执行顺序... 566

11.2.5  一个较大的实例：九宫棋... 569

11.2.6  命令式控制流... 571

11.2.7  数据库操作... 574

11.3  理论基础... CD 180·579

11.3.1  子句形式................................................................................ CD 181

11.3.2  局限性.................................................................................... CD 182

11.3.3  Skolem化............................................................................... CD 183

11.4  逻辑式程序设计的展望... 579

11.4.1  没有覆盖的逻辑部分... 580

11.4.2  执行顺序... 580

11.4.3  否定和“闭世界”假设... 581

11.5  总结和注记... 583

11.6  练习... 584

11.7  探索... 586

11.8  有关参考文献... 587

第12章  并发.. 589

12.1  基础和动力... 590

12.1.1  简单历史... 590

12.1.2  多线程程序的不同情况... 593

12.1.3  多处理器体系结构... 597

12.2  并发程序设计基础... 601

12.2.1  通信和同步... 601

12.2.2  语言和库... 603

12.2.3  创建线程的语法... 604

12.2.4  线程的实现... 613

12.3  共享存储器... 619

12.3.1  忙等待同步... 620

12.3.2  调度器的实现... 623

12.3.3  信号量... 627

12.3.4  管程... 629

12.3.5  条件临界区域... 634

12.3.6  隐式同步... 638

12.4  消息传递... 642

12.4.1  通信对方的命名... 642

12.4.2  发送... 646

12.4.3  接收... 651

12.4.4  远程过程调用... 656

12.5  总结和注记... 660

12.6  练习... 662

12.7  探索... 668

12.8  有关参考文献... 669

第13章  脚本语言.. 671

13.1  什么是脚本语言... 672

13.1.1  公共特性... 674

13.2  问题领域... 677

13.2.1  外壳（命令）语言... 677

13.2.2  文字处理和报表生成... 684

13.2.3  数学和统计... 689

13.2.4  “粘结”语言和通用脚本... 690

13.2.5  扩充语言... 698

13.3  万维网脚本... 701

13.3.1  CGI脚本... 702

13.3.2  嵌入式服务器端脚本... 703

13.3.3  客户端脚本... 708

13.3.4  Java小程序... 708

13.3.5  XSLT. 712

13.4  新特征... 722

13.4.1  名字和作用域... 723

13.4.2  串和模式匹配... 728

13.4.3  数据类型... 736

13.4.4  面向对象... 741

13.5  总结和注记... 748

13.6  练习... 750

13.7  探索... 755

13.8  有关参考文献... 756

第4部分  对实现的近距离考查....................................................... 759

第14章  构造可运行程序.. 761

14.1  后端编译器结构... 761

14.1.1  一种可行的多阶段组织... 762

14.1.2  阶段和遍... 766

14.2  中间形式... CD 189·766

14.2.1  Diana....................................................................................... CD 189

14.2.2  GNU的RTL.......................................................................... CD 192

14.3  代码生成... 769

14.3.1  一个属性文法实例... 769

14.3.2  寄存器分配... 772

14.4  地址空间组织... 775

14.5  汇编... 776

14.5.1  指令发射... 778

14.5.2  为名字指定地址... 780

14.6  连接... 781

14.6.1  重定位和名字解析... 782

14.6.2  类型检查... 783

14.7  动态连接... CD 195·784

14.7.1  与定位无关的代码................................................................ CD 195

14.7.2  完全动态连接（惰性连接）................................................ CD 196

14.8  总结和注记... 786

14.9  练习... 787

14.10  探索... 789

14.11  有关参考文献... 790

第15章  代码改进... CD 202·791

15.1  代码优化阶段.... CD 204

15.2  窥孔优化.... CD 206

15.3  基本块内的冗余删除.... CD 209

15.3.1  一直使用的实例... CD 210

15.3.2  值编号... CD 211

15.4  全局冗余删除和数据流分析.... CD 217

15.4.1  SSA（静态单赋值形式）和全局值编号... CD 218

15.4.2  全局公共子表达式删除... CD 220

15.5  循环改进I CD 227

15.5.1  循环不变量... CD 228

15.5.2  归纳变量... CD 229

15.6  指令调度... CD 232

15.7  循环改进II CD 236

15.7.1  循环展开和软件流水线... CD 237

15.7.2  循环重排... CD 241

15.8  寄存器分配... CD 248

15.9  总结和注记... CD 252

15.10  练习... CD 253

15.11  探索... CD 257

15.12  有关参考文献... CD 258

附录A  本书中提到的程序设计语言................................................... 793

附录B  语言设计和语言实现............................................................ 803

附录C  编号示例表......................................................................... 807

参考书目......................................................................................... 819

索引............................................................................................... 837