第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
· · · · · · (收起)