編譯原理

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