本書(shū)是全國(guó)電子信息類(lèi)優(yōu)秀教材和華中科技大學(xué)優(yōu)秀教學(xué)成果，根據(jù)高等學(xué)校"編譯原理”課程教學(xué)基本要求編寫(xiě)。全書(shū)系統(tǒng)介紹了編譯程序的一般構(gòu)造原理、基本設(shè)計(jì)方法和主要實(shí)現(xiàn)技術(shù)。內(nèi)容包括：文法和語(yǔ)言基本知識(shí)、詞法分析程序的設(shè)計(jì)原理與構(gòu)造方法、各種語(yǔ)法分析技術(shù)、語(yǔ)法制導(dǎo)翻譯技術(shù)與中間代碼生成、符號(hào)表的組織和管理、代碼優(yōu)化、運(yùn)行時(shí)存儲(chǔ)空間的組織與管理、目標(biāo)代碼生成、并行編譯技術(shù)基本常識(shí)等。 本書(shū)系統(tǒng)性強(qiáng)、概念清晰，內(nèi)容簡(jiǎn)明通俗，每章配有本章學(xué)習(xí)導(dǎo)讀、本章小結(jié)、自測(cè)練習(xí)題和習(xí)題。附錄給出了自測(cè)練習(xí)題與習(xí)題參考答案及編譯程序?qū)嶒?yàn)等，本書(shū)還免費(fèi)提供電子課件和實(shí)驗(yàn)源代碼。 本書(shū)可作為高等學(xué)校計(jì)算機(jī)專(zhuān)業(yè)本科生教材，也可作為成人教育本科和專(zhuān)升本學(xué)生的教材，對(duì)相關(guān)工程技術(shù)人員也有參考價(jià)值。
劉銘，華中科技大學(xué)信息安全專(zhuān)業(yè)博士（2010），碩導(dǎo)，美國(guó)雪城大學(xué)訪問(wèn)學(xué)者。華中科技大學(xué)系統(tǒng)與軟件安全團(tuán)隊(duì)（湖北省青年五四獎(jiǎng)?wù)录w，2023）成員，長(zhǎng)期從事計(jì)算機(jī)系統(tǒng)軟件、軟件安全研究，參與國(guó)家自然科學(xué)基金項(xiàng)目5項(xiàng)，獲得相關(guān)專(zhuān)利10余項(xiàng)，主持教育部產(chǎn)學(xué)研協(xié)同育人項(xiàng)目1項(xiàng)，參與并獲得獲湖北省科技進(jìn)步一等獎(jiǎng)1項(xiàng)（2022），省部級(jí)教學(xué)成果二等獎(jiǎng)1項(xiàng)（2022），主編教材3部。
第 1 章 編譯概述 ……………………………………………………………………………… 1
1. 1 翻譯程序與編譯程序 ……………………………………………………………………… 1
1.2 編譯過(guò)程和編譯程序的基本結(jié)構(gòu) ………………………………………………………… 2
1.3 編譯程序的生成方法 ……………………………………………………………………… 5
1. 4 編譯技術(shù)在軟件開(kāi)發(fā)中的應(yīng)用 …………………………………………………………… 6
本章小結(jié) ……………………………………………………………………………………… 7
擴(kuò)展閱讀 ……………………………………………………………………………………… 7
自測(cè)練習(xí)題 1 ………………………………………………………………………………… 7
習(xí)題 1 …………………………………………………………………………………………8
第 2 章 文法和語(yǔ)言的基本知識(shí) ………………………………………………………………9
2. 1 概述 ……………………………………………………………………………………… 9
2.2 字母表和符號(hào)串的基本概念 ……………………………………………………………… 9
2.2.1 字母表和符號(hào)串 …………………………………………………………………… 9
2.2.2 符號(hào)串的運(yùn)算 …………………………………………………………………… 10
2.3 文法和語(yǔ)言的形式定義 ………………………………………………………………… 11
2.3.1 形式語(yǔ)言 ………………………………………………………………………… 11
2.3.2 文法的形式定義…………………………………………………………………… 12
2.3.3 語(yǔ)言的形式定義…………………………………………………………………… 15
2.3. 4 規(guī)范推導(dǎo)和規(guī)范歸約 ……………………………………………………………… 17
2.3.5 遞歸規(guī)則與文法的遞歸性 ………………………………………………………… 19
2.4 短語(yǔ)、 直接短語(yǔ)和句柄 ………………………………………………………………… 20
2. 4. 1 短語(yǔ)和直接短語(yǔ)…………………………………………………………………… 20
2.4.2 句柄 ……………………………………………………………………………… 20
2.5 語(yǔ)法樹(shù)與文法的二義性 ………………………………………………………………… 21
2.5.1 推導(dǎo)和語(yǔ)法樹(shù) …………………………………………………………………… 21
2.5.2 文法的二義性 …………………………………………………………………… 23
2.5.3 文法二義性的消除 ………………………………………………………………… 24
2.6 文法和語(yǔ)言的分類(lèi) ……………………………………………………………………… 25
2.7 有關(guān)文法的實(shí)用限制和變換 ……………………………………………………………… 27
本章小結(jié) ……………………………………………………………………………………… 28
擴(kuò)展閱讀 ……………………………………………………………………………………… 29
自測(cè)練習(xí)題 2 ………………………………………………………………………………… 29
習(xí)題 2 …………………………………………………………………………………………32
第 3 章 詞法分析與有窮自動(dòng)機(jī)……………………………………………………………… 34
3.1 詞法分析程序的功能 …………………………………………………………………… 34
3. 2 單詞符號(hào)及輸出單詞的形式 ……………………………………………………………… 34
3.2. 1 語(yǔ)言的單詞符號(hào)…………………………………………………………………… 35
3. 2.2 詞法分析程序輸出單詞的形式 …………………………………………………… 35
3.3 語(yǔ)言單詞符號(hào)的兩種定義方式 …………………………………………………………… 36
3. 3. 1 正規(guī)式與正規(guī)集…………………………………………………………………… 36
3. 3. 2 正規(guī)文法與正規(guī)式 ………………………………………………………………… 37
3.4 正規(guī)式與有窮自動(dòng)機(jī) …………………………………………………………………… 40
3.4. 1 確定有窮自動(dòng)機(jī) (DFA) ………………………………………………………… 40
3. 4.2 非確定有窮自動(dòng)機(jī) (NFA) ……………………………………………………… 41
3. 4. 3 由正規(guī)表達(dá)式 R 構(gòu)造 NFA ………………………………………………………… 42
3. 4. 4 NFA 確定化為 DFA 的方法 ………………………………………………………… 43
3. 4.5 DFA 的化簡(jiǎn) ……………………………………………………………………… 46
3.4. 6 有窮自動(dòng)機(jī)到正規(guī)式的轉(zhuǎn)換 ……………………………………………………… 48
3.5 正規(guī)文法與有窮自動(dòng)機(jī) ………………………………………………………………… 49
3.5.1 右線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法 ………………………………………… 49
3. 5. 2 左線性正規(guī)文法到有窮自動(dòng)機(jī)的轉(zhuǎn)換方法 ………………………………………… 50
3. 5.3 有窮自動(dòng)機(jī)到正規(guī)文法的轉(zhuǎn)換方法………………………………………………… 50
3.6 詞法分析程序的編寫(xiě)方法………………………………………………………………… 51
本章小結(jié) ……………………………………………………………………………………… 56
擴(kuò)展閱讀 ……………………………………………………………………………………… 57
自測(cè)練習(xí)題 3 ………………………………………………………………………………… 58
習(xí)題 3 …………………………………………………………………………………………59
第 4 章 語(yǔ)法分析 ……………………………………………………………………………… 62
4. 1 語(yǔ)法分析程序的功能 …………………………………………………………………… 62
4.2 自上而下分析法 ………………………………………………………………………… 63
4.2. 1 非確定的自上而下分析法的思想 ………………………………………………… 63
4. 2.2 文法的左遞歸性和回溯的消除 …………………………………………………… 64
4. 2.3 某些非 LL(1)文法到 LL(1)文法的改寫(xiě) …………………………………………… 67
4.2.4 遞歸下降分析法…………………………………………………………………… 69
4. 2. 5 預(yù)測(cè)分析法與預(yù)測(cè)分析表的構(gòu)造 ………………………………………………… 71
4. 3 自下而上分析法的一般原理 ……………………………………………………………… 73
4.4 算符優(yōu)先分析法 ………………………………………………………………………… 74
4.4. 1 方法概述 ………………………………………………………………………… 74
4. 4.2 算符優(yōu)先文法的定義 ……………………………………………………………… 75
4.4.3 算符優(yōu)先關(guān)系表的構(gòu)造 …………………………………………………………… 76
4.4.4 算符優(yōu)先分析算法的設(shè)計(jì) ………………………………………………………… 77
4.4. 5 優(yōu)先函數(shù)的構(gòu)造…………………………………………………………………… 80
4.4.6 算符優(yōu)先分析法的局限性 ………………………………………………………… 82
4.5 LR 分析法 ……………………………………………………………………………… 82
4.5.1 LR 分析器的工作原理和過(guò)程 ……………………………………………………… 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 分析法對(duì)二義性文法的應(yīng)用 …………………………………………………… 99
4. 5.7 LR 語(yǔ)法分析中的錯(cuò)誤恢復(fù)技術(shù)…………………………………………………… 100
4.6 語(yǔ)法分析程序的編寫(xiě)方法 ……………………………………………………………… 103
本章小結(jié) …………………………………………………………………………………… 104
擴(kuò)展閱讀 …………………………………………………………………………………… 105
自測(cè)練習(xí)題 4 ………………………………………………………………………………… 106
習(xí)題 4 ………………………………………………………………………………………108
第 5 章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成 …………………………………………………111
5. 1 概述 …………………………………………………………………………………… 111
5.2 屬性文法 ……………………………………………………………………………… 111
5.3 語(yǔ)法制導(dǎo)翻譯概述 ……………………………………………………………………… 114
5.4 中間語(yǔ)言 ……………………………………………………………………………… 115
5.4.1 逆波蘭式 ………………………………………………………………………… 115
5.4.2 三元式和樹(shù)形表示 ……………………………………………………………… 116
5.4.3 四元式和三地址代碼 …………………………………………………………… 118
5.5 自下而上語(yǔ)法制導(dǎo)翻譯 ………………………………………………………………… 118
5.5.1 簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯 ……………………………………………… 118
5.5.2 布爾表達(dá)式的翻譯 ……………………………………………………………… 120
5.5.3 控制語(yǔ)句的翻譯 ………………………………………………………………… 126
5.5.4 循環(huán)語(yǔ)句的翻譯 ………………………………………………………………… 129
5.5.5 簡(jiǎn)單說(shuō)明語(yǔ)句的翻譯 …………………………………………………………… 130
5.5.6 含數(shù)組元素的賦值語(yǔ)句的翻譯 …………………………………………………… 131
5.5.7 過(guò)程和函數(shù)調(diào)用語(yǔ)句的翻譯 ……………………………………………………… 134
5.6 遞歸下降語(yǔ)法制導(dǎo)的翻譯 ……………………………………………………………… 136
本章小結(jié) …………………………………………………………………………………… 137
擴(kuò)展閱讀 …………………………………………………………………………………… 138
自測(cè)練習(xí)題 5 ………………………………………………………………………………… 138
習(xí)題 5 ………………………………………………………………………………………139
第 6 章 符號(hào)表的組織與管理 …………………………………………………………………141
6. 1 符號(hào)表的作用…………………………………………………………………………… 141
6.2 符號(hào)表的組織…………………………………………………………………………… 143
6.3 符號(hào)表的建立和查找 …………………………………………………………………… 146
本章小結(jié) …………………………………………………………………………………… 149
擴(kuò)展閱讀 …………………………………………………………………………………… 149
自測(cè)練習(xí)題 6 ………………………………………………………………………………… 149
習(xí)題 6 ………………………………………………………………………………………150
第 7 章 代碼優(yōu)化 ………………………………………………………………………………151
7.1 優(yōu)化概述 ……………………………………………………………………………… 151
7.2 局部?jī)?yōu)化 ……………………………………………………………………………… 155
7.2. 1 劃分基本塊的方法 ……………………………………………………………… 155
7.2.2 基本塊的 DAG 表示 ……………………………………………………………… 155
7.2.3 利用 DAG 進(jìn)行基本塊的優(yōu)化處理 ………………………………………………… 159
7. 3 循環(huán)優(yōu)化 ……………………………………………………………………………… 160
7.3.1 程序流圖與循環(huán) ………………………………………………………………… 161
7.3.2 循環(huán)查找 ………………………………………………………………………… 162
7.3. 3 循環(huán)優(yōu)化 ………………………………………………………………………… 164
7.4 窺孔優(yōu)化 ……………………………………………………………………………… 168
本章小結(jié) …………………………………………………………………………………… 170
擴(kuò)展閱讀 …………………………………………………………………………………… 171
自測(cè)練習(xí)題 7 ………………………………………………………………………………… 171
習(xí)題 7 ………………………………………………………………………………………172
第 8 章 運(yùn)行時(shí)的存儲(chǔ)組織與管理…………………………………………………………… 173
8.1 概述 …………………………………………………………………………………… 173
8. 2 靜態(tài)存儲(chǔ)分配…………………………………………………………………………… 174
8.3 棧式存儲(chǔ)分配…………………………………………………………………………… 175
8.3.1 簡(jiǎn)單棧式存儲(chǔ)分配 ……………………………………………………………… 175
8.3.2 嵌套過(guò)程的棧式存儲(chǔ)分配 ………………………………………………………… 176
8.4 堆式存儲(chǔ)分配…………………………………………………………………………… 178
8.5 臨時(shí)變量的存儲(chǔ)分配 …………………………………………………………………… 179
本章小結(jié) …………………………………………………………………………………… 179
擴(kuò)展閱讀 …………………………………………………………………………………… 180
自測(cè)練習(xí)題 8 ………………………………………………………………………………… 180
習(xí)題 8 ………………………………………………………………………………………180
第 9 章 目標(biāo)代碼生成 …………………………………………………………………………182
9. 1 概述 …………………………………………………………………………………… 182
9. 2 假想的計(jì)算機(jī)模型 ……………………………………………………………………… 182
9.3 簡(jiǎn)單代碼生成器 ………………………………………………………………………… 183
9.3.1 待用信息與活躍信息 …………………………………………………………… 183
9. 3.2 代碼生成算法 …………………………………………………………………… 185
9.3. 3 寄存器的分配 …………………………………………………………………… 186
9.4 代碼生成器的自動(dòng)生成技術(shù) …………………………………………………………… 186
本章小結(jié) …………………………………………………………………………………… 187
擴(kuò)展閱讀 …………………………………………………………………………………… 187
自測(cè)練習(xí)題 9 ………………………………………………………………………………… 187
習(xí)題 9 ………………………………………………………………………………………187
第 10 章 并行編譯技術(shù)基本常識(shí) ……………………………………………………………189
10. 1 并行編譯技術(shù)的引入…………………………………………………………………… 189
10. 2 并行編譯系統(tǒng)的功能和結(jié)構(gòu) …………………………………………………………… 190
10.2.1 并行編譯系統(tǒng)的功能 …………………………………………………………… 190
10.2.2 并行編譯系統(tǒng)的結(jié)構(gòu) …………………………………………………………… 190
10. 3 向量語(yǔ)言編譯技術(shù) …………………………………………………………………… 191
10. 3.1 向量語(yǔ)法處理…………………………………………………………………… 191
10.3.2 向量結(jié)構(gòu)優(yōu)化…………………………………………………………………… 191
10.4 共享存儲(chǔ)器并行機(jī)并行編譯技術(shù) ……………………………………………………… 192
10.4. 1 預(yù)編譯 ………………………………………………………………………… 192
10.4.2 可再入的目標(biāo)代碼 ……………………………………………………………… 192
本章小結(jié) …………………………………………………………………………………… 193
習(xí)題 10 ………………………………………………………………………………………193
附錄 A 詞法分析程序生成器 Lex ………………………………………………………… 194
A.1 詞法分析程序生成器 Lex 簡(jiǎn)介 ………………………………………………………… 194
A.2 Lex 輸入文件的格式 …………………………………………………………………… 195
A.3 正規(guī)表達(dá)式的 Lex 約定 ………………………………………………………………… 197
A.4 Lex 源程序中的規(guī)則部分 ……………………………………………………………… 199
A. 5 Flex 的命令選項(xiàng)………………………………………………………………………… 201
A.6 Lex 程序示例 ……………………………………………………………………………202
附錄 B 語(yǔ)法分析程序生成器 YACC ………………………………………………………203
B. 1 語(yǔ)法分析程序 YACC 簡(jiǎn)介 ……………………………………………………………… 203
B.2 YACC 輸入文件的格式 ………………………………………………………………… 203
B.3 YACC 各部分的書(shū)寫(xiě)格式 ……………………………………………………………… 204
B. 3. 1 定義部分………………………………………………………………………… 204
B. 3.2 規(guī)則部分………………………………………………………………………… 207
B.3.3 輔助程序部分 …………………………………………………………………… 209
B.4 YACC 的內(nèi)置名稱和定義機(jī)制…………………………………………………………… 209
B.5 Flex 與 Bison 的聯(lián)合使用 ………………………………………………………………209
附錄 C 編譯程序?qū)嶒?yàn) …………………………………………………………………………212
C.1 詞法分析 ……………………………………………………………………………… 212
C.1.1 實(shí)驗(yàn)?zāi)康摹?212
C.1.2 實(shí)驗(yàn)要求………………………………………………………………………… 212
C.1.3 詞法分析程序的算法思想………………………………………………………… 213
C.1.4 詞法分析程序的 C 語(yǔ)言程序框架 ………………………………………………… 214
C. 2 語(yǔ)法分析 ……………………………………………………………………………… 219
C.2. 1 實(shí)驗(yàn)?zāi)康摹?219
C.2.2 實(shí)驗(yàn)要求………………………………………………………………………… 219
C.2.3 語(yǔ)法分析程序的算法思想………………………………………………………… 219
C 2.4 語(yǔ)法分析程序的 C 語(yǔ)言程序框架 ………………………………………………… 221
C.3 語(yǔ)義分析 ……………………………………………………………………………… 222
C.3.1 實(shí)驗(yàn)?zāi)康摹?222
C.3.2 實(shí)驗(yàn)要求………………………………………………………………………… 222
C.3.3 語(yǔ)義分析程序的 C 語(yǔ)言程序框架 ………………………………………………… 223
C.4 算符優(yōu)先分析法………………………………………………………………………… 225
C.5 實(shí)驗(yàn)實(shí)例 ……………………………………………………………………………… 226
C.6 正規(guī)式轉(zhuǎn)換成自動(dòng)機(jī)的圖形表示………………………………………………………… 244
C.6.1 實(shí)驗(yàn)?zāi)康摹?244
C. 6.2 實(shí)驗(yàn)要求………………………………………………………………………… 244
C.6.3 參考設(shè)計(jì)思路 …………………………………………………………………… 244
C.6.4 參考算法 …………………………………………………………………………245
附錄 D 自測(cè)練習(xí)題與習(xí)題參考答案 …………………………………………………………248
參考文獻(xiàn)………………………………………………………………………………………… 269
書(shū)單推薦
