編譯原理

第1章 編譯程序概論 1
1.1 什么是編譯程序 1
1.2 編譯過(guò)程和編譯程序的結(jié)構(gòu) 3
1.2.1 詞法分析 3
1.2.2 語(yǔ)法分析 4
1.2.3 語(yǔ)義分析 5
1.2.4 中間代碼生成 6
1.2.5 代碼優(yōu)化 6
1.2.6 目標(biāo)代碼生成 6
1.2.7 符號(hào)表管理和出錯(cuò)處理 7
1.2.8 編譯階段的組合和編譯結(jié)構(gòu) 9
1.3 實(shí)例：PL/0編譯程序 10
1.3.1 PL/0語(yǔ)言簡(jiǎn)介 10
1.3.2 PL/0語(yǔ)言處理系統(tǒng) 11
習(xí)題 13
第2章 語(yǔ)言和文法 14
2.1 語(yǔ)言的基本概念 14
2.1.1 字母表和字 14
2.1.2 關(guān)于字的運(yùn)算和字母表上的運(yùn)算 14
2.1.3 語(yǔ)言 15
2.1.4 關(guān)于語(yǔ)言的運(yùn)算 15
2.2 上下文無(wú)關(guān)文法 16
2.2.1 上下文無(wú)關(guān)文法的基本概念 16
2.2.2 歸約與推導(dǎo) 17
2.2.3 上下文無(wú)關(guān)語(yǔ)言 18
2.2.4 句型、句子與分析樹(shù) 20
2.2.5 歸約、推導(dǎo)與分析樹(shù)之間關(guān)系 20
2.2.6 文法的二義性 21
2.3 PL/0語(yǔ)言的語(yǔ)法 25
2.3.1 PL/0語(yǔ)言語(yǔ)法的上下文無(wú)關(guān)文法描述 25
2.3.2 PL/0語(yǔ)言語(yǔ)法的EBNF描述 26
習(xí)題 28
第3章 詞法分析程序及其自動(dòng)構(gòu)造 31
3.1 詞法分析概述 31
3.1.1 詞法分析的任務(wù) 31
3.1.2 詞法分析在編譯程序中的組織 32
3.1.3 詞法分析程序中如何識(shí)別單詞 33
3.2 實(shí)例：PL/0編譯程序中詞法分析程序的設(shè)計(jì)和實(shí)現(xiàn) 33
3.3 詞法分析程序自動(dòng)構(gòu)造原理 37
3.3.1 正規(guī)表達(dá)式與正規(guī)語(yǔ)言 37
3.3.2 有限自動(dòng)機(jī) 40
3.3.3 詞法分析程序構(gòu)造的自動(dòng)化 52
3.4 LEX：一個(gè)詞法分析程序的生成工具 52
3.4.1 LEX描述文件中使用的正規(guī)表達(dá)式 53
3.4.2 LEX描述文件的格式 54
3.4.3 LEX的使用 56
3.4.4 與YACC的接口約定 56
3.4.5 用LEX構(gòu)造PL/0詞法分析程序 57
習(xí)題 57
第4章 自頂向下語(yǔ)法分析 60
4.1 自頂向下分析思想 60
4.2 LL（1）分析方法 63
4.2.1 First集合和Follow集合 63
4.2.2 LL（1）文法 66
4.2.3 LL（1）分析的實(shí)現(xiàn) 66
4.2.4 一些有用的文法變換 72
4.3 實(shí)例：PL/0編譯程序中語(yǔ)法分析程序的設(shè)計(jì)和實(shí)現(xiàn) 76
4.3.1 PL/0語(yǔ)法分析程序的自頂向下預(yù)測(cè)分析思想 76
4.3.2 PL/0遞歸下降語(yǔ)法分析程序的設(shè)計(jì) 78
4.3.3 PL/0編譯程序中的錯(cuò)誤處理 80
習(xí)題 82
第5章 自底向上語(yǔ)法分析 85
5.1 自底向上分析思想 85
5.1.1 短語(yǔ)和直接短語(yǔ) 86
5.1.2 句柄 87
5.1.3 移進(jìn)-歸約分析 89
5.2 LR分析方法 92
5.2.1 LR分析基礎(chǔ) 92
5.2.2 LR（0）分析 95
5.2.3 SLR（1）分析 100
5.2.4 LR（1）分析 102
5.2.5 LALR（1）分析 107
5.2.6 某些非LR文法的強(qiáng)制LR分析 109
5.3 LR分析中的錯(cuò)誤處理 111
5.4 幾類(lèi)分析文法之間的關(guān)系 113
習(xí)題 113
第6章 語(yǔ)法制導(dǎo)的語(yǔ)義分析和中間代碼生成 118
6.1 語(yǔ)法制導(dǎo)的語(yǔ)義處理基礎(chǔ) 118
6.1.1 屬性文法以及基于屬性文法的語(yǔ)義處理 118
6.1.2 翻譯模式以及基于翻譯模式的語(yǔ)義處理 127
6.2 語(yǔ)法制導(dǎo)的語(yǔ)義分析 133
6.2.1 語(yǔ)義分析的主要工作 134
6.2.2 類(lèi)型檢查 134
6.3 語(yǔ)法制導(dǎo)的中間代碼生成 137
6.3.1 常見(jiàn)的中間表示形式 137
6.3.2 生成抽象語(yǔ)法樹(shù) 138
6.3.3 生成三地址碼 139
6.4 YACC：一個(gè)語(yǔ)法分析/語(yǔ)義處理程序的生成工具 147
6.4.1 YACC描述文件 147
6.4.2 使用YACC的一個(gè)簡(jiǎn)單例子 151
6.4.3 用LEX和YACC實(shí)現(xiàn)PL/0編譯程序 152
習(xí)題 152
第7章 符號(hào)表 158
7.1 名字的屬性和說(shuō)明 158
7.2 符號(hào)表的組織 159
7.2.1 符號(hào)表的總體組織 159
7.2.2 關(guān)鍵字域的組織 160
7.2.3 符號(hào)表的基本實(shí)現(xiàn)技術(shù) 160
7.3 分程序結(jié)構(gòu)的符號(hào)表 161
7.4 PL/0編譯程序中符號(hào)表的設(shè)計(jì)與實(shí)現(xiàn) 164
7.4.1 PL/0符號(hào)表的設(shè)計(jì) 164
7.4.2 作用域與可見(jiàn)性 166
7.4.3 符號(hào)表的操作 168
習(xí)題 169
第8章 目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織 171
8.1 數(shù)據(jù)空間的使用和管理方法 171
8.1.1 靜態(tài)存儲(chǔ)分配 172
8.1.2 動(dòng)態(tài)存儲(chǔ)分配 172
8.2 棧式存儲(chǔ)分配的實(shí)現(xiàn) 173
8.2.1 動(dòng)態(tài)地分配和釋放一個(gè)過(guò)程的數(shù)據(jù)空間 174
8.2.2 對(duì)非局部變量的引用 175
8.2.3 分程序共享過(guò)程的活動(dòng)記錄 179
8.3 參數(shù)傳遞 180
8.3.1 形實(shí)參對(duì)應(yīng)的方法 181
8.3.2 傳值的實(shí)現(xiàn) 181
8.3.3 傳地址的實(shí)現(xiàn) 182
8.4 PL/0程序運(yùn)行時(shí)的存儲(chǔ)組織 183
8.4.1 PL/0程序運(yùn)行棧中的過(guò)程活動(dòng)記錄 183
8.4.2 實(shí)現(xiàn)過(guò)程調(diào)用和返回的類(lèi)P-code指令 185
習(xí)題 186
第9章 代碼優(yōu)化和代碼生成 189
9.1 基本塊和流圖 191
9.1.1 基本塊 191
9.1.2 控制流圖 192
9.1.3 循環(huán)的判定 193
9.1.4 跟蹤基本塊內(nèi)部變量使用信息 194
9.1.5 跟蹤基本塊之間變量使用信息 196
9.2 中間代碼優(yōu)化 200
9.2.1 局部?jī)?yōu)化 200
9.2.2 循環(huán)優(yōu)化 202
9.2.3 全局優(yōu)化 205
9.3 目標(biāo)代碼的生成和優(yōu)化 207
9.3.1 設(shè)計(jì)代碼生成程序的基本考慮 207
9.3.2 一個(gè)簡(jiǎn)單的代碼生成算法 209
9.3.3 目標(biāo)代碼優(yōu)化 211
9.4 PL/0編譯程序中的目標(biāo)代碼生成 212
習(xí)題 214
第10章 編譯器和相關(guān)工具實(shí)例——GCC/Binutils 217
10.1 開(kāi)源編譯器GCC 217
10.1.1 GCC介紹 218
10.1.2 GCC總體結(jié)構(gòu) 219
10.1.3 GCC編譯流程 220
10.1.4 GCC代碼組織 221
10.2 開(kāi)源工具Binutils 222
10.2.1 目標(biāo)文件 222
10.2.2 匯編器和鏈接器 223
10.2.3 其他工具 224
10.3 編譯器和工具使用實(shí)例 224
10.3.1 編譯特定版本的編譯器 224
10.3.2 查看目標(biāo)文件 227
10.3.3 程序代碼優(yōu)化 229
習(xí)題 232
附錄A PL/0編譯程序文本 233
附錄A-1 PL/0編譯程序文本（Pascal） 233
附錄A-2 PL/0編譯程序文本（C） 250
附錄B 用于生成某個(gè)PL/0編譯程序的LEX描述文件和YACC描述文件 279
附錄B-1 LEX描述文件pl0.l 279
附錄B-2 YACC描述文件pl0.y 280
附錄B-3 頭文件define.h 292
參考文獻(xiàn) 293