編譯原理與技術（微課版）
鄭艷偉、於東曉、周勁
相關主題
商品描述
目錄大綱
目錄
第1 章編譯器概述................................. 1
1.1 編譯器的基本概念..................... 1
1.1.1 語言的分類..................... 1
1.1.2 程序設計語言分類........... 2
1.1.3 編譯程序........................ 2
1.1.4 編譯原理與技術的特點.... 3
1.1.5 編譯程序的生成.............. 4
1.1.6 本書定位........................ 5
1.2 高級程序設計語言..................... 7
1.2.1 高級語言分類................. 7
1.2.2 程序結構...................... 10
1.2.3 數據類型...................... 13
1.2.4 語句形式...................... 15
1.3 目標語言................................. 20
1.3.1 CPU 架構和指令集........ 20
1.3.2 寄存器......................... 21
1.3.3 匯編程序結構............... 24
1.3.4 匯編指令...................... 26
1.3.5 尋址方式及記號約定..... 26
1.3.6 傳送指令...................... 27
1.3.7 基本運算指令............... 28
1.3.8 轉移指令...................... 31
1.3.9 棧操作指令................... 32
1.3.10 浮點指令.................... 33
1.4 中間語言................................. 36
1.4.1 後綴式......................... 36
1.4.2 圖表示法...................... 37
1.4.3 三地址碼...................... 38
1.5 編譯器組成............................. 40
1.5.1 編譯器框架................... 40
1.5.2 編譯前端與後端.............................. 43
1.6 數學基礎..... 44
1.6.1 數理邏輯和記號.............................. 44
1.6.2 集合論........................................... 45
1.6.3 圖論. 46
第1 章習題...... 48
第2 章文法與語言設計.......................................... 49
2.1 文法和語言. 49
2.1.1 基本概念........................................ 49
2.1.2 文法. 50
2.1.3 推導和歸約..................................... 52
2.1.4 語言. 53
2.1.5 文法的Chomsky 分類...................... 55
2.2 語法樹與二義文法..................................... 56
2.2.1 短語和句柄..................................... 56
2.2.2 語法樹........................................... 57
2.2.3 二義文法........................................ 58
2.3 程序語言設計............................................ 59
2.3.1 正規式........................................... 60
2.3.2 正規式等價變換.............................. 61
2.3.3 基本運算的文法設計....................... 61
2.3.4 連接-閉包和閉包-連接..................... 62
2.3.5 拆分括號對..................................... 63
2.3.6 表達式的優先級與結合性................. 64
2.4 文法的等價變換......................................... 65
2.4.1 消除無用產生式.............................. 65
2.4.2 消除單非產生式.............................. 69
2.4.3 消除空符產生式.............................. 72
第2 章習題...... 75
第3 章詞法分析...... 76
3.1 詞法分析器的設計..................................... 76
3.1.1 詞法分析器的任務........................... 76
3.1.2 詞法分析器設計需要考慮的問題....... 77
3.1.3 狀態轉換圖..................................... 78
3.2 有限自動機. 79
3.2.1 確定有限自動機.............................. 79
3.2.2 非確定有限自動機........................... 84
3.2.3 非確定有限自動機確定化................. 85
3.2.4 確定有限自動機化簡....................... 94
3.2.5 正規式與有限自動機的等價性.......... 98
3.3 正規文法.... 100
3.3.1 右線性文法轉有限自動機................ 100
3.3.2 左線性文法轉有限自動機................ 101
3.3.3 有限自動機轉右線性文法................ 102
3.3.4 有限自動機轉左線性文法................ 103
3.3.5 正規式轉右線性文法...................... 104
3.3.6 正規式轉左線性文法...................... 105
3.3.7 正規文法轉正規式.......................... 106
3.3.8 3 種工具的轉換.............................. 106
3.3.9 有限自動機轉正規式...................... 107
3.4 詞法分析器的實現.................................... 108
3.4.1 詞法分析器邊界............................. 108
3.4.2 單詞正規式.................................... 109
3.4.3 識別單詞的DFA ............................ 110
3.4.4 單詞識別算法................................ 113
第3 章習題..... 115
第4 章語法分析..... 116
4.1 LL(1) 分析法............................................ 116
4.1.1 自上而下分析................................ 116
4.1.2 消除顯式左遞歸............................. 119
4.1.3 消除隱含左遞歸............................. 120
4.1.4 消除左公因子................................ 121
4.1.5 首符集First .................................. 122
4.1.6 後繼符集Follow ............................ 124
4.1.7 LL(1) 預測分析表........................... 127
4.1.8 LL(1) 分析程序.............................. 129
4.1.9 二義文法的LL(1) 分析................... 132
4.1.10 遞歸下降分析器........................... 134
4.2 算符優先分析法........................................ 136
4.2.1 算符優先文法................................ 136
4.2.2 首尾終結符集................................ 137
4.2.3 使用棧求首、尾終結符集................ 139
4.2.4 算符優先分析表............................. 143
4.2.5 算符優先分析程序.......................... 145
4.2.6 優先函數....................................... 149
4.2.7 用可達矩陣構造算符優先函數......... 150
4.3 LR 分析法.. 152
4.3.1 LR(0) 分析的基本思想.................... 152
4.3.2 拓廣文法....................................... 157
4.3.3 LR(0) 項目集規範族....................... 157
4.3.4 LR(0) 項目集規範族的構造............. 158
4.3.5 LR(0) 分析表構造.......................... 161
4.3.6 LR 分析器..................................... 164
4.3.7 LR(0) 分析法的局限性.................... 166
4.3.8 SLR(1) 分析表構造........................ 171
4.3.9 SLR(1) 分析法的局限性.................. 173
4.3.10 LR(1) 項目集規範族的構造........... 177
4.3.11 LR(1) 分析表構造......................... 180
4.3.12 LALR(1) 項目集規範族的構造....... 184
4.3.13 二義文法的LR 分析...................... 186
第4 章習題..... 194
第5 章符號表管理.. 195
5.1 作用與操作 195
5.2 表項內容.... 195
5.2.1 變量 196
5.2.2 數組 196
5.2.3 結構體.......................................... 197
5.2.4 過程 198
5.2.5 標號 198
5.3 結構組織.... 198
5.3.1 嵌套定義過程................................ 198
5.3.2 符號表棧....................................... 201
5.3.3 非嵌套定義過程............................. 202
5.4 內容組織.... 203
5.4.1 表格組織....................................... 203
5.4.2 表記錄組織.................................... 204
5.4.3 面向對象的組織............................. 206
5.5 排序與查找 207
5.5.1 線性組織....................................... 207
5.5.2 二叉樹.......................................... 208
5.5.3 平衡二叉樹.................................... 209
5.5.4 哈希表.......................................... 214
第5 章習題..... 217
第6 章運行時存儲空間組織.................................. 218
6.1 目標代碼運行時的活動.............................. 218
6.1.1 運行時存儲空間訪問...................... 218
6.1.2 棧幀結構....................................... 218
6.1.3 存儲空間分配策略.......................... 221
6.2 過程調用規範........................................... 222
6.2.1 高級程序參數傳遞.......................... 222
6.2.2 std call .......................................... 224
6.2.3 C 調用規範.................................... 225
6.2.4 x64 調用規範................................. 226
6.2.5 寄存器保護.................................... 227
6.2.6 地址計算....................................... 227
6.2.7 ARM 規範..................................... 229
6.3 運行時庫.... 229
6.3.1 使用C 運行時庫輸入/輸出.............. 229
6.3.2 編譯器生成輸入/輸出代碼.............. 231
6.3.3 冪運算.......................................... 234
6.3.4 跨文件調用.................................... 237
6.3.5 封裝庫.......................................... 238
6.4 嵌套定義過程........................................... 239
6.4.1 靜態鏈.......................................... 239
6.4.2 靜態鏈構建.................................... 242
6.4.3 外層變量訪問................................ 243
6.4.4 嵌套層次顯示表............................. 244
6.4.5 display 表的構建............................ 246
6.4.6 通過display 訪問變量..................... 246
6.5 堆式存儲分配........................................... 247
6.5.1 堆區首地址.................................... 247
6.5.2 定長塊管理.................................... 247
6.5.3 保留元數據.................................... 249
6.5.4 變長塊管理.................................... 250
6.5.5 存儲回收....................................... 254
第6 章習題..... 254
第7 章語法制導翻譯與中間代碼生成..................... 255
7.1 屬性文法及其計算.................................... 256
7.1.1 屬性翻譯文法................................ 256
7.1.2 綜合屬性的自下而上計算................ 258
7.1.3 繼承屬性的自上而下計算................ 259
7.1.4 依賴圖.......................................... 259
7.1.5 樹遍歷的計算方法.......................... 260
7.1.6 一遍掃描的處理方法...................... 263
7.2 S-屬性文法. 263
7.2.1 S-屬性文法的自下而上計算............. 263
7.2.2 構造表達式的抽象語法樹................ 264
7.2.3 NFA 箭弧單符化............................ 266
7.3 L-屬性文法. 269
7.3.1 翻譯模式....................................... 270
7.3.2 L-屬性文法自上而下計算................ 271
7.3.3 L-屬性文法自下而上計算................ 275
7.3.4 綜合屬性代替繼承屬性................... 278
7.4 聲明語句的翻譯........................................ 279
7.4.1 Pascal 風格過程內聲明語句............ 280
7.4.2 Pascal 風格過程定義與聲明語句...... 283
7.4.3 Pascal 風格數組聲明...................... 288
7.4.4 Pascal 風格結構體聲明................... 293
7.4.5 C 風格函數定義與聲明語句............. 297
7.5 表達式與賦值語句的翻譯.......................... 305
7.5.1 算術表達式與賦值語句................... 305
7.5.2 Pascal 風格數組的引用................... 307
7.5.3 C 風格數組的引用.......................... 312
7.5.4 結構體的引用................................ 312
7.5.5 作為邏輯運算的布爾表達式............ 316
7.5.6 地址和指針的引用.......................... 319
7.6 控制語句的翻譯........................................ 322
7.6.1 真、假出口鏈................................ 322
7.6.2 四元式鏈操作................................ 323
7.6.3 作為條件控制的布爾表達式............ 325
7.6.4 if 和while 語句............................... 329
7.6.5 C 風格for 語句............................... 335
7.6.6 MATLAB 風格for 語句................... 338
7.6.7 標號-goto 語句............................... 343
7.6.8 switch 語句.................................... 346
7.6.9 break 和continue 語句.................... 351
7.6.10 三元運算符.................................. 356
7.6.11 關系運算符的結合........................ 358
7.7 過程語句的翻譯........................................ 361
7.7.1 過程的開始與結束標記................... 361
7.7.2 返回語句....................................... 361
7.7.3 過程調用....................................... 361
7.8 類型檢查.... 363
7.8.1 類型表達式.................................... 363
7.8.2 翻譯模式....................................... 364
7.8.3 隱式轉換....................................... 367
7.8.4 顯式轉換....................................... 370
第7 章習題..... 370
第8 章中間代碼優化............................................ 371
8.1 程序的拓撲結構........................................ 371
8.1.1 優化代碼例子................................ 371
8.1.2 基本塊劃分.................................... 373
8.1.3 流圖構建....................................... 375
8.1.4 支配結點....................................... 377
8.1.5 回邊識別....................................... 379
8.1.6 循環識別....................................... 381
8.1.7 循環層次....................................... 384
8.1.8 支配樹.......................................... 386
8.1.9 四元式編號調整............................. 389
8.2 常用優化技術........................................... 391
8.2.1 優化的基本概念............................. 391
8.2.2 刪除公共子表達式.......................... 392
8.2.3 復寫傳播....................................... 393
8.2.4 刪除無用賦值................................ 394
8.2.5 代碼外提....................................... 394
8.2.6 強度削弱....................................... 395
8.2.7 合並已知常量................................ 395
8.2.8 刪除歸納變量................................ 396
8.3 局部優化.... 397
8.3.1 基本塊的DAG 表示........................ 397
8.3.2 DAG 優化的基本思想..................... 398
8.3.3 DAG 優化算法............................... 398
8.3.4 變量附加的處理............................. 405
8.3.5 數組的處理.................................... 406
8.4 數據流分析 407
8.4.1 任意路徑反向流分析...................... 408
8.4.2 任意路徑前向流分析...................... 413
8.4.3 全路徑前向流分析.......................... 417
8.4.4 全路徑反向流分析.......................... 422
8.4.5 數據流問題的分類.......................... 425
8.4.6 到達定值分析................................ 426
8.4.7 引用-定值鏈.................................. 430
8.4.8 帶引用點的活躍變量分析................ 432
8.4.9 定值-引用鏈.................................. 435
8.5 全局優化.... 438
8.5.1 代碼提升....................................... 438
8.5.2 全局公共子表達式刪除................... 442
8.5.3 刪除無用賦值................................ 447
8.5.4 未初始化變量檢測.......................... 450
8.5.5 復寫傳播和常量傳播...................... 452
8.6 循環優化.... 454
8.6.1 代碼外提....................................... 454
8.6.2 歸納變量識別................................ 458
8.6.3 強度削弱....................................... 460
8.6.4 歸納變量刪除................................ 462
第8 章習題..... 465
第9 章目標代碼生成............................................ 466
9.1 基本問題.... 466
9.1.1 代碼生成器的輸入.......................... 466
9.1.2 目標程序的形式............................. 467
9.1.3 指令選擇....................................... 467
9.1.4 指令調度....................................... 468
9.1.5 寄存器分配.................................... 469
9.2 簡單代碼生成器........................................ 469
9.2.1 代碼書寫約定................................ 469
9.2.2 待用信息....................................... 470
9.2.3 寄存器描述符和地址描述符............ 473
9.2.4 簡單代碼生成算法.......................... 474
9.2.5 局部寄存器分配............................. 477
9.2.6 釋放寄存器.................................... 478
9.2.7 簡單代碼生成示例.......................... 479
9.3 目標代碼映射........................................... 481
9.3.1 整型運算....................................... 481
9.3.2 浮點運算....................................... 482
9.3.3 數組 484
9.3.4 轉移語句....................................... 484
9.3.5 地址和指針.................................... 485
9.3.6 類型轉換....................................... 486
9.3.7 程序和過程.................................... 486
9.3.8 指令的執行代價............................. 487
9.4 基於DAG 的目標代碼優化......................... 488
9.4.1 基本思想....................................... 488
9.4.2 DAG 結點重排............................... 489
9.5 面向循環的固定寄存器分配....................... 491
9.5.1 固定寄存器分配代價計算................ 492
9.5.2 循環代碼生成................................ 494
9.6 圖著色寄存器分配.................................... 497
9.6.1 算法框架....................................... 497
9.6.2 分配虛擬寄存器............................. 498
9.6.3 低級中間代碼表示.......................... 501
9.6.4 構建沖突圖.................................... 502
9.6.5 合並寄存器.................................... 509
9.6.6 構建鄰接表.................................... 514
9.6.7 計算溢出代價................................ 517
9.6.8 修剪沖突圖.................................... 521
9.6.9 圖著色.......................................... 523
9.6.10 分配物理寄存器........................... 524
9.6.11 生成溢出代碼............................... 525
9.7 線性掃描寄存器分配................................. 531
9.7.1 流圖線性化.................................... 532
9.7.2 計算活躍區間................................ 532
9.7.3 分配物理寄存器............................. 536
9.8 全局目標代碼生成.................................... 544
9.8.1 全局代碼生成框架.......................... 544
9.8.2 操作數訪問.................................... 545
9.8.3 運算指令....................................... 547
9.8.4 加載保存指令................................ 548
9.8.5 數組指令....................................... 549
9.8.6 地址指針指令................................ 550
9.8.7 轉移指令....................................... 551
9.8.8 過程指令....................................... 551
9.8.9 過程調用指令................................ 553
9.8.10 代碼生成示例............................... 554
9.9 窺孔優化.... 558
9.9.1 目標代碼表示................................ 558
9.9.2 簡單窺孔優化模式.......................... 558
9.9.3 真、假出口轉移合並...................... 559
9.9.4 不可達代碼刪除............................. 561
9.9.5 控制流優化.................................... 562
9.9.6 窺孔優化框架................................ 564
第9 章習題..... 565
附錄A 面向對象語言的翻譯................................. 566
