程序設(shè)計(jì)語言：實(shí)踐之路

前言 xvii
第1章 引言 1
1.1 語言設(shè)計(jì)的藝術(shù) 3
1.2 程序設(shè)計(jì)語言的譜系 5
1.3 為什么研究程序設(shè)計(jì)語言 7
1.4 編譯和解釋 9
1.5 程序設(shè)計(jì)環(huán)境 14
1.6 編譯概覽 15
1.6.1 詞法和語法分析 16
1.6.2 語義分析和中間代碼生成 18
1.6.3 目標(biāo)代碼生成 22
1.6.4 代碼改進(jìn) 24
1.7 總結(jié)和注記 24
1.8 復(fù)習(xí) 25
1.9 練習(xí) 26
1.10 有關(guān)參考文獻(xiàn) 28
第2章 程序設(shè)計(jì)語言的語法 31
2.1 描述語法：正則表達(dá)式和上下文無關(guān)文法 32
2.1.1 單詞和正則表達(dá)式 33
2.1.2 上下文無關(guān)文法 34
2.1.3 推導(dǎo)和語法分析樹 36
2.2 識別語法：掃描器和語法分析器 39
2.2.1 掃描 40
2.2.2 自上而下和自下而上的語法分析 48
2.2.3 遞歸下降 51
2.2.4 語法錯(cuò)誤 57
2.2.5 表格驅(qū)動(dòng)的自上而下語法分析 62
2.2.6 自下而上的語法分析 75
2.3* 理論基礎(chǔ) 87
2.3.1 有窮自動(dòng)機(jī) 88
2.3.2 下推自動(dòng)機(jī) 92
2.3.3 文法和語言類 93
2.4 總結(jié)和注記 94
2.5 復(fù)習(xí) 97
2.6 練習(xí) 98
2.7 有關(guān)參考文獻(xiàn) 102
第3章 名字、作用域和約束 105
3.1 約束時(shí)間的概念 106
3.2 對象生存期和存儲管理 108
3.2.1 基于堆棧的分配 111
3.2.2 堆分配 113
3.2.3 廢料收集 114
3.3 作用域規(guī)則 115
3.3.1 靜態(tài)作用域 116
3.3.2 動(dòng)態(tài)作用域 129
3.3.3 符號表 132
3.3.4 關(guān)聯(lián)表和中心引用表列 137
3.4 引用環(huán)境的約束 139
3.4.1 子程序閉包 141
3.4.2 一級和二級子程序 143
3.5 重載和相關(guān)概念 144
3.6 語言設(shè)計(jì)中與名字有關(guān)的缺陷 149
3.6.1 作用域規(guī)則 149
3.6.2 分別編譯 151
3.7 總結(jié)和注記 155
3.8 復(fù)習(xí) 157
3.9 練習(xí) 158
3.10 有關(guān)參考文獻(xiàn) 162
第4章 語義分析 165
4.1 語義分析器所扮演的角色 166
4.2 屬性文法 168
4.3 屬性流 170
4.4 動(dòng)作例程 179
4.5 屬性的空間管理 180
4.5.1 自下而上求值 181
4.5.2 自上而下求值 186
4.6 語法樹的標(biāo)注 191
4.7 總結(jié)和注記 197
4.8 復(fù)習(xí) 198
4.9 練習(xí) 199
4.10 有關(guān)參考文獻(xiàn) 202
第5章 匯編層計(jì)算機(jī)體系結(jié)構(gòu) 203
5.1 工作站的微體系結(jié)構(gòu) 204
5.2 存儲器層次結(jié)構(gòu) 207
5.3 數(shù)據(jù)表示 209
5.3.1 整數(shù)算術(shù) 211
5.3.2 浮點(diǎn)算術(shù) 212
5.4 指令集的體系結(jié)構(gòu) 214
5.4.1 尋址模式 215
5.4.2 條件分支 217
5.5 處理器體系結(jié)構(gòu)的演化 218
5.5.1 兩個(gè)實(shí)例體系結(jié)構(gòu)：680x0和MIPS 220
5.5.2 偽匯編記法形式 225
5.6 為新型處理器做編譯 227
5.6.1 維持流水線滿 227
5.6.2 寄存器分配 234
5.7 總結(jié)和注記 242
5.8 復(fù)習(xí) 243
5.9 練習(xí) 244
5.10 有關(guān)參考文獻(xiàn) 247
第6章 控制流 249
6.1 表達(dá)式求值 250
6.1.1 優(yōu)先級和結(jié)合性 251
6.1.2 賦值 254
6.1.3 表達(dá)式里的順序 262
6.1.4 短路求值 265
6.2 結(jié)構(gòu)化和非結(jié)構(gòu)化的流程 267
6.3 順序復(fù)合 270
6.4 選擇 271
6.4.1 短路條件 272
6.4.2 分情況/開關(guān)語句 275
6.5 迭代 280
6.5.1 枚舉控制的循環(huán) 280
6.5.2 組合循環(huán) 286
6.5.3 迭代器 287
6.5.4 邏輯控制的循環(huán) 294
6.6 遞歸 297
6.6.1 迭代和遞歸 297
6.6.2 應(yīng)用序和正則序求值 301
6.7 非確定性 303
6.8 總結(jié)和注記 308
6.9 復(fù)習(xí) 310
6.10 練習(xí) 311
6.11 有關(guān)參考文獻(xiàn) 316
第7章 數(shù)據(jù)類型 319
7.1 類型系統(tǒng) 320
7.1.1 類型的定義 322
7.1.2 類型的分類 323
7.2 類型檢查 330
7.2.1 類型等價(jià) 330
7.2.2 類型變換和轉(zhuǎn)換 334
7.2.3 類型相容和強(qiáng)制 337
7.2.4 類型推理 341
7.2.5 ML的類型系統(tǒng) 344
7.3 記錄（結(jié)構(gòu)）與變體（聯(lián)合） 351
7.3.1 語法和操作 351
7.3.2 存儲布局和緊縮 353
7.3.3 With語句 355
7.3.4 變體記錄 358
7.4 數(shù)組 365
7.4.1 語法和操作 365
7.4.2 維數(shù)、上下界和分配 369
7.4.3 數(shù)組的布局 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 總結(jié)和注記 416
7.12 復(fù)習(xí) 418
7.13 練習(xí) 420
7.14 有關(guān)參考文獻(xiàn) 425
第8章 子程序和控制抽象 427
8.1 重溫堆棧布局 428
8.2 調(diào)用序列 431
8.2.1 實(shí)例研究：在MIPS上實(shí)現(xiàn)C 434
8.2.2 實(shí)例研究：在680x0上實(shí)現(xiàn)Pascal 437
8.2.3 在線展開 441
8.3 參數(shù)傳遞 442
8.3.1 參數(shù)模式 443
8.3.2 專用的參數(shù) 453
8.3.3 函數(shù)返回 457
8.4 通用型過程和模塊 459
8.5 異常處理 464
8.5.1 異常的定義 466
8.5.2 異常的傳播 468
8.5.3 實(shí)例：遞歸下降語法分析中的短語層恢復(fù) 470
8.5.4 異常的實(shí)現(xiàn) 471
8.6 協(xié)作程序 474
8.6.1 堆棧分配 476
8.6.2 轉(zhuǎn)移 478
8.6.3 迭代器 479
8.6.4 實(shí)例：離散事件模擬 480
8.7 總結(jié)和注記 484
8.8 復(fù)習(xí) 485
8.9 練習(xí) 486
8.10 有關(guān)參考文獻(xiàn) 489
第9章 構(gòu)造可運(yùn)行程序 491
9.1 后端編譯器結(jié)構(gòu) 491
9.1.1 一個(gè)實(shí)例 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 一個(gè)屬性文法實(shí)例 504
9.3.2 寄存器分配 504
9.4 地址空間組織 507
9.5 匯編 510
9.5.1 指令發(fā)射 511
9.5.2 為名字指定地址 514
9.6 連接 515
9.6.1 重定位和名字解析 515
9.6.2 類型檢查 516
9.7 動(dòng)態(tài)連接 518
9.7.1 與定位無關(guān)的代碼 519
9.7.2 完全動(dòng)態(tài)連接（惰性連接） 521
9.8 總結(jié)和注記 522
9.9 復(fù)習(xí) 523
9.10 練習(xí) 524
9.11 有關(guān)參考文獻(xiàn) 527
第10章 數(shù)據(jù)抽象和面向?qū)ο?529
10.1 面向?qū)ο蟮某绦蛟O(shè)計(jì) 530
10.2 封裝和繼承 539
10.2.1 模塊 539
10.2.2 類 542
10.2.3 類型擴(kuò)展 544
10.3 初始化和終結(jié)處理 546
10.3.1 構(gòu)造函數(shù)的選擇 547
10.3.2 引用和值 550
10.3.3 執(zhí)行順序 551
10.3.4 廢料收集 553
10.4 動(dòng)態(tài)方法約束 554
10.4.1 虛函數(shù)和非虛函數(shù) 555
10.4.2 抽象類 557
10.4.3 成員查找 557
10.4.4 相關(guān)概念 561
10.5 多重繼承 564
10.5.1 語義歧義性 568
10.5.2 復(fù)本式繼承 570
10.5.3 共享繼承 572
10.5.4 混入式繼承 573
10.6 重溫面向?qū)ο蟮某绦蛟O(shè)計(jì) 574
10.6.1 Smalltalk的對象模型 577
10.7 總結(jié)和注記 580
10.8 復(fù)習(xí) 582
10.9 練習(xí) 583
10.10 有關(guān)參考文獻(xiàn) 586
第11章 非命令式程序設(shè)計(jì)模型：函數(shù)式和邏輯式語言 589
11.1 歷史淵源 590
11.2 函數(shù)式程序設(shè)計(jì) 592
11.2.1 Scheme簡介 594
11.2.2 重溫求值順序 604
11.2.3 高階函數(shù) 609
11.2.4 理論基礎(chǔ) 612
11.2.5 函數(shù)式程序設(shè)計(jì)展望 622
11.3 邏輯式程序設(shè)計(jì) 624
11.3.1 Prolog 625
11.3.2 理論基礎(chǔ) 641
11.3.3 邏輯式程序設(shè)計(jì)的展望 646
11.4 總結(jié)和注記 648
11.5 復(fù)習(xí) 650
11.6 練習(xí) 651
11.7 有關(guān)參考文獻(xiàn) 657
第12章 并發(fā) 659
12.1 基礎(chǔ)和動(dòng)力 660
12.1.1 簡單歷史 660
12.1.2 多線程程序的不同情況 663
12.1.3 多處理器體系結(jié)構(gòu) 667
12.2 并發(fā)程序設(shè)計(jì)基礎(chǔ) 670
12.2.1 通信和同步 671
12.2.2 語言和庫 672
12.2.3 創(chuàng)建線程的語法 673
12.2.4 線程的實(shí)現(xiàn) 682
12.3 共享存儲器 687
12.3.1 忙等待同步 688
12.3.2 調(diào)度器的實(shí)現(xiàn) 692
12.3.3 基于調(diào)度的同步 694
12.3.4 隱式同步 703
12.4 消息傳遞 706
12.4.1 通信對方的命名 706
12.4.2 傳送 710
12.4.3 接收 714
12.4.4 遠(yuǎn)程過程調(diào)用 719
12.5 總結(jié)和注記 722
12.6 復(fù)習(xí) 724
12.7 練習(xí) 725
12.8 有關(guān)參考文獻(xiàn) 730
第13章 代碼改進(jìn) 733
13.1 代碼優(yōu)化的階段 735
13.2 窺孔優(yōu)化 737
13.3 基本塊內(nèi)的冗余刪除 740
13.4 全局冗余刪除和數(shù)據(jù)流分析 745
13.4.1 靜態(tài)單賦值形式和全局值編號 746
13.4.2 全局公共子表達(dá)式刪除 750
13.5 循環(huán)改進(jìn) I 755
13.5.1 循環(huán)不變量 755
13.5.2 歸納變量 756
13.6 指令調(diào)度 759
13.7 循環(huán)改進(jìn) II 763
13.7.1 循環(huán)展開和軟件流水線 763
13.7.2 循環(huán)重排 767
13.8 寄存器分配 775
13.9 總結(jié)和注記 778
13.10 復(fù)習(xí) 780
13.11 練習(xí) 781
13.12 有關(guān)參考文獻(xiàn) 785
附錄A 本書中提到的程序設(shè)計(jì)語言 787
附錄B 語言設(shè)計(jì)和語言實(shí)現(xiàn) 795
參考書目 801
索引 827