編譯原理（簡體書）

本書系統地闡述了編譯原理的一般理論、常用方法和實現技術。主要內容包括形式語言基礎知識、詞法分析、語法分析、中間代碼生成、代碼優化、目標代碼生成、符號表的構造和運行時存儲空間的組織等部分。本書系統性強，內容循序漸進，實例豐富。對算法的描述深入淺出，文字簡練，通俗易懂。每章都配有各種類型的習題。

長春工業大學軟件學院教授，博士；美國ACM會員，中國計算機學會CCF會員，吉林省省政府政務大廳評標專家；發表學術論文30餘篇，其中SCI、EI檢索20餘篇；完成專著2部，出版教材近10部。

編譯技術是計算語言發展的支柱，也是計算機科學中發展最迅速、最成熟的一個分支。“編譯原理”是一門研究設計和構造編譯程序的原理和方法的課程，是計算機及其相關專業的一門核心課程，在教學中佔有極其重要的地位。該課程蘊涵著計算機學科中解決問題的思路、形式化問題和解決問題的方法。編譯程序是計算機系統軟件的重要組成部分，其基本原理和實現技術也適用於一般軟件的設計和實現，因此對應用軟件和系統軟件的設計與開發有一定的啟發和重要的指導作用，在軟件工程、軟件自動化、語言轉換、程序分析及其他領域具有廣泛的應用。本書主要介紹設計和構造編譯程序的一般原理、基本方法和主要實現技術。通過該課程的學習，使學生掌握編譯系統的結構、工作流程及編譯程序各組成部分的設計原理和常用的編譯技術及方法，為今後從事應用軟件和系統軟件的開發奠定一定的理論和實踐基礎。
本書共分9章。第1章介紹了編譯程序的基礎知識，包括編譯工作的基本過程及各階段的基本任務；第2章介紹了文法及語言的基本概念、文法分類、詞法分析程序的設計原理與構造方法等；第3章介紹了自頂向下語法分析的基本思想和分析技術，包括語法分析的任務、LL(1)文法、LL(1)分析法和遞歸下降分析法；第4章介紹了自底向上語法分析的基本思想和分析技術，包括算符優先分析、LR分析法等；第5章介紹了語義分析與中間代碼的生成；第6章介紹了符號表的組織與管理，包括符號表的作用、符號表的組織和使用方法；第7章介紹了運行時的存儲組織與分配技術；第8章介紹了代碼優化的基本概念、基本塊的劃分、局部優化和循環優化方法等；第9章介紹了目標代碼生成的基本技術。
本書系統性強，概念清晰，內容簡明通俗，每章章首配有本章的學習目標和學習要求，章末配有本章小結和適量的習題，可使學習者快速掌握書中的內容。本書附錄中的程序代碼可掃相應的二維碼查看，或者登錄華信教育資源網www.hxedu.com.cn註冊後下載。
本書根據作者多年的教學經驗編寫而成，在成書的過程中，編著參考了書末所列出的有關文獻，在此，向這些書籍的作者一併表示感謝。由於編著者水平有限，時間倉促，書中難免存在一些缺點和不足，敬請讀者多提寶貴意見，以便再做修訂補充。

編著者

