目      錄
譯者序
前言
第1章   概論	1
1.1   為什么要用編譯器	2
1.2   與編譯器相關的程序	3
1.3   翻譯步驟	5
1.4   編譯器中的主要數據結構	8
1.5   編譯器結構中的其他問題	10
1.6   自舉與移植	12
1.7   TINY樣本語言與編譯器	14
1.7.1   TINY語言	15
1.7.2   TINY編譯器	15
1.7.3   TM機	17
1.8   C-Minus：編譯器項目的一種語言	18
練習	19
注意與參考	20
第2章   詞法分析	21
2.1   掃描處理	21
2.2   正則表達式	23
2.2.1   正則表達式的定義	23
2.2.2   正則表達式的擴展	27
2.2.3   程序設計語言記號的正則表達式	29
2.3   有窮自動機	32
2.3.1   確定性有窮自動機的定義	32
2.3.2   先行、回溯和非確定性自動機	36
2.3.3   用代碼實現有窮自動機	41
2.4   從正則表達式到DFA	45
2.4.1   從正則表達式到NFA	45
2.4.2   從NFA到DFA	48
2.4.3   利用子集構造模擬NFA	50
2.4.4   將DFA中的狀態數最小化	51
2.5   TINY掃描程序的實現	52
2.5.1   為樣本語言TINY實現一個掃描
程序	53
2.5.2   保留字與標識符	56
2.5.3   為標識符分配空間	57
2.6   利用Lex 自動生成掃描程序	57
2.6.1   正則表達式的Lex 約定	58
2.6.2   Lex輸入文件的格式	59
2.6.3   使用Lex的TINY掃描程序	64
練習	65
編程練習	67
注意與參考	67
第3章   上下文無關文法及分析	69
3.1   分析過程	69
3.2   上下文無關文法	70
3.2.1   與正則表達式比較	70
3.2.2   上下文無關文法規則的說明	71
3.2.3   推導及由文法定義的語言	72
3.3   分析樹與抽象語法樹	77
3.3.1   分析樹	77
3.3.2   抽象語法樹	79
3.4   二義性	83
3.4.1   二義性文法	83
3.4.2   優先權和結合性	85
3.4.3   懸掛else問題	87
3.4.4   無關緊要的二義性	89
3.5   擴展的表示法：EBNF和語法圖	89
3.5.1   EBNF表示法	89
3.5.2   語法圖	91
3.6   上下文無關語言的形式特性	93
3.6.1   上下文無關語言的形式定義	93
3.6.2   文法規則和等式	94
3.6.3   喬姆斯基層次和作為上下文無關
規則的語法局限	95
3.7   TINY語言的語法	97
3.7.1   TINY的上下文無關文法	97
3.7.2   TINY編譯器的語法樹結構	98
練習	101
注意與參考	104
第4章   自頂向下的分析	105
4.1   使用遞歸下降分析算法進行自頂向下
的分析	105
4.1.1   遞歸下降分析的基本方法	105
4.1.2   重復和選擇：使用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)分析中構造語法樹	124
4.3   First集合和Follow集合	125
4.3.1   First 集合	125
4.3.2   Follow 集合	130
4.3.3   構造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
練習	143
編程練習	146
注意與參考	148
第5章   自底向上的分析	150
5.1   自底向上分析概覽	151
5.2   LR(0)項的有窮自動機與LR(0)分析	153
5.2.1   LR(0)項	153
5.2.2   項目的有窮自動機	154
5.2.3   LR(0)分析算法	157
5.3   SLR(1)分析	160
5.3.1   SLR(1)分析算法	160
5.3.2   用于分析沖突的消除二義性
規則	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)項的有窮自動機	166
5.4.2   LR(1)分析算法	169
5.4.3   LALR(1)分析	171
5.5   Yacc：一個LALR(1)分析程序的
生成器	173
5.5.1   Yacc基礎	173
5.5.2   Yacc選項	176
5.5.3   分析沖突與消除二義性的規則	180
5.5.4   描述Yacc分析程序的執行	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   應急方式錯誤校正	188
5.7.3   Yacc中的錯誤校正	189
5.7.4   TINY中的錯誤校正	192
練習	192
編程練習	195
注意與參考	197
第6章   語義分析	198
6.1   屬性和屬性文法	199
6.1.1   屬性文法	200
6.1.2   屬性文法的簡化和擴充	206
6.2   屬性計算算法	207
6.2.1   相關圖和賦值順序	208
6.2.2   合成和繼承屬性	212
6.2.3   作為參數和返回值的屬性	219
6.2.4   使用擴展數據結構存儲屬性值	221
6.2.5   語法分析時屬性的計算	223
6.2.6   語法中屬性計算的相關性	226
6.3   符號表	227
6.3.1   符號表的結構	228
6.3.2   說明	230
6.3.3   作用域規則和塊結構	232
6.3.4   同層說明的相互作用	236
6.3.5   使用符號表的屬性文法的一個
擴充例子	237
6.4   數據類型和類型檢查	241
6.4.1   類型表達式和類型構造器	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
練習	260
編程練習	264
注意與參考	264
第7章   運行時環境	266
7.1   程序執行時的存儲器組織	266
7.2   完全靜態運行時環境	269
7.3   基于棧的運行時環境	271
7.3.1   沒有局部過程的基于棧的環境	271
7.3.2  帶有局部過程的基于棧的環境	281
7.3.3   帶有過程參數的基于棧的環境	284
7.4   動態存儲器	286
7.4.1   完全動態運行時環境	286
7.4.2   面向對象的語言中的動態存儲器	287
7.4.3   堆管理	289
7.4.4   堆的自動管理	292
7.5   參數傳遞機制	292
7.5.1   值傳遞	293
7.5.2   引用傳遞	294
7.5.3   值結果傳遞	295
7.5.4   名字傳遞	295
7.6   TINY語言的運行時環境	296
練習	297
編程練習	303
注意與參考	304
第8章   代碼生成	305
8.1   中間代碼和用于代碼生成的數據
結構	305
8.1.1   三地址碼	306
8.1.2   用于實現三地址碼的數據結構	308
8.1.3   P-代碼	310
8.2   基本的代碼生成技術	312
8.2.1   作為合成屬性的中間代碼或目標
代碼	312
8.2.2   實際的代碼生成	314
8.2.3   從中間代碼生成目標代碼	317
8.3   數據結構引用的代碼生成	319
8.3.1   地址計算	319
8.3.2   數組引用	320
8.3.3   棧記錄結構和指針引用	325
8.4   控制語句和邏輯表達式的代碼生成	328
8.4.1   if 和while 語句的代碼生成	328
8.4.2   標號的生成和回填	330
8.4.3   邏輯表達式的代碼生成	330
8.4.4   if 和while 語句的代碼生成過程
樣例	331
8.5   過程和函數調用的代碼生成	334
8.5.1   過程和函數的中間代碼	334
8.5.2   函數定義和調用的代碼生成過程	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：簡單的目標機器	346
8.7.1   Tiny Machine的基本結構	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編譯器產生和使用TM
代碼文件	354
8.8.4   TINY編譯器生成的TM代碼文
件示例	355
8.9   代碼優化技術考察	357
8.9.1   代碼優化的主要來源	358
8.9.2   優化分類	360
8.9.3   優化的數據結構和實現技術	362
8.10   TINY代碼生成器的簡單優化	366
8.10.1   將臨時變量放入寄存器	366
8.10.2   在寄存器中保存變量	367
8.10.3   優化測試表達式	367
練習	368
編程練習	371
注意與參考	372
附錄A   編譯器設計方案	373
附錄B   小型編譯器列表	381
附錄C   Tiny Machine模擬器列表	417