編譯原理, 5/e

第 1 章 編譯概述 ……………………………………………………………………………… 1
1. 1 翻譯程序與編譯程序 ……………………………………………………………………… 1
1.2 編譯過程和編譯程序的基本結構 ………………………………………………………… 2
1.3 編譯程序的生成方法 ……………………………………………………………………… 5
1. 4 編譯技術在軟件開發中的應用 …………………………………………………………… 6
本章小結 ……………………………………………………………………………………… 7
擴展閱讀 ……………………………………………………………………………………… 7
自測練習題 1 ………………………………………………………………………………… 7
習題 1 …………………………………………………………………………………………8
第 2 章 文法和語言的基本知識 ………………………………………………………………9
2. 1 概述 ……………………………………………………………………………………… 9
2.2 字母表和符號串的基本概念 ……………………………………………………………… 9
2.2.1 字母表和符號串 …………………………………………………………………… 9
2.2.2 符號串的運算 …………………………………………………………………… 10
2.3 文法和語言的形式定義 ………………………………………………………………… 11
2.3.1 形式語言 ………………………………………………………………………… 11
2.3.2 文法的形式定義…………………………………………………………………… 12
2.3.3 語言的形式定義…………………………………………………………………… 15
2.3. 4 規範推導和規範歸約 ……………………………………………………………… 17
2.3.5 遞歸規則與文法的遞歸性 ………………………………………………………… 19
2.4 短語、 直接短語和句柄 ………………………………………………………………… 20
2. 4. 1 短語和直接短語…………………………………………………………………… 20
2.4.2 句柄 ……………………………………………………………………………… 20
2.5 語法樹與文法的二義性 ………………………………………………………………… 21
2.5.1 推導和語法樹 …………………………………………………………………… 21
2.5.2 文法的二義性 …………………………………………………………………… 23
2.5.3 文法二義性的消除 ………………………………………………………………… 24
2.6 文法和語言的分類 ……………………………………………………………………… 25
2.7 有關文法的實用限制和變換 ……………………………………………………………… 27
本章小結 ……………………………………………………………………………………… 28
擴展閱讀 ……………………………………………………………………………………… 29
自測練習題 2 ………………………………………………………………………………… 29
習題 2 …………………………………………………………………………………………32
第 3 章 詞法分析與有窮自動機……………………………………………………………… 34
3.1 詞法分析程序的功能 …………………………………………………………………… 34
3. 2 單詞符號及輸出單詞的形式 ……………………………………………………………… 34
3.2. 1 語言的單詞符號…………………………………………………………………… 35
3. 2.2 詞法分析程序輸出單詞的形式 …………………………………………………… 35
3.3 語言單詞符號的兩種定義方式 …………………………………………………………… 36
3. 3. 1 正規式與正規集…………………………………………………………………… 36
3. 3. 2 正規文法與正規式 ………………………………………………………………… 37
3.4 正規式與有窮自動機 …………………………………………………………………… 40
3.4. 1 確定有窮自動機 (DFA) ………………………………………………………… 40
3. 4.2 非確定有窮自動機 (NFA) ……………………………………………………… 41
3. 4. 3 由正規表達式 R 構造 NFA ………………………………………………………… 42
3. 4. 4 NFA 確定化為 DFA 的方法 ………………………………………………………… 43
3. 4.5 DFA 的化簡 ……………………………………………………………………… 46
3.4. 6 有窮自動機到正規式的轉換 ……………………………………………………… 48
3.5 正規文法與有窮自動機 ………………………………………………………………… 49
3.5.1 右線性正規文法到有窮自動機的轉換方法 ………………………………………… 49
3. 5. 2 左線性正規文法到有窮自動機的轉換方法 ………………………………………… 50
3. 5.3 有窮自動機到正規文法的轉換方法………………………………………………… 50
3.6 詞法分析程序的編寫方法………………………………………………………………… 51
本章小結 ……………………………………………………………………………………… 56
擴展閱讀 ……………………………………………………………………………………… 57
自測練習題 3 ………………………………………………………………………………… 58
習題 3 …………………………………………………………………………………………59
第 4 章 語法分析 ……………………………………………………………………………… 62
4. 1 語法分析程序的功能 …………………………………………………………………… 62
4.2 自上而下分析法 ………………………………………………………………………… 63
4.2. 1 非確定的自上而下分析法的思想 ………………………………………………… 63
4. 2.2 文法的左遞歸性和回溯的消除 …………………………………………………… 64
4. 2.3 某些非 LL(1)文法到 LL(1)文法的改寫 …………………………………………… 67
4.2.4 遞歸下降分析法…………………………………………………………………… 69
4. 2. 5 預測分析法與預測分析表的構造 ………………………………………………… 71
4. 3 自下而上分析法的一般原理 ……………………………………………………………… 73
4.4 算符優先分析法 ………………………………………………………………………… 74
4.4. 1 方法概述 ………………………………………………………………………… 74
4. 4.2 算符優先文法的定義 ……………………………………………………………… 75
4.4.3 算符優先關系表的構造 …………………………………………………………… 76
4.4.4 算符優先分析算法的設計 ………………………………………………………… 77
4.4. 5 優先函數的構造…………………………………………………………………… 80
4.4.6 算符優先分析法的局限性 ………………………………………………………… 82
4.5 LR 分析法 ……………………………………………………………………………… 82
4.5.1 LR 分析器的工作原理和過程 ……………………………………………………… 82
4. 5.2 LR(0)分析法 …………………………………………………………………… 85
4. 5. 3 SLR(1)分析法 …………………………………………………………………… 89
4.5.4 LR(1)分析法 …………………………………………………………………… 93
4.5.5 LALR(1)分析法 ………………………………………………………………… 96
4.5.6 LR 分析法對二義性文法的應用 …………………………………………………… 99
4. 5.7 LR 語法分析中的錯誤恢復技術…………………………………………………… 100
4.6 語法分析程序的編寫方法 ……………………………………………………………… 103
本章小結 …………………………………………………………………………………… 104
擴展閱讀 …………………………………………………………………………………… 105
自測練習題 4 ………………………………………………………………………………… 106
習題 4 ………………………………………………………………………………………108
第 5 章 語法制導翻譯技術和中間代碼生成 …………………………………………………111
5. 1 概述 …………………………………………………………………………………… 111
5.2 屬性文法 ……………………………………………………………………………… 111
5.3 語法制導翻譯概述 ……………………………………………………………………… 114
5.4 中間語言 ……………………………………………………………………………… 115
5.4.1 逆波蘭式 ………………………………………………………………………… 115
5.4.2 三元式和樹形表示 ……………………………………………………………… 116
5.4.3 四元式和三地址代碼 …………………………………………………………… 118
5.5 自下而上語法制導翻譯 ………………………………………………………………… 118
5.5.1 簡單算術表達式和賦值語句的翻譯 ……………………………………………… 118
5.5.2 布爾表達式的翻譯 ……………………………………………………………… 120
5.5.3 控制語句的翻譯 ………………………………………………………………… 126
5.5.4 循環語句的翻譯 ………………………………………………………………… 129
5.5.5 簡單說明語句的翻譯 …………………………………………………………… 130
5.5.6 含數組元素的賦值語句的翻譯 …………………………………………………… 131
5.5.7 過程和函數調用語句的翻譯 ……………………………………………………… 134
5.6 遞歸下降語法制導的翻譯 ……………………………………………………………… 136
本章小結 …………………………………………………………………………………… 137
擴展閱讀 …………………………………………………………………………………… 138
自測練習題 5 ………………………………………………………………………………… 138
習題 5 ………………………………………………………………………………………139
第 6 章 符號表的組織與管理 …………………………………………………………………141
6. 1 符號表的作用…………………………………………………………………………… 141
6.2 符號表的組織…………………………………………………………………………… 143
6.3 符號表的建立和查找 …………………………………………………………………… 146
本章小結 …………………………………………………………………………………… 149
擴展閱讀 …………………………………………………………………………………… 149
自測練習題 6 ………………………………………………………………………………… 149
習題 6 ………………………………………………………………………………………150
第 7 章 代碼優化 ………………………………………………………………………………151
7.1 優化概述 ……………………………………………………………………………… 151
7.2 局部優化 ……………………………………………………………………………… 155
7.2. 1 劃分基本塊的方法 ……………………………………………………………… 155
7.2.2 基本塊的 DAG 表示 ……………………………………………………………… 155
7.2.3 利用 DAG 進行基本塊的優化處理 ………………………………………………… 159
7. 3 循環優化 ……………………………………………………………………………… 160
7.3.1 程序流圖與循環 ………………………………………………………………… 161
7.3.2 循環查找 ………………………………………………………………………… 162
7.3. 3 循環優化 ………………………………………………………………………… 164
7.4 窺孔優化 ……………………………………………………………………………… 168
本章小結 …………………………………………………………………………………… 170
擴展閱讀 …………………………………………………………………………………… 171
自測練習題 7 ………………………………………………………………………………… 171
習題 7 ………………………………………………………………………………………172
第 8 章 運行時的存儲組織與管理…………………………………………………………… 173
8.1 概述 …………………………………………………………………………………… 173
8. 2 靜態存儲分配…………………………………………………………………………… 174
8.3 棧式存儲分配…………………………………………………………………………… 175
8.3.1 簡單棧式存儲分配 ……………………………………………………………… 175
8.3.2 嵌套過程的棧式存儲分配 ………………………………………………………… 176
8.4 堆式存儲分配…………………………………………………………………………… 178
8.5 臨時變量的存儲分配 …………………………………………………………………… 179
本章小結 …………………………………………………………………………………… 179
擴展閱讀 …………………………………………………………………………………… 180
自測練習題 8 ………………………………………………………………………………… 180
習題 8 ………………………………………………………………………………………180
第 9 章 目標代碼生成 …………………………………………………………………………182
9. 1 概述 …………………………………………………………………………………… 182
9. 2 假想的電腦模型 ……………………………………………………………………… 182
9.3 簡單代碼生成器 ………………………………………………………………………… 183
9.3.1 待用信息與活躍信息 …………………………………………………………… 183
9. 3.2 代碼生成算法 …………………………………………………………………… 185
9.3. 3 寄存器的分配 …………………………………………………………………… 186
9.4 代碼生成器的自動生成技術 …………………………………………………………… 186
本章小結 …………………………………………………………………………………… 187
擴展閱讀 …………………………………………………………………………………… 187
自測練習題 9 ………………………………………………………………………………… 187
習題 9 ………………………………………………………………………………………187
第 10 章 並行編譯技術基本常識 ……………………………………………………………189
10. 1 並行編譯技術的引入…………………………………………………………………… 189
10. 2 並行編譯系統的功能和結構 …………………………………………………………… 190
10.2.1 並行編譯系統的功能 …………………………………………………………… 190
10.2.2 並行編譯系統的結構 …………………………………………………………… 190
10. 3 向量語言編譯技術 …………………………………………………………………… 191
10. 3.1 向量語法處理…………………………………………………………………… 191
10.3.2 向量結構優化…………………………………………………………………… 191
10.4 共享存儲器並行機並行編譯技術 ……………………………………………………… 192
10.4. 1 預編譯 ………………………………………………………………………… 192
10.4.2 可再入的目標代碼 ……………………………………………………………… 192
本章小結 …………………………………………………………………………………… 193
習題 10 ………………………………………………………………………………………193
附錄 A 詞法分析程序生成器 Lex ………………………………………………………… 194
A.1 詞法分析程序生成器 Lex 簡介 ………………………………………………………… 194
A.2 Lex 輸入文件的格式 …………………………………………………………………… 195
A.3 正規表達式的 Lex 約定 ………………………………………………………………… 197
A.4 Lex 源程序中的規則部分 ……………………………………………………………… 199
A. 5 Flex 的命令選項………………………………………………………………………… 201
A.6 Lex 程序示例 ……………………………………………………………………………202
附錄 B 語法分析程序生成器 YACC ………………………………………………………203
B. 1 語法分析程序 YACC 簡介 ……………………………………………………………… 203
B.2 YACC 輸入文件的格式 ………………………………………………………………… 203
B.3 YACC 各部分的書寫格式 ……………………………………………………………… 204
B. 3. 1 定義部分………………………………………………………………………… 204
B. 3.2 規則部分………………………………………………………………………… 207
B.3.3 輔助程序部分 …………………………………………………………………… 209
B.4 YACC 的內置名稱和定義機制…………………………………………………………… 209
B.5 Flex 與 Bison 的聯合使用 ………………………………………………………………209
附錄 C 編譯程序實驗 …………………………………………………………………………212
C.1 詞法分析 ……………………………………………………………………………… 212
C.1.1 實驗目的………………………………………………………………………… 212
C.1.2 實驗要求………………………………………………………………………… 212
C.1.3 詞法分析程序的算法思想………………………………………………………… 213
C.1.4 詞法分析程序的 C 語言程序框架 ………………………………………………… 214
C. 2 語法分析 ……………………………………………………………………………… 219
C.2. 1 實驗目的………………………………………………………………………… 219
C.2.2 實驗要求………………………………………………………………………… 219
C.2.3 語法分析程序的算法思想………………………………………………………… 219
C 2.4 語法分析程序的 C 語言程序框架 ………………………………………………… 221
C.3 語義分析 ……………………………………………………………………………… 222
C.3.1 實驗目的………………………………………………………………………… 222
C.3.2 實驗要求………………………………………………………………………… 222
C.3.3 語義分析程序的 C 語言程序框架 ………………………………………………… 223
C.4 算符優先分析法………………………………………………………………………… 225
C.5 實驗實例 ……………………………………………………………………………… 226
C.6 正規式轉換成自動機的圖形表示………………………………………………………… 244
C.6.1 實驗目的………………………………………………………………………… 244
C. 6.2 實驗要求………………………………………………………………………… 244
C.6.3 參考設計思路 …………………………………………………………………… 244
C.6.4 參考算法 …………………………………………………………………………245
附錄 D 自測練習題與習題參考答案 …………………………………………………………248
參考文獻………………………………………………………………………………………… 269