第1章 編譯簡述 1
1.1 程序的翻譯 1
1.1.1 程序設計語言 1
1.1.2 編譯程序 2
1.1.3 實現高級語言的編譯方式 2
1.2 編譯程序的組成 3
1.2.1 編譯程序的構成 4
1.2.2 遍 5
1.2.3 編譯程序前端和後端 5
1.3 編譯程序的構造 5
1.4 小結 6
複習思考題 7
第2章 形式語言與詞法分析 8
2.1 字母表和符號串的基本概念 8
2.1.1 字母表和符號串 9
2.1.2 符號串的運算 10
2.2 文法和語言的形式定義 11
2.2.1 形式語言 12
2.2.2 文法的形式定義 13
2.2.3 語言的形式定義 14
2.3 語法樹與文法二義性 17
2.3.1 語法樹 17
2.3.2 文法二義性 18
2.4 文法和語言的分類 19
2.5 詞法分析的任務 20
2.5.1 詞法分析的任務描述 20
2.5.2 詞法分析器與語法分析器的接口 20
2.6 詞法分析程序的輸出形式 21
2.6.1 單詞符號的分類 21
2.6.2 詞法分析程序單詞的輸出形式 22
2.6.3 詞法錯誤 23
2.7 詞法分析程序的設計與實現 24
2.7.1 輸入和預處理功能 24
2.7.2 單詞符號的識別 25
2.7.3 狀態轉換圖 26
2.7.4 狀態轉換圖的實現 26
2.8 正規表達式與有限自動機 27
2.8.1 正規表達式與正規集 28
2.8.2 有限自動機 31
2.9 詞法分析程序的自動生成工具Lex 40
2.10 實例語言的詞法分析程序 43
2.10.1 微小語言Micro 43
2.10.2 Micro的詞法分析 43
2.11 小結 45
複習思考題 46
第3章 自頂向下語法分析 50
3.1 自頂向下分析的一般方法 51
3.2 LL(1)文法 52
3.2.1 消除左遞歸 52
3.2.2 提取左因子 53
3.3 遞歸下降分析法 58
3.4 LL(1)分析法 60
3.4.1 非遞歸預測分析器 60
3.4.2 構造預測分析表 62
3.5 預測分析中的錯誤處理 63
3.6 小結 64
複習思考題 64
第4章 自底向上語法分析 66
4.1 自底向上分析的基本概念 66
4.1.1 歸約 66
4.1.2 句柄 67
4.1.3 用棧實現自底向上分析 68
4.1.4 移進-歸約分析的衝突 69
4.2 算符優先分析 70
4.2.1 直觀算符優先分析法 71
4.2.2 算符優先文法的定義 73
4.2.3 算符優先關係表的構造 74
4.2.4 算符優先分析算法 75
4.2.5 優先函數 76
4.2.6 算符優先分析法的局限性 78
4.3 LR分析法 78
4.3.1 LR分析算法 79
4.3.2 LR文法和LR分析方法的特點 81
4.3.3 構造LR(0)分析表 82
4.3.4 構造SLR(1)分析表 88
4.3.5 構造規範的LR分析表 92
4.3.6 構造LALR分析表 95
4.3.7 二義文法的應用 97
4.4 語法分析程序的自動生成工具YACC 101
4.5 實例語言編譯程序的語法分析 104
4.6 小結 106
複習思考題 107
第5章 語義分析與中間代碼的生成 110
5.1 語義分析的任務 110
5.1.1 語義分析的概念 110
5.1.2 語義分析的任務 111
5.2 語法制導翻譯 111
5.2.1 屬性文法 111
5.2.2 語法制導翻譯方法 111
5.3 中間代碼 112
5.3.1 逆波蘭表示法 112
5.3.2 四元式 112
5.3.3 三元式 113
5.3.4 間接三元式 113
5.3.5 抽象語法樹 114
5.4 說明語句的翻譯 114
5.4.1 簡單說明語句的翻譯 114
5.4.2 過程中的說明 115
5.5 賦值語句的翻譯 115
5.5.1 簡單算術表達式和賦值語句的翻譯 115
5.5.2 數組的翻譯 117
5.6 布爾表達式的翻譯 117
5.7 控制語句的翻譯 120
5.7.1 條件語句if的翻譯 121
5.7.2 循環語句while的翻譯 122
5.7.3 三種基本控制結構的翻譯 123
5.8 過程調用的翻譯 124
5.9 實例編譯程序的語義分析 125
5.10 小結 127
複習思考題 127
第6章 符號表管理 131
6.1 符號表的作用 131
6.1.1 收集標識符屬性信息 131
6.1.2 符號表內容為上下文語義的合法性檢查提供依據 132
6.1.3 作為目標代碼生成階段編譯程序分配地址空間的依據 132
6.2 符號表的主要內容 132
6.2.1 符號名 132
6.2.2 符號的類型 133
6.2.3 符號的存儲類型 133
6.2.4 符號的作用域及可視性 133
6.2.5 符號變量的存儲分配信息 134
6.2.6 符號的其他屬性 136
6.3 符號表的組織 136
6.3.1 符號表的總體組織 136
6.3.2 符號表項的組織 138
6.4 符號表的管理 142
6.4.1 符號表的初始化 142
6.4.2 符號的插入 143
6.4.3 符號的查找 145
6.5 小結 146
複習思考題 146
第7章 運行時的存儲組織與分配 147
7.1 存儲組織概述 147
7.1.1 運行時內存的劃分 147
7.1.2 過程活動記錄 149
7.2 靜態存儲分配 150
7.3 棧式動態存儲分配 151
7.3.1 棧的結構 151
7.3.2 活動樹和簡單的棧式存儲分配 151
7.3.3 嵌套過程語言的棧式實現 153
7.4 堆式動態存儲分配 154
7.5 小結 156
複習思考題 156
第8章 代碼優化 158
8.1 局部優化 159
8.1.1 基本塊的劃分 159
8.1.2 利用基本塊DAG進行優化 162
8.2 循環優化 166
8.2.1 程序流圖 166
8.2.2 循環的查找 167
8.2.3 循環優化 169
8.3 小結 171
複習思考題 171
第9章 目標代碼生成 173
9.1 目標代碼的形式 173
9.2 假想的計算機模型 174
9.3 一個簡單的代碼生成程序 175
9.3.1 待用信息和活躍信息 175
9.3.2 寄存器描述和地址描述 175
9.3.3 代碼生成算法 176
9.3.4 寄存器選擇函數 177
9.3.5 為變址和指針語句產生代碼 178
9.3.6 條件語句 178
9.4 小結 180
複習思考題 180
附錄A C語言實現的實例語言編譯程序 181
附錄B YACC語言實現的實例語言編譯程序 184
參考文獻 185