21世紀高等學校計算機規劃教材‧名家系列：編譯原理

《編譯原理》主要介紹編譯系統的一般構造原理和基本實現技術。內容包括語言基礎知識、詞法分析、語法分析、中間代碼生成、代碼優化、目標代碼生成、符號表的構造和運行時存儲空間的組織等，同時將「PL/0語言編譯程序」的設計作為實例貫穿於相關章節中。最後還通過一系列程序實例介紹了工業界廣泛使用的開源工具GCC和Binutils。

第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 代碼優化 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語言處理系統 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編譯程序中詞法分析程序的設計和實現 33
3.3 詞法分析程序自動構造原理 37
3.3.1 正規表達式與正規語言 37
3.3.2 有限自動機 40
3.3.3 詞法分析程序構造的自動化 52
3.4 LEX：一個詞法分析程序的生成工具 52
3.4.1 LEX描述文件中使用的正規表達式 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）分析的實現 66
4.2.4 一些有用的文法變換 72
4.3 實例：PL/0編譯程序中語法分析程序的設計和實現 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實現PL/0編譯程序 152
習題 152

第7章 符號表 158
7.1 名字的屬性和說明 158
7.2 符號表的組織 159
7.2.1 符號表的總體組織 159
7.2.2 關鍵字域的組織 160
7.2.3 符號表的基本實現技術 160
7.3 分程序結構的符號表 161
7.4 PL/0編譯程序中符號表的設計與實現 164
7.4.1 PL/0符號表的設計 164
7.4.2 作用域與可見性 166
7.4.3 符號表的操作 168
習題 169

第8章 目標程序運行時的存儲組織 171
8.1 數據空間的使用和管理方法 171
8.1.1 靜態存儲分配 172
8.1.2 動態存儲分配 172
8.2 棧式存儲分配的實現 173
8.2.1 動態地分配和釋放一個過程的數據空間 174
8.2.2 對非局部變量的引用 175
8.2.3 分程序共享過程的活動記錄 179
8.3 參數傳遞 180
8.3.1 形實參對應的方法 181
8.3.2 傳值的實現 181
8.3.3 傳地址的實現 182
8.4 PL/0程序運行時的存儲組織 183
8.4.1 PL/0程序運行棧中的過程活動記錄 183
8.4.2 實現過程調用和返回的類P-code指令 185
習題 186

第9章 代碼優化和代碼生成 189
9.1 基本塊和流圖 191
9.1.1 基本塊 191
9.1.2 控制流圖 192
9.1.3 循環的判定 193
9.1.4 跟蹤基本塊內部變量使用信息 194
9.1.5 跟蹤基本塊之間變量使用信息 196
9.2 中間代碼優化 200
9.2.1 局部優化 200
9.2.2 循環優化 202
9.2.3 全局優化 205
9.3 目標代碼的生成和優化 207
9.3.1 設計代碼生成程序的基本考慮 207
9.3.2 一個簡單的代碼生成算法 209
9.3.3 目標代碼優化 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 程序代碼優化 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