內容簡介
本書聚焦編譯器設計的難點、痛點,在第1 章 概述編譯器的基本構成,並從編譯角度介紹高
級程序設計語言、目標語言和中間語言;第2 章 介紹文法的相關概念,以及如何進行程序語言設
計的問題;第3~9 章 介紹編譯器各組成部分的原理和設計,包括詞法分析器、語法分析器、中間
代碼生成器、中間代碼優化器、目標代碼生成器,以及符號表管理和運行時存儲空間組織。
本書可以作為高等學校計算機專業本科生的教材,也可供從事計算機應用的工程技術人員或
其他自學者學習參考。本書力求使學生僅掌握一門高級語言,即可開發出一個完整可用的編譯器,
從根本上解決國外技術依賴問題。
目錄
第1 章 編譯器概述 1
11 編譯器的基本概念 1
111 語言的分類 1
112 程序設計語言分類 2
113 編譯程序 2
114 編譯原理與技術的特點 3
115 編譯程序的生成 4
116 本書定位 5
12 高級程序設計語言 7
121 高級語言分類 7
122 程序結構 10
123 數據類型 13
124 語句形式 15
13 目標語言 20
131 CPU 架構和指令集 20
132 寄存器 21
133 匯編程序結構 24
134 彙編指令 26
135 尋址方式及記號約定 26
136 傳送指令 27
137 基本運算指令 28
138 轉移指令 31
139 棧操作指令 32
1310 浮點指令 33
14 中間語言 36
141 後綴式 36
142 圖表示法 37
143 三地址碼 38
15 編譯器組成 40
151 編譯器框架 40
152 編譯前端與後端 43
16 數學基礎 44
161 數理邏輯和記號 44
162 集合論 45
163 圖論 46
第1 章 習題 48
第2 章 文法與語言設計 49
21 文法和語言 49
211 基本概念 49
212 文法 50
213 推導和歸約 52
214 語言 53
215 文法的Chomsky 分類 55
22 語法樹與二義文法 56
221 短語和句柄 56
222 語法樹 57
223 二義文法 58
23 程序語言設計 59
231 正規式 60
232 正規式等價變換 61
233 基本運算的文法設計 61
234 連接-閉包和閉包-連接 62
235 拆分括號對 63
236 表達式的優先級與結合性 64
24 文法的等價變換 65
241 消除無用產生式 65
242 消除單非產生式 69
243 消除空符產生式 72
第2 章 習題 75
第3 章 詞法分析 76
31 詞法分析器的設計 76
311 詞法分析器的任務 76
312 詞法分析器設計需要考慮的問題 77
313 狀態轉換圖 78
32 有限自動機 79
321 確定有限自動機 79
322 非確定有限自動機 84
323 非確定有限自動機確定化 85
324 確定有限自動機化簡 94
325 正規式與有限自動機的等價性 98
33 正規文法 100
331 右線性文法轉有限自動機 100
332 左線性文法轉有限自動機 101
333 有限自動機轉右線性文法 102
334 有限自動機轉左線性文法 103
335 正規式轉右線性文法 104
336 正規式轉左線性文法 105
337 正規文法轉正規式 106
338 3 種工具的轉換 106
339 有限自動機轉正規式 107
34 詞法分析器的實現 108
341 詞法分析器邊界 108
342 單詞正規式 109
343 識別單詞的DFA 110
344 單詞識別算法 113
第3 章 習題 115
第4 章 語法分析 116
41 LL(1) 分析法 116
411 自上而下分析 116
412 消除顯式左遞歸 119
413 消除隱含左遞歸 120
414 消除左公因子 121
415 首符集First 122
416 後繼符集Follow 124
417 LL(1) 預測分析表 127
418 LL(1) 分析程序 129
419 二義文法的LL(1) 分析 132
4110 遞歸下降分析器 134
42 算符優先分析法 136
421 算符優先文法 136
422 首尾終結符集 137
423 使用棧求首、尾終結符集 139
424 算符優先分析表 143
425 算符優先分析程序 145
426 優先函數 149
427 用可達矩陣構造算符優先函數 150
43 LR 分析法 152
431 LR(0) 分析的基本思想 152
432 拓廣文法 157
433 LR(0) 項目集規範族 157
434 LR(0) 項目集規範族的構造 158
435 LR(0) 分析表構造 161
436 LR 分析器 164
437 LR(0) 分析法的局限性 166
438 SLR(1) 分析表構造 171
439 SLR(1) 分析法的局限性 173
4310 LR(1) 項目集規範族的構造 177
4311 LR(1) 分析表構造 180
4312 LALR(1) 項目集規範族的構造 184
4313 二義文法的LR 分析 186
第4 章 習題 194
第5 章 符號表管理 195
51 作用與操作 195
52 表項內容 195
521 變量 196
522 數組 196
523 結構體 197
524 過程 198
525 標號 198
53 結構組織 198
531 嵌套定義過程 198
532 符號表棧 201
533 非嵌套定義過程 202
54 內容組織 203
541 表格組織 203
542 表記錄組織 204
543 面向對象的組織 206
55 排序與查找 207
551 線性組織 207
552 二叉樹 208
553 平衡二叉樹 209
554 哈希表 214
第5 章 習題 217
第6 章 運行時存儲空間組織 218
61 目標代碼運行時的活動 218
611 運行時存儲空間訪問 218
612 棧幀結構 218
613 存儲空間分配策略 221
62 過程調用規範 222
621 高級程序參數傳遞 222
622 std call 224
623 C 調用規範 225
624 x64 調用規範 226
625 寄存器保護 227
626 地址計算 227
627 ARM 規範 229
63 運行時庫 229
631 使用C 運行時庫輸入/輸出 229
632 編譯器生成輸入/輸出代碼 231
633 冪運算 234
634 跨文件調用 237
635 封裝庫 238
64 嵌套定義過程 239
641 靜態鏈 239
642 靜態鏈構建 242
643 外層變量訪問 243
644 嵌套層次顯示表 244
645 display 表的構建 246
646 通過display 訪問變量 246
65 堆式存儲分配 247
651 堆區首地址 247
652 定長塊管理 247
653 保留元數據 249
654 變長塊管理 250
655 存儲回收 254
第6 章 習題 254
第7 章 語法制導翻譯與中間代碼生成 255
71 屬性文法及其計算 256
711 屬性翻譯文法 256
712 綜合屬性的自下而上計算 258
713 繼承屬性的自上而下計算 259
714 依賴圖 259
715 樹遍歷的計算方法 260
716 一遍掃描的處理方法 263
72 S-屬性文法 263
721 S-屬性文法的自下而上計算 263
722 構造表達式的抽象語法樹 264
723 NFA 箭弧單符化 266
73 L-屬性文法 269
731 翻譯模式 270
732 L-屬性文法自上而下計算 271
733 L-屬性文法自下而上計算 275
734 綜合屬性代替繼承屬性 278
74 聲明語句的翻譯 279
741 Pascal 風格過程內聲明語句 280
742 Pascal 風格過程定義與聲明語句 283
743 Pascal 風格數組聲明 288
744 Pascal 風格結構體聲明 293
745 C 風格函數定義與聲明語句 297
75 表達式與賦值語句的翻譯 305
751 算術表達式與賦值語句 305
752 Pascal 風格數組的引用 307
753 C 風格數組的引用 312
754 結構體的引用 312
755 作為邏輯運算的布爾表達式 316
756 地址和指針的引用 319
76 控制語句的翻譯 322
761 真、假出口鏈 322
762 四元式鏈操作 323
763 作為條件控制的布爾表達式 325
764 if 和while 語句 329
765 C 風格for 語句 335
766 MATLAB 風格for 語句 338
767 標號-goto 語句 343
768 switch 語句 346
769 break 和continue 語句 351
7610 三元運算符 356
7611 關係運算符的結合 358
77 過程語句的翻譯 361
771 過程的開始與結束標記 361
772 返回語句 361
773 過程調用 361
78 類型檢查 363
781 類型表達式 363
782 翻譯模式 364
783 隱式轉換 367
784 顯式轉換 370
第7 章 習題 370
第8 章 中間代碼優化 371
81 程序的拓撲結構 371
811 優化代碼例子 371
812 基本塊劃分 373
813 流圖構建 375
814 支配結點 377
815 回邊識別 379
816 循環識別 381
817 循環層次 384
818 支配樹 386
819 四元式編號調整 389
82 常用優化技術 391
821 優化的基本概念 391
822 刪除公共子表達式 392
823 複寫傳播 393
824 刪除無用賦值 394
825 代碼外提 394
826 強度削弱 395
827 合併已知常量 395
828 刪除歸納變量 396
83 局部優化 397
831 基本塊的DAG 表示 397
832 DAG 優化的基本思想 398
833 DAG 優化算法 398
834 變量附加的處理 405
835 數組的處理 406
84 數據流分析 407
841 任意路徑反向流分析 408
842 任意路徑前向流分析 413
843 全路徑前向流分析 417
844 全路徑反向流分析 422
845 數據流問題的分類 425
846 到達定值分析 426
847 引用-定值鏈 430
848 帶引用點的活躍變量分析 432
849 定值-引用鏈 435
85 全域優化 438
851 代碼提升 438
852 全域公共子表達式刪除 442
853 刪除無用賦值