編譯原理及實踐

目      錄
譯者序
前言
第1章   概論 1
1.1   為什么要用編譯器 2
1.2   與編譯器相關(guān)的程序 3
1.3   翻譯步驟 5
1.4   編譯器中的主要數(shù)據(jù)結(jié)構(gòu) 8
1.5   編譯器結(jié)構(gòu)中的其他問題 10
1.6   自舉與移植 12
1.7   TINY樣本語言與編譯器 14
1.7.1   TINY語言 15
1.7.2   TINY編譯器 15
1.7.3   TM機(jī) 17
1.8   C-Minus：編譯器項目的一種語言 18
練習(xí) 19
注意與參考 20
第2章   詞法分析 21
2.1   掃描處理 21
2.2   正則表達(dá)式 23
2.2.1   正則表達(dá)式的定義 23
2.2.2   正則表達(dá)式的擴(kuò)展 27
2.2.3   程序設(shè)計語言記號的正則表達(dá)式 29
2.3   有窮自動機(jī) 32
2.3.1   確定性有窮自動機(jī)的定義 32
2.3.2   先行. 回溯和非確定性自動機(jī) 36
2.3.3   用代碼實現(xiàn)有窮自動機(jī) 41
2.4   從正則表達(dá)式到DFA 45
2.4.1   從正則表達(dá)式到NFA 45
2.4.2   從NFA到DFA 48
2.4.3   利用子集構(gòu)造模擬NFA 50
2.4.4   將DFA中的狀態(tài)數(shù)最小化 51
2.5   TINY掃描程序的實現(xiàn) 52
2.5.1   為樣本語言TINY實現(xiàn)一個掃描
程序 53
2.5.2   保留字與標(biāo)識符 56
2.5.3   為標(biāo)識符分配空間 57
2.6   利用Lex 自動生成掃描程序 57
2.6.1   正則表達(dá)式的Lex 約定 58
2.6.2   Lex輸入文件的格式 59
2.6.3   使用Lex的TINY掃描程序 64
練習(xí) 65
編程練習(xí) 67
注意與參考 67
第3章   上下文無關(guān)文法及分析 69
3.1   分析過程 69
3.2   上下文無關(guān)文法 70
3.2.1   與正則表達(dá)式比較 70
3.2.2   上下文無關(guān)文法規(guī)則的說明 71
3.2.3   推導(dǎo)及由文法定義的語言 72
3.3   分析樹與抽象語法樹 77
3.3.1   分析樹 77
3.3.2   抽象語法樹 79
3.4   二義性 83
3.4.1   二義性文法 83
3.4.2   優(yōu)先權(quán)和結(jié)合性 85
3.4.3   懸掛else問題 87
3.4.4   無關(guān)緊要的二義性 89
3.5   擴(kuò)展的表示法：EBNF和語法圖 89
3.5.1   EBNF表示法 89
3.5.2   語法圖 91
3.6   上下文無關(guān)語言的形式特性 93
3.6.1   上下文無關(guān)語言的形式定義 93
3.6.2   文法規(guī)則和等式 94
3.6.3   喬姆斯基層次和作為上下文無關(guān)
規(guī)則的語法局限 95
3.7   TINY語言的語法 97
3.7.1   TINY的上下文無關(guān)文法 97
3.7.2   TINY編譯器的語法樹結(jié)構(gòu) 98
練習(xí) 101
注意與參考 104
第4章   自頂向下的分析 105
4.1   使用遞歸下降分析算法進(jìn)行自頂向下
的分析 105
4.1.1   遞歸下降分析的基本方法 105
4.1.2   重復(fù)和選擇：使用EBNF 107
4.1.3   其他決定問題 112
4.2   LL(1)分析 113
4.2.1   LL(1)分析的基本方法 113
4.2.2   LL(1)分析與算法 114
4.2.3   消除左遞歸和提取左因子 117
4.2.4   在LL(1)分析中構(gòu)造語法樹 124
4.3   First集合和Follow集合 125
4.3.1   First 集合 125
4.3.2   Follow 集合 130
4.3.3   構(gòu)造LL(1)分析表 134
4.3.4   再向前：LL(k)分析程序 135
4.4   TINY語言的遞歸下降分析程序 136
4.5   自頂向下分析程序中的錯誤校正 137
4.5.1   在遞歸下降分析程序中的錯誤
校正 138
4.5.2   在LL(1)分析程序中的錯誤校正 140
4.5.3   在TINY分析程序中的錯誤校正 141
練習(xí) 143
編程練習(xí) 146
注意與參考 148
第5章   自底向上的分析 150
5.1   自底向上分析概覽 151
5.2   LR(0)項的有窮自動機(jī)與LR(0)分析 153
5.2.1   LR(0)項 153
5.2.2   項目的有窮自動機(jī) 154
5.2.3   LR(0)分析算法 157
5.3   SLR(1)分析 160
5.3.1   SLR(1)分析算法 160
5.3.2   用于分析沖突的消除二義性
規(guī)則 163
5.3.3   SLR(1)分析能力的局限性 164
5.3.4   SLR(k)文法 165
5.4   一般的LR(1)和LALR(1)分析 166
5.4.1   LR(1)項的有窮自動機(jī) 166
5.4.2   LR(1)分析算法 169
5.4.3   LALR(1)分析 171
5.5   Yacc：一個LALR(1)分析程序的
生成器 173
5.5.1   Yacc基礎(chǔ) 173
5.5.2   Yacc選項 176
5.5.3   分析沖突與消除二義性的規(guī)則 180
5.5.4   描述Yacc分析程序的執(zhí)行 183
5.5.5   Yacc中的任意值類型 184
5.5.6   Yacc中嵌入的動作 185
5.6   使用Yacc生成TINY分析程序 186
5.7   自底向上分析程序中的錯誤校正 188
5.7.1   自底向上分析中的錯誤檢測 188
5.7.2   應(yīng)急方式錯誤校正 188
5.7.3   Yacc中的錯誤校正 189
5.7.4   TINY中的錯誤校正 192
練習(xí) 192
編程練習(xí) 195
注意與參考 197
第6章   語義分析 198
6.1   屬性和屬性文法 199
6.1.1   屬性文法 200
6.1.2   屬性文法的簡化和擴(kuò)充 206
6.2   屬性計算算法 207
6.2.1   相關(guān)圖和賦值順序 208
6.2.2   合成和繼承屬性 212
6.2.3   作為參數(shù)和返回值的屬性 219
6.2.4   使用擴(kuò)展數(shù)據(jù)結(jié)構(gòu)存儲屬性值 221
6.2.5   語法分析時屬性的計算 223
6.2.6   語法中屬性計算的相關(guān)性 226
6.3   符號表 227
6.3.1   符號表的結(jié)構(gòu) 228
6.3.2   說明 230
6.3.3   作用域規(guī)則和塊結(jié)構(gòu) 232
6.3.4   同層說明的相互作用 236
6.3.5   使用符號表的屬性文法的一個
擴(kuò)充例子 237
6.4   數(shù)據(jù)類型和類型檢查 241
6.4.1   類型表達(dá)式和類型構(gòu)造器 242
6.4.2   類型名. 類型說明和遞歸類型 246
6.4.3   類型等價 248
6.4.4   類型推論和類型檢查 253
6.4.5   類型檢查的其他主題 255
6.5   TINY語言的語義分析 257
6.5.1   TINY的符號表 258
6.5.2   TINY語義分析程序 259
練習(xí) 260
編程練習(xí) 264
注意與參考 264
第7章   運行時環(huán)境 266
7.1   程序執(zhí)行時的存儲器組織 266
7.2   完全靜態(tài)運行時環(huán)境 269
7.3   基于棧的運行時環(huán)境 271
7.3.1   沒有局部過程的基于棧的環(huán)境 271
7.3.2  帶有局部過程的基于棧的環(huán)境 281
7.3.3   帶有過程參數(shù)的基于棧的環(huán)境 284
7.4   動態(tài)存儲器 286
7.4.1   完全動態(tài)運行時環(huán)境 286
7.4.2   面向?qū)ο蟮恼Z言中的動態(tài)存儲器 287
7.4.3   堆管理 289
7.4.4   堆的自動管理 292
7.5   參數(shù)傳遞機(jī)制 292
7.5.1   值傳遞 293
7.5.2   引用傳遞 294
7.5.3   值結(jié)果傳遞 295
7.5.4   名字傳遞 295
7.6   TINY語言的運行時環(huán)境 296
練習(xí) 297
編程練習(xí) 303
注意與參考 304
第8章   代碼生成 305
8.1   中間代碼和用于代碼生成的數(shù)據(jù)
結(jié)構(gòu) 305
8.1.1   三地址碼 306
8.1.2   用于實現(xiàn)三地址碼的數(shù)據(jù)結(jié)構(gòu) 308
8.1.3   P-代碼 310
8.2   基本的代碼生成技術(shù) 312
8.2.1   作為合成屬性的中間代碼或目標(biāo)
代碼 312
8.2.2   實際的代碼生成 314
8.2.3   從中間代碼生成目標(biāo)代碼 317
8.3   數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 319
8.3.1   地址計算 319
8.3.2   數(shù)組引用 320
8.3.3   棧記錄結(jié)構(gòu)和指針引用 325
8.4   控制語句和邏輯表達(dá)式的代碼生成 328
8.4.1   if 和while 語句的代碼生成 328
8.4.2   標(biāo)號的生成和回填 330
8.4.3   邏輯表達(dá)式的代碼生成 330
8.4.4   if 和while 語句的代碼生成過程
樣例 331
8.5   過程和函數(shù)調(diào)用的代碼生成 334
8.5.1   過程和函數(shù)的中間代碼 334
8.5.2   函數(shù)定義和調(diào)用的代碼生成過程 336
8.6   商用編譯器中的代碼生成：兩個案
例研究 339
8.6.1   對于80×86的Borland 3.0版C編
譯器 339
8.6.2   Sun SparcStation的Sun 2.0 C編
譯器 343
8.7   TM：簡單的目標(biāo)機(jī)器 346
8.7.1   Tiny Machine的基本結(jié)構(gòu) 347
8.7.2   TM模擬器 349
8.8   TINY語言的代碼生成器 351
8.8.1   TINY代碼生成器的TM接口 351
8.8.2   TINY代碼生成器 352
8.8.3   用TINY編譯器產(chǎn)生和使用TM
代碼文件 354
8.8.4   TINY編譯器生成的TM代碼文
件示例 355
8.9   代碼優(yōu)化技術(shù)考察 357
8.9.1   代碼優(yōu)化的主要來源 358
8.9.2   優(yōu)化分類 360
8.9.3   優(yōu)化的數(shù)據(jù)結(jié)構(gòu)和實現(xiàn)技術(shù) 362
8.10   TINY代碼生成器的簡單優(yōu)化 366
8.10.1   將臨時變量放入寄存器 366
8.10.2   在寄存器中保存變量 367
8.10.3   優(yōu)化測試表達(dá)式 367
練習(xí) 368
編程練習(xí) 371
注意與參考 372
附錄A   編譯器設(shè)計方案 373
附錄B   小型編譯器列表 381
附錄C   Tiny Machine模擬器列表 417