編譯原理

目錄
第1篇 構(gòu)思(Conceive)
第1章 編譯程序概論 3
1.1 編譯程序的概念 3
1.1.1 程序設(shè)計(jì)語(yǔ)言 3
1.1.2 基本概念和術(shù)語(yǔ) 4
1.1.3 程序設(shè)計(jì)語(yǔ)言的翻譯 4
1.1.4 高級(jí)語(yǔ)言程序的執(zhí)行 5
1.2 編譯過(guò)程 6
1.3 編譯程序的結(jié)構(gòu) 8
1.3.1 詞法分析程序 10
1.3.2 語(yǔ)法分析程序 11
1.3.3 語(yǔ)義分析程序 12
1.3.4 中間代碼生成程序 12
1.3.5 代碼優(yōu)化程序 13
1.3.6 目標(biāo)代碼生成程序 14
1.3.7 信息表管理程序 15
1.3.8 錯(cuò)誤檢查和處理程序 16
1.3.9 編譯程序的分遍 17
1.4 解釋程序 18
1.5 編譯程序的評(píng)價(jià)指標(biāo)與構(gòu)造技術(shù) 19
1.5.1 編譯程序的評(píng)價(jià)指標(biāo) 20
1.5.2 編譯程序的構(gòu)造技術(shù) 21
1.6 程序設(shè)計(jì)語(yǔ)言范型 24
習(xí)題 26
第2章 文法和語(yǔ)言 27
2.1 符號(hào)和符號(hào)串 27
2.2 文法和語(yǔ)言的定義 29
2.3 文法的類型 35
2.4 上下文無(wú)關(guān)文法及其語(yǔ)法樹(shù) 37
2.4.1 程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)的描述 37
2.4.2 語(yǔ)法樹(shù) 38
2.4.3 文法的二義性 39
2.5 句型的分析 41
2.5.1 規(guī)范推導(dǎo)和規(guī)范歸約 41
2.5.2 短語(yǔ)和句柄 43
2.6 文法描述語(yǔ)言時(shí)的限制與擴(kuò)充 46
2.6.1 文法描述語(yǔ)言時(shí)的限制 46
2.6.2 文法描述語(yǔ)言時(shí)的擴(kuò)充 47
習(xí)題 48
第2篇 設(shè)計(jì)(Design)
第3章 詞法分析 53
3.1 詞法分析概述 53
3.2 詞法分析器的結(jié)構(gòu) 53
3.2.1 詞法分析器的工作方式 53
3.2.2 詞法分析器的輸出 54
3.2.3 詞法分析作為一個(gè)*立階段的原因 55
3.3 單詞的描述工具 55
3.3.1 正規(guī)文法 56
3.3.2 正規(guī)式 56
3.3.3 正規(guī)文法和正規(guī)式的等價(jià)性 58
3.4 有限自動(dòng)機(jī) 60
3.4.1 確定的有限自動(dòng)機(jī)(DFA) 60
3.4.2 不確定的有限自動(dòng)機(jī)(NFA) 62
3.4.3 NFA轉(zhuǎn)換為等價(jià)的DFA 63
3.4.4 確定有限自動(dòng)機(jī)的化簡(jiǎn) 66
3.5 正規(guī)式和有限自動(dòng)機(jī)的等價(jià)性 68
3.6 正規(guī)文法和有限自動(dòng)機(jī)的等價(jià)性 71
3.7 詞法分析器的自動(dòng)構(gòu)造工具 73
習(xí)題 75
實(shí)踐項(xiàng)目一 76
第4章 自頂向下語(yǔ)法分析 77
4.1 自頂向下語(yǔ)法分析概述 77
4.2 遞歸下降分析法 78
4.3 LL(1)預(yù)測(cè)分析法 80
4.4 非LL(1)文法到LL(1)文法的等價(jià)變換 83
4.4.1 提取左公共因子 83
4.4.2 消除左遞歸 84
4.4.3 消除文法左遞歸的方法 86
4.5 LL的自動(dòng)生成工具 88
4.5.1 遞歸子程序法 88
4.5.2 預(yù)測(cè)分析方法 90
案例分析 91
習(xí)題 93
實(shí)踐項(xiàng)目二 95
第5章 自底向上語(yǔ)法分析 96
5.1 自底向上語(yǔ)法分析概述 96
5.2 算符優(yōu)先分析 97
5.2.1 算符優(yōu)先文法的定義 97
5.2.2 算符優(yōu)先關(guān)系表的構(gòu)造 99
5.2.3 *左素短語(yǔ) 101
5.2.4 優(yōu)先函數(shù) 103
5.3 LR分析 104
5.3.1 LR分析器概述 105
5.3.2 LR(0)分析 106
5.3.3 SLR(1)分析 113
5.3.4 LR(1)分析 114
5.3.5 LALR(1)分析 114
5.4 LR的自動(dòng)生成工具 115
案例分析 115
習(xí)題 120
實(shí)踐項(xiàng)目三 121
第6章 語(yǔ)義分析與符號(hào)表 122
6.1 語(yǔ)義分析概述 122
6.2 符號(hào)表的作用 122
6.3 符號(hào)表的內(nèi)容 123
6.4 符號(hào)表的組織 128
6.5 符號(hào)表的管理 135
習(xí)題 137
第3篇 實(shí)現(xiàn)(Implement)
第7章 語(yǔ)法制導(dǎo)翻譯與中間代碼生成 141
7.1 語(yǔ)法制導(dǎo)翻譯 141
7.1.1 屬性文法 141
7.1.2 語(yǔ)法翻譯概述 141
7.2 中間代碼表示 143
7.2.1 逆波蘭式 143
7.2.2 三地址代碼 144
7.2.3 四元式表示 145
7.2.4 其他表示 146
7.3 簡(jiǎn)單賦值語(yǔ)句的翻譯 146
7.4 布爾表達(dá)式的翻譯 147
7.5 控制語(yǔ)句的翻譯 149
習(xí)題 151
實(shí)踐項(xiàng)目四 153
第8章 目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織 154
8.1 存儲(chǔ)組織及管理 154
8.2 靜態(tài)存儲(chǔ)分配策略 155
8.3 動(dòng)態(tài)存儲(chǔ)分配 157
8.3.1 過(guò)程與活動(dòng)記錄 157
8.3.2 簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn) 159
8.3.3 嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn) 159
習(xí)題 161
第9章 出錯(cuò)處理 163
9.1 錯(cuò)誤分類 163
9.1.1 語(yǔ)法錯(cuò)誤 163
9.1.2 語(yǔ)義錯(cuò)誤 163
9.2 編譯程序中參數(shù)錯(cuò)誤的處理 164
9.2.1 校正法 164
9.2.2 局部化法 165
9.2.3 參數(shù)FSYS集合內(nèi)容的補(bǔ)充 168
9.3 一些語(yǔ)義錯(cuò)誤的處理 169
9.3.1 遏止株連錯(cuò)誤 169
9.3.2 遏止重復(fù)錯(cuò)誤 169
習(xí)題 170
實(shí)踐項(xiàng)目五 171
第10章 代碼優(yōu)化 172
10.1 優(yōu)化技術(shù)簡(jiǎn)介 172
10.1.1 刪除多余運(yùn)算 172
10.1.2 復(fù)寫(xiě)傳播 173
10.1.3 無(wú)用代碼刪除 173
10.1.4 代碼外提 173
10.1.5 強(qiáng)度削弱和基本歸納變量刪除 174
10.2 局部?jī)?yōu)化 175
10.2.1 基本塊 175
10.2.2 基本塊的有向無(wú)環(huán)圖表示 176
10.2.3 基于基本塊的優(yōu)化 179
10.3 循環(huán)優(yōu)化 180
10.3.1 流圖 180
10.3.2 循環(huán) 180
10.3.3 循環(huán)不變計(jì)算及代碼外提 183
10.3.4 歸納變量相關(guān)的優(yōu)化 186
10.4 全局優(yōu)化 188
10.4.1 全局公共子表達(dá)式 188
10.4.2 復(fù)寫(xiě)傳播 188
習(xí)題 190
實(shí)踐項(xiàng)目六 192
第11章 目標(biāo)代碼生成 193
11.1 目標(biāo)代碼生成概述 193
11.1.1 代碼生成器的輸入 193
11.1.2 目標(biāo)代碼的形式 193
11.1.3 指令選擇 194
11.1.4 寄存器分配 194
11.1.5 計(jì)算順序的選擇 195
11.2 常用的代碼生成器的開(kāi)發(fā)方法 195
11.2.1 解釋性代碼生成法 195
11.2.2 模式匹配代碼生成法 196
11.2.3 表驅(qū)動(dòng)代碼生成法 196
習(xí)題 197
第4篇 運(yùn)作(Operate)
第12章 寄存器分配 201
12.1 寄存器分配概述 201
12.2 寄存器分配圖染色法 202
12.3 合并 204
12.4 預(yù)著色的結(jié)點(diǎn) 206
12.5 圖著色的實(shí)現(xiàn) 207
12.6 針對(duì)樹(shù)的寄存器分配 208
習(xí)題 212
第13章 垃圾回收 213
13.1 垃圾收集概述 213
13.2 引用計(jì)數(shù) 214
13.3 復(fù)制式收集 215
13.4 分代收集 217
13.5 增量式收集 218
13.6 編譯器接口 219
習(xí)題 221
第14章 面向?qū)ο笳Z(yǔ)言編譯器 222
14.1 面向?qū)ο笳Z(yǔ)言概述 222
14.2 類與繼承 223
14.3 私有域和私有方法 224
14.4 面向?qū)ο笳Z(yǔ)言的翻譯 225
14.4.1 單繼承的編譯方案 225
14.4.2 多繼承的編譯方案 227
14.5 面向?qū)ο笳Z(yǔ)言的編譯優(yōu)化 228
習(xí)題 230
第15章 人工智能編譯器 231
15.1 人工智能編程語(yǔ)言概述 231
15.1.1 Python 231
15.1.2 R 232
15.1.3 LISP 233
15.1.4 Prolog 233
15.2 Python虛擬機(jī)基本原理 233
15.2.1 過(guò)程概述 233
15.2.2 關(guān)于.pyc文件 234
15.2.3 關(guān)于PyCodeObject 234
15.2.4 執(zhí)行字節(jié)碼 235
15.2.5 Python字節(jié)碼 236
15.3 代碼自動(dòng)生成與抽象語(yǔ)法樹(shù) 237
習(xí)題 239
參考文獻(xiàn) 240