編譯原理

第1章 編譯程序概論 1
1.1 什么是編譯程序 1
1.2 編譯過程和編譯程序的結構 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 編譯階段的組合和編譯結構 9
1.3 實例：PL/0編譯程序 10
1.3.1 PL/0語言簡介 10
1.3.2 PL/0語言處理系統(tǒng) 11
習題 13
第2章 語言和文法 14
2.1 語言的基本概念 14
2.1.1 字母表和字 14
2.1.2 關于字的運算和字母表上的運算 14
2.1.3 語言 15
2.1.4 關于語言的運算 15
2.2 上下文無關文法 16
2.2.1 上下文無關文法的基本概念 16
2.2.2 歸約與推導 17
2.2.3 上下文無關語言 18
2.2.4 句型、句子與分析樹 20
2.2.5 歸約、推導與分析樹之間關系 20
2.2.6 文法的二義性 21
2.3 PL/0語言的語法 25
2.3.1 PL/0語言語法的上下文無關文法描述 25
2.3.2 PL/0語言語法的EBNF描述 26
習題 28
第3章 詞法分析程序及其自動構造 31
3.1 詞法分析概述 31
3.1.1 詞法分析的任務 31
3.1.2 詞法分析在編譯程序中的組織 32
3.1.3 詞法分析程序中如何識別單詞 33
3.2 實例：PL/0編譯程序中詞法分析程序的設計和實現(xiàn) 33
3.3 詞法分析程序自動構造原理 37
3.3.1 正規(guī)表達式與正規(guī)語言 37
3.3.2 有限自動機 40
3.3.3 詞法分析程序構造的自動化 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構造PL/0詞法分析程序 57
習題 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編譯程序中語法分析程序的設計和實現(xiàn) 76
4.3.1 PL/0語法分析程序的自頂向下預測分析思想 76
4.3.2 PL/0遞歸下降語法分析程序的設計 78
4.3.3 PL/0編譯程序中的錯誤處理 80
習題 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分析基礎 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 幾類分析文法之間的關系 113
習題 113
第6章 語法制導的語義分析和中間代碼生成 118
6.1 語法制導的語義處理基礎 118
6.1.1 屬性文法以及基于屬性文法的語義處理 118
6.1.2 翻譯模式以及基于翻譯模式的語義處理 127
6.2 語法制導的語義分析 133
6.2.1 語義分析的主要工作 134
6.2.2 類型檢查 134
6.3 語法制導的中間代碼生成 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
習題 152
第7章 符號表 158
7.1 名字的屬性和說明 158
7.2 符號表的組織 159
7.2.1 符號表的總體組織 159
7.2.2 關鍵字域的組織 160
7.2.3 符號表的基本實現(xiàn)技術 160
7.3 分程序結構的符號表 161
7.4 PL/0編譯程序中符號表的設計與實現(xiàn) 164
7.4.1 PL/0符號表的設計 164
7.4.2 作用域與可見性 166
7.4.3 符號表的操作 168
習題 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 形實參對應的方法 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)過程調用和返回的類P-code指令 185
習題 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 跟蹤基本塊內部變量使用信息 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 設計代碼生成程序的基本考慮 207
9.3.2 一個簡單的代碼生成算法 209
9.3.3 目標代碼優(yōu)化 211
9.4 PL/0編譯程序中的目標代碼生成 212
習題 214
第10章 編譯器和相關工具實例——GCC/Binutils 217
10.1 開源編譯器GCC 217
10.1.1 GCC介紹 218
10.1.2 GCC總體結構 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
習題 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