程序设计语言 实践之路

第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.1 重定位和名字解析 515

9.6 连接 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.1 简单历史 660

12.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 循环改进Ⅰ 755

13.5.1 循环不变量 755

13.5.2 归纳变量 756

13.6 指令调度 759

13.7 循环改进Ⅱ 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