內容簡介
本書系統地介紹了程式設計語言翻譯的基本原理與技術，內容包括編譯器構造的所有重要階段：詞法分析、語法分析、語義分析與中間代碼生成、代碼最佳化、運行時的存儲分配以及目標代碼的生成等。本書還介紹了編譯器編寫工具LEX和YACC的工作原理與使用方法，並對語法制導翻譯與屬性計算、類型與類型檢查、數據流分析等編譯器構造和程式分析技術中當前重點關注的原理和方法進行了討論。
本書既可以作為工科院校計算機專業或非計算機專業本科生與研究生的教材，也可以作為軟體技術人員和程式設計語言愛好者的參考書。
目錄
第1章 引言 1
1.1 從面向機器的語言到面向人類的語言 1
1.2 語言之間的翻譯 2
1.3 編譯器與解釋器 3
1.4 編譯器的工作原理與基本組成 4
1.4.1 通用程式設計語言的主要成分 4
1.4.2 以階段劃分編譯器 5
1.4.3 編譯器各階段的工作 6
1.4.4 編譯器的分析/綜合模式 10
1.4.5 編譯器掃描的遍數 11
1.5 編譯器的編寫 11
1.6 本章小結 12
習題 13
第2章 詞法分析 14
2.1 詞法分析中的若干問題 14
2.1.1 記號、模式與單詞 14
2.1.2 記號的屬性 15
2.1.3 詞法分析器的作用與工作方式 16
2.1.4 輸入緩衝區 17
2.2 模式的形式化描述 18
2.2.1 字元串與語言 18
2.2.2 正規式與正規集 20
2.2.3 記號的說明 21
2.3 記號的識別——有限自動機 22
2.3.1 不確定的有限自動機(Nondeterministic Finite Automata，NFA) 22
2.3.2 確定的有限自動機(Deterministic Finite Automata，DFA) 25
2.3.3 有限自動機的等價 26
2.4 從正規式到詞法分析器 27
2.4.1 從正規式到NFA 27
2.4.2 從NFA到DFA 29
2.4.3 最小化DFA 33
2.4.4* DFA的“短路”計算 35
2.4.5 由DFA構造詞法分析器 42
2.5 本章小結 44
習題 45
第3章 語法分析 48
3.1 語法分析的若干問題 48
3.1.1 語法分析器的作用 48
3.1.2 語法錯誤的處理原則 49
3.2 上下文無關文法 50
3.2.1 上下文無關文法的定義與表示 50
3.2.2 CFG產生語言的基本方法——推導 52
3.2.3 推導、分析樹與語法樹 53
3.2.4 二義性與二義性的消除 54
3.3 語言與文法簡介 59
3.3.1 正規式與上下文無關文法 59
3.3.2 上下文有關文法 60
3.3.3 形式語言與自動機簡介 62
3.4 自上而下語法分析 63
3.4.1 自上而下分析的一般方法 63
3.4.2 消除左遞歸 64
3.4.3 提取左因子 66
3.4.4 遞歸下降分析 67
3.4.5 預測分析器 71
3.5 自下而上語法分析 77
3.5.1 自下而上分析的基本方法 77
3.5.2 LR分析 80
3.6* LR(1)與LALR(1)分析 89
3.6.1 SLR分析器的弱點 89
3.6.2 LR(1)分析器 90
3.6.3 LALR(1)分析器 92
3.6.4 LR(1)與LALR(1)的關係 94
3.6.5 LR(1)與二義文法的關係 96
3.7* 編譯器編寫工具 97
3.7.1 詞法分析器生成器LEX 97
3.7.2 語法分析器生成器YACC 109
3.7.3 語言識別器生成工具簡述 131
3.8 本章小結 134
習題 136
第4章 靜態語義分析 139
4.1 語法制導翻譯簡介 139
4.1.1 語法與語義 139
4.1.2 屬性與語義規則 140
4.1.3 語義規則的兩種形式 141
4.1.4 LR分析翻譯方案的設計 142
4.1.5 遞歸下降分析翻譯方案的設計 144
4.2* 屬性的計算 145
4.2.1 綜合屬性與自下而上分析 145
4.2.2 繼承屬性與自上而下分析 146
4.2.3 依賴圖與屬性計算 148
4.2.4 L_屬性的增量分析 151
4.2.5 L_屬性的自下而上計算 154
4.2.6 屬性的空間分配 160
4.2.7 YACC源程式中的語法制導翻譯 163
4.3 中間代碼簡介 165
4.3.1 後綴式 165
4.3.2 三地址碼 166
4.3.3 圖形表示 170
4.4 符號表簡介 171
4.4.1 符號表條目 172
4.4.2 構成名字的字元串 173
4.4.3 名字的作用域 173
4.4.4 線性表 175
4.4.5 散列表 175
4.5 聲明語句的翻譯 177
4.5.1 變數的聲明 177
4.5.2 數組變數的聲明 179
4.5.3 過程的定義與聲明 184
4.5.4 記錄的域名 194
4.6 簡單算術表達式與賦值句 195
4.6.1 簡單變數的語法制導翻譯 195
4.6.2 變數的類型轉換 195
4.7 數組元素的引用 198
4.7.1 數組元素的地址計算 199
4.7.2 數組元素引用的語法制導翻譯 200
4.8 布爾表達式 203
4.8.1 布爾表達式的作用與結構 203
4.8.2 布爾表達式的計算方法 203
4.8.3 數值表示與直接計算的語法制導翻譯 204
4.8.4 短路計算的語法制導翻譯 206
4.8.5 拉鏈與回填 207
4.9 控制語句 209
4.9.1 標號與無條件轉移 210
4.9.2 條件轉移 211
4.10 過程調用 214
4.11* 類型檢查 215
4.11.1 類型、類型系統與類型檢查 215
4.11.2 類型系統 219
4.11.3 簡單的類型檢查 222
4.11.4 類型表達式的等價 226
4.11.5 多態函式的類型檢查 229
4.11.6 特定多態的類型檢查 235
4.12 本章小結 238
習題 240
第5章 運行環境 243
5.1 過程的動態特性 243
5.1.1 過程與活動 243
5.1.2 控制棧與活動記錄 245
5.1.3 名字的綁定 246
5.2 運行時數據空間的組織 247
5.2.1 運行時記憶體的劃分與數據空間的存儲分配策略 247
5.2.2 靜態與動態分配簡介 248
5.3 棧式動態分配 250
5.3.1 控制棧中的活動記錄 250
5.3.2 調用序列與返回序列 251
5.3.3 棧式分配中對非本地名字的訪問 252
5.3.4 參數傳遞的實現 255
5.4 本章小結 257
習題 258
第6章 代碼生成 260
6.1 代碼生成的相關問題 260
6.2 簡單的計算機模型 260
6.3 簡單的代碼生成器 262
6.3.1 基本塊、流圖與循環 263
6.3.2 下次引用信息與活躍信息 266
6.3.3 簡單的代碼生成 267
6.4 本章小結 269
習題 269
第7章 代碼最佳化 271
7.1 局部最佳化 271
7.1.1 基本塊的最佳化 271
7.1.2 窺孔最佳化 276
7.1.3 表達式的最佳化代碼生成 278
7.2 獨立於機器的最佳化 281
7.2.1 運行實例：快排序 282
7.2.2 全局公共子表達式 284
7.2.3 複寫傳播(Copy Propagation) 286
7.2.4 死代碼消除(Dead-Code Elimination) 286
7.2.5 代碼外提(Code Motion) 287
7.2.6 歸納變數與強度削弱 287
7.3* 數據流分析簡介 289
7.3.1 數據流抽象 290
7.3.2 數據流分析模式 291
7.3.3 基本塊上的數據流模式 292
7.3.4 到達定值(Reaching Definitions) 292
7.3.5 活躍變數(Live Varibale) 296
7.3.6 可用表達式(Availabal Expression) 297
7.3.7 小結 300
7.4* 數據流分析的數學基礎 300
7.4.1 半格(Semilattices) 301
7.4.2 轉換函式(Transfer Functions) 303
7.4.3 通用框架的疊代算法 305
7.4.4 數據流解的意義 306
7.5 本章小結 308
習題 309
參考文獻 311
