第1章 概论 1
1.1 原理 2
1.2 范例 3
1.3 专题 5
1.4 编程语言发展简史 5
1.5 关于语言设计 10
1.5.1 设计约束 11
1.5.2 结果和目标 13
1.6 编译器和虚拟机 17
1.7 小结 19
1.8 练习 19
第2章 语法 21
2.1 文法 22
2.1.1 BNF文法 22
2.1.2 推导 24
2.1.3 语法分析树 25
2.1.4 结合性和优先级 27
2.1.5 歧义性文法 29
2.2 BNF扩展 32
2.3 小语言CLITE的语法 34
2.3.1 词法 36
2.3.2 具体语法 37
2.4 编译器和解释器 41
2.5 语法和语义学链接 44
2.5.1 抽象语法 45
2.5.2 抽象语法树 47
2.5.3 Clite的抽象语法 48
2.6 小结 50
2.7 练习 51
第3章 词法和语法分析 55
3.1 Chomsky层次结构 55
3.2 词法分析 58
3.2.1 正则表达式 59
3.2.2 有穷状态机 61
3.2.3 从设计到代码 64
3.3 语法分析 68
3.3.1 基本定义 69
3.3.2 递归下降分析 73
3.4 小结 79
3.5 练习 79
第4章 命名 83
4.1 语法问题 84
4.2 变量 85
4.3 作用域 87
4.4 符号表 89
4.5 解析引用 90
4.6 动态作用域 92
4.7 可见性 93
4.8 重载 94
4.9 生存期 96
4.10 小结 97
4.11 练习 97
第5章 类型 99
5.1 类型错误 100
5.2 静态类型和动态类型 101
5.3 基本类型 102
5.4 非基本类型 110
5.4.1 枚举 110
5.4.2 指针 111
5.4.3 数组和列表 112
5.4.4 串 117
5.4.5 结构体 118
5.4.6 变体记录和共用体 119
5.5 递归数据类型 121
5.6 作为类型的函数 122
5.7 类型等价 123
5.8 子类型 124
5.9 多态和通用类 125
5.10 自定义类型 129
5.11 小结 130
5.12 练习 130
第6章 类型系统 133
6.1 Clite的类型系统 135
6.2 隐式类型转换 142
6.3 规范Clite类型系统 146
6.4 小结 149
6.5 练习 149
第7章 语义 151
7.1 动机 151
7.2 表达式语义 153
7.2.1 表示法 153
7.2.2 结合律和优先级 154
7.2.3 短循环求值 156
7.2.4 表达式的意义 157
7.3 程序状态 158
7.4 赋值语义 160
7.4.1 多重赋值 160
7.4.2 赋值语句与赋值表达式 160
7.4.3 语义的引用和复制 161
7.5 流程控制语义 161
7.5.1 顺序执行语句 162
7.5.2 条件语句 162
7.5.3 循环语句 164
7.5.4 GoTo争议 165
7.6 输入／输出语句 167
7.6.1 基本概念 167
7.6.2 随机访问文件 172
7.6.3 I/O错误处理语义 175
7.7 异常处理语义 177
7.7.1 策略和设计理念 178
7.7.2 Ada、C＋＋和Java中的异常处理 180
7.7.3 异常和断言 188
7.8 小结 192
7.9 练习 192
第8章 语义解释 195
8.1 状态转换和局部函数 195
8.2 Clite语义 196
8.2.1 程序的意义 197
8.2.2 语句的语义 198
8.2.3 表达式语义 202
8.2.4 表达式的副作用 206
8.3 动态类型语义 207
8.4 语义的规范化处理 211
8.4.1 状态和状态转换 212
8.4.2 程序的表示型语义 213
8.4.3 语句的表示型语义 214
8.4.4 表达式的表示型语义 218
8.4.5 规范化语义模型的局限性 220
8.5 小结 220
8.6 练习 220
第9章 函数 225
9.1 基本术语 226
9.2 函数调用和返回 226
9.3 参数 227
9.4 参数传递机制 229
9.4.1 传值调用 229
9.4.2 按引用传递 231
9.4.3 值结果和结果传递 233
9.4.4 按名传递 234
9.4.5 Ada中的参数传递 236
9.5 活动记录 236
9.6 递归函数 237
9.7 运行时堆栈 239
9.8 小结 241
9.9 练习 242
第10章 函数实现 245
10.1 Clite中的函数声明与调用 245
10.1.1 具体句法 246
10.1.2 抽象句法 247
10.2 编译Clite类型系统 249
10.3 函数调用与返回的语义 251
10.3.1 非void函数 252
10.3.2 重访问的副作用 253
10.4 类型和语义的规范处理 254
10.4.1 Clite类型映射 254
10.4.2 规范化Clite类型规则 255
10.4.3 规范Clite语义 257
10.5 小结 262
10.6 练习 262
第11章 内存管理 265
11.1 堆 266
11.2 动态数组的实现 267
11.3 垃圾回收 270
11.3.1 引用计数 271
11.3.2 标记扫描 272
11.3.3 复制收集 275
11.3.4 策略优劣比较 277
11.4 小结 277
11.5 练习 278
第12章 命令式编程 279
12.1 命令式语言的产生 279
12.2 过程抽象 281
12.3 表达式和赋值 283
12.4 支持数据结构的库 284
12.5 命令式编程和C语言 286
12.5.1 一般特征 287
12.5.2 示例：Grep 288
12.5.3 示例：Average 290
12.5.4 示例：符号微分法 290
12.6 命令式编程和Ada语言 294
12.6.1 一般特征 295
12.6.2 示例：Average 297
12.6.3 示例：Matrix Multiplication 299
12.7 命令式编程和Perl语言 300
12.7.1 一般特性 301
12.7.2 示例：Grep 302
12.7.3 示例：Mailing Grades 305
12.8 小结 308
12.9 练习 309
第13章 面向对象编程 311
13.1 抽象数据类型 311
13.2 对象模型 317
13.2.1 类 317
13.2.2 可见性和信息隐藏 320
13.2.3 继承 321
13.2.4 多重继承 325
13.2.5 多态 326
13.2.6 模板 327
13.2.7 抽象类 328
13.2.8 接口 329
13.2.9 虚拟方法表 331
13.2.10 运行时类型标识 333
13.2.11 反射 333
13.3 Smalltalk 334
13.3.1 一般特性 335
13.3.2 示例：多项式 338
13.3.3 示例：复数 340
13.3.4 示例：银行账户 342
13.4 Java 343
13.4.1 示例：符号微分 343
13.4.2 示例：回溯 346
13.5 PYTHON 350
13.5.1 一般特性 353
13.5.2 示例：多项式 354
13.5.3 示例：分数 356
13.6 小结 358
13.7 练习 359
第14章 函数式编程 363
14.1 函数和λ演算 364
14.2 Scheme语言 368
14.2.1 表达式 368
14.2.2 表达式求值 369
14.2.3 列表 370
14.2.4 元素值 372
14.2.5 控制流 373
14.2.6 定义函数 373
14.2.7 let表达式 376
14.2.8 示例：Clite语义 378
14.2.9 示例：符号微分 382
14.2.10 示例：八皇后问题 384
14.3 Haskell语言 388
14.3.1 简介 389
14.3.2 表达式 390
14.3.3 列表及其产生 391
14.3.4 基本类型和值 394
14.3.5 控制流 394
14.3.6 定义函数 395
14.3.7 元组 398
14.3.8 示例：Clite语义 399
14.3.9 示例：符号微分 402
14.3.10 示例：八皇后问题 404
14.4 小结 406
14.5 练习 406
第15章 逻辑式编程 411
15.1 逻辑和horn语句 412
15.2 Prolog语言中的逻辑式编程 415
15.2.1 Prolog程序元素 415
15.2.2 Prolog语言的实际应用 423
15.3 Prolog程序示例 427
15.3.1 符号微分法 427
15.3.2 猜字谜 429
15.3.3 自然语言处理 430
15.3.4 Clite的语义 434
15.3.5 八皇后的问题 437
15.4 小结 439
15.5 练习 440
第16章 事件驱动编程 443
16.1 事件驱动控制 444
16.1.1 模型-视图-控制器 445
16.1.2 Java中的事件 446
16.1.3 Java GUI应用程序 448
16.2 事件处理 450
16.2.1 单击鼠标 450
16.2.2 鼠标移动 451
16.2.3 按钮 452
16.2.4 标签、文本域和文本框 453
16.2.5 组合框 455
16.3 3个示例 456
16.3.1 简单的GUI接口 456
16.3.2 设计Java Applet 462
16.3.3 基于事件驱动的交互式游戏 464
16.4 其他事件-驱动应用程序 472
16.4.1 ATM自动取款机 472
16.4.2 家庭保安系统 473
16.5 小结 475
16.6 练习 475
第17章 并发编程 479
17.1 并发的概念 480
17.1.1 历史和定义 481
17.1.2 线程控制与通信 482
17.1.3 竞争和死锁 483
17.2 同步策略 485
17.2.1 信标 485
17.2.2 监视器 487
17.3 Java中的同步 489
17.3.1 Java线程 489
17.3.2 示例 491
17.4 进程间通信 500
17.4.1 IP地址、端口和套接字 501
17.4.2 一个客户／服务器示例 502
17.5 其他语言中的并发 508
17.6 小结 510
17.7 练习 510
第18章 程序的正确性 513
18.1 公理语义 514
18.1.1 基本概念 515
18.1.2 赋值规则 518
18.1.3 推理规则 518
18.1.4 Max函数的正确性 519
18.1.5 循环程序的正确性 520
18.1.6 形式化方法的观点 523
18.2 形式化方法工具：JML 525
18.3 面向对象程序的正确性 532
18.3.1 按照契约设计 532
18.3.2 类常量 533
18.3.3 示例：堆栈应用的正确性 535
18.3.4 总结 540
18.4 函数程序的正确性 541
18.4.1 递归与归纳 541
18.4.2 结构化归纳示例 542
18.5 小结 544
18.6 练习 545
附录A Clite的定义 549
A.1 Clite词汇和具体句法 549
A.2 Clite的抽象句法 550
A.3 Clite的类型系统 551
A.4 Clite的语义 552
A.5 Clite的加法函数 554
A.5.1 词汇以及具体语法 554
A.5.2 抽象句法 555
A.5.3 类型系统 555
A.5.4 语义 556
附录B 离散数学回顾 557
B.1 集合和关系 557
B.2 视图 561
B.3 逻辑 562
B.4 推理规则和直接证明 566
B.5 归纳证明 568