程序設計語言：實踐之路

前言 xvii
第1章 引言 1
1.1 語言設計的藝術 3
1.2 程序設計語言的譜系 5
1.3 為什么研究程序設計語言 7
1.4 編譯和解釋 9
1.5 程序設計環(huán)境 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 作用域規(guī)則 115
3.3.1 靜態(tài)作用域 116
3.3.2 動態(tài)作用域 129
3.3.3 符號表 132
3.3.4 關聯(lián)表和中心引用表列 137
3.4 引用環(huán)境的約束 139
3.4.1 子程序閉包 141
3.4.2 一級和二級子程序 143
3.5 重載和相關概念 144
3.6 語言設計中與名字有關的缺陷 149
3.6.1 作用域規(guī)則 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 數(shù)據表示 209
5.3.1 整數(shù)算術 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 優(yōu)先級和結合性 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 枚舉控制的循環(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 應用序和正則序求值 301
6.7 非確定性 303
6.8 總結和注記 308
6.9 復習 310
6.10 練習 311
6.11 有關參考文獻 316
第7章 數(shù)據類型 319
7.1 類型系統(tǒng) 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的類型系統(tǒng) 344
7.3 記錄（結構）與變體（聯(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 總結和注記 416
7.12 復習 418
7.13 練習 420
7.14 有關參考文獻 425
第8章 子程序和控制抽象 427
8.1 重溫堆棧布局 428
8.2 調用序列 431
8.2.1 實例研究：在MIPS上實現(xiàn)C 434
8.2.2 實例研究：在680x0上實現(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 實例：遞歸下降語法分析中的短語層恢復 470
8.5.4 異常的實現(xiàn) 471
8.6 協(xié)作程序 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 指令發(fā)射 511
9.5.2 為名字指定地址 514
9.6 連接 515
9.6.1 重定位和名字解析 515
9.6.2 類型檢查 516
9.7 動態(tài)連接 518
9.7.1 與定位無關的代碼 519
9.7.2 完全動態(tài)連接（惰性連接） 521
9.8 總結和注記 522
9.9 復習 523
9.10 練習 524
9.11 有關參考文獻 527
第10章 數(shù)據抽象和面向對象 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 構造函數(shù)的選擇 547
10.3.2 引用和值 550
10.3.3 執(zhí)行順序 551
10.3.4 廢料收集 553
10.4 動態(tài)方法約束 554
10.4.1 虛函數(shù)和非虛函數(shù) 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章 非命令式程序設計模型：函數(shù)式和邏輯式語言 589
11.1 歷史淵源 590
11.2 函數(shù)式程序設計 592
11.2.1 Scheme簡介 594
11.2.2 重溫求值順序 604
11.2.3 高階函數(shù) 609
11.2.4 理論基礎 612
11.2.5 函數(shù)式程序設計展望 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章 并發(fā) 659
12.1 基礎和動力 660
12.1.1 簡單歷史 660
12.1.2 多線程程序的不同情況 663
12.1.3 多處理器體系結構 667
12.2 并發(fā)程序設計基礎 670
12.2.1 通信和同步 671
12.2.2 語言和庫 672
12.2.3 創(chuàng)建線程的語法 673
12.2.4 線程的實現(xiàn) 682
12.3 共享存儲器 687
12.3.1 忙等待同步 688
12.3.2 調度器的實現(xiàn) 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 代碼優(yōu)化的階段 735
13.2 窺孔優(yōu)化 737
13.3 基本塊內的冗余刪除 740
13.4 全局冗余刪除和數(shù)據流分析 745
13.4.1 靜態(tài)單賦值形式和全局值編號 746
13.4.2 全局公共子表達式刪除 750
13.5 循環(huán)改進 I 755
13.5.1 循環(huán)不變量 755
13.5.2 歸納變量 756
13.6 指令調度 759
13.7 循環(huán)改進 II 763
13.7.1 循環(huán)展開和軟件流水線 763
13.7.2 循環(huán)重排 767
13.8 寄存器分配 775
13.9 總結和注記 778
13.10 復習 780
13.11 練習 781
13.12 有關參考文獻 785
附錄A 本書中提到的程序設計語言 787
附錄B 語言設計和語言實現(xiàn) 795
參考書目 801
索引 827