編譯原理及實(shí)踐

目      錄
譯者序
前言
第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)中的其他問(wèn)題 10
1.6   自舉與移植 12
1.7   TINY樣本語(yǔ)言與編譯器 14
1.7.1   TINY語(yǔ)言 15
1.7.2   TINY編譯器 15
1.7.3   TM機(jī) 17
1.8   C-Minus：編譯器項(xiàng)目的一種語(yǔ)言 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è)計(jì)語(yǔ)言記號(hào)的正則表達(dá)式 29
2.3   有窮自動(dòng)機(jī) 32
2.3.1   確定性有窮自動(dòng)機(jī)的定義 32
2.3.2   先行. 回溯和非確定性自動(dòng)機(jī) 36
2.3.3   用代碼實(shí)現(xiàn)有窮自動(dòng)機(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掃描程序的實(shí)現(xiàn) 52
2.5.1   為樣本語(yǔ)言TINY實(shí)現(xiàn)一個(gè)掃描
程序 53
2.5.2   保留字與標(biāo)識(shí)符 56
2.5.3   為標(biāo)識(shí)符分配空間 57
2.6   利用Lex 自動(dòng)生成掃描程序 57
2.6.1   正則表達(dá)式的Lex 約定 58
2.6.2   Lex輸入文件的格式 59
2.6.3   使用Lex的TINY掃描程序 64
練習(xí) 65
編程練習(xí) 67
注意與參考 67
第3章   上下文無(wú)關(guān)文法及分析 69
3.1   分析過(guò)程 69
3.2   上下文無(wú)關(guān)文法 70
3.2.1   與正則表達(dá)式比較 70
3.2.2   上下文無(wú)關(guān)文法規(guī)則的說(shuō)明 71
3.2.3   推導(dǎo)及由文法定義的語(yǔ)言 72
3.3   分析樹(shù)與抽象語(yǔ)法樹(shù) 77
3.3.1   分析樹(shù) 77
3.3.2   抽象語(yǔ)法樹(shù) 79
3.4   二義性 83
3.4.1   二義性文法 83
3.4.2   優(yōu)先權(quán)和結(jié)合性 85
3.4.3   懸掛else問(wèn)題 87
3.4.4   無(wú)關(guān)緊要的二義性 89
3.5   擴(kuò)展的表示法：EBNF和語(yǔ)法圖 89
3.5.1   EBNF表示法 89
3.5.2   語(yǔ)法圖 91
3.6   上下文無(wú)關(guān)語(yǔ)言的形式特性 93
3.6.1   上下文無(wú)關(guān)語(yǔ)言的形式定義 93
3.6.2   文法規(guī)則和等式 94
3.6.3   喬姆斯基層次和作為上下文無(wú)關(guān)
規(guī)則的語(yǔ)法局限 95
3.7   TINY語(yǔ)言的語(yǔ)法 97
3.7.1   TINY的上下文無(wú)關(guān)文法 97
3.7.2   TINY編譯器的語(yǔ)法樹(shù)結(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   其他決定問(wèn)題 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)造語(yǔ)法樹(shù) 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語(yǔ)言的遞歸下降分析程序 136
4.5   自頂向下分析程序中的錯(cuò)誤校正 137
4.5.1   在遞歸下降分析程序中的錯(cuò)誤
校正 138
4.5.2   在LL(1)分析程序中的錯(cuò)誤校正 140
4.5.3   在TINY分析程序中的錯(cuò)誤校正 141
練習(xí) 143
編程練習(xí) 146
注意與參考 148
第5章   自底向上的分析 150
5.1   自底向上分析概覽 151
5.2   LR(0)項(xiàng)的有窮自動(dòng)機(jī)與LR(0)分析 153
5.2.1   LR(0)項(xiàng) 153
5.2.2   項(xiàng)目的有窮自動(dòng)機(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)項(xiàng)的有窮自動(dòng)機(jī) 166
5.4.2   LR(1)分析算法 169
5.4.3   LALR(1)分析 171
5.5   Yacc：一個(gè)LALR(1)分析程序的
生成器 173
5.5.1   Yacc基礎(chǔ) 173
5.5.2   Yacc選項(xiàng) 176
5.5.3   分析沖突與消除二義性的規(guī)則 180
5.5.4   描述Yacc分析程序的執(zhí)行 183
5.5.5   Yacc中的任意值類型 184
5.5.6   Yacc中嵌入的動(dòng)作 185
5.6   使用Yacc生成TINY分析程序 186
5.7   自底向上分析程序中的錯(cuò)誤校正 188
5.7.1   自底向上分析中的錯(cuò)誤檢測(cè) 188
5.7.2   應(yīng)急方式錯(cuò)誤校正 188
5.7.3   Yacc中的錯(cuò)誤校正 189
5.7.4   TINY中的錯(cuò)誤校正 192
練習(xí) 192
編程練習(xí) 195
注意與參考 197
第6章   語(yǔ)義分析 198
6.1   屬性和屬性文法 199
6.1.1   屬性文法 200
6.1.2   屬性文法的簡(jiǎn)化和擴(kuò)充 206
6.2   屬性計(jì)算算法 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)存儲(chǔ)屬性值 221
6.2.5   語(yǔ)法分析時(shí)屬性的計(jì)算 223
6.2.6   語(yǔ)法中屬性計(jì)算的相關(guān)性 226
6.3   符號(hào)表 227
6.3.1   符號(hào)表的結(jié)構(gòu) 228
6.3.2   說(shuō)明 230
6.3.3   作用域規(guī)則和塊結(jié)構(gòu) 232
6.3.4   同層說(shuō)明的相互作用 236
6.3.5   使用符號(hào)表的屬性文法的一個(gè)
擴(kuò)充例子 237
6.4   數(shù)據(jù)類型和類型檢查 241
6.4.1   類型表達(dá)式和類型構(gòu)造器 242
6.4.2   類型名. 類型說(shuō)明和遞歸類型 246
6.4.3   類型等價(jià) 248
6.4.4   類型推論和類型檢查 253
6.4.5   類型檢查的其他主題 255
6.5   TINY語(yǔ)言的語(yǔ)義分析 257
6.5.1   TINY的符號(hào)表 258
6.5.2   TINY語(yǔ)義分析程序 259
練習(xí) 260
編程練習(xí) 264
注意與參考 264
第7章   運(yùn)行時(shí)環(huán)境 266
7.1   程序執(zhí)行時(shí)的存儲(chǔ)器組織 266
7.2   完全靜態(tài)運(yùn)行時(shí)環(huán)境 269
7.3   基于棧的運(yùn)行時(shí)環(huán)境 271
7.3.1   沒(méi)有局部過(guò)程的基于棧的環(huán)境 271
7.3.2  帶有局部過(guò)程的基于棧的環(huán)境 281
7.3.3   帶有過(guò)程參數(shù)的基于棧的環(huán)境 284
7.4   動(dòng)態(tài)存儲(chǔ)器 286
7.4.1   完全動(dòng)態(tài)運(yùn)行時(shí)環(huán)境 286
7.4.2   面向?qū)ο蟮恼Z(yǔ)言中的動(dòng)態(tài)存儲(chǔ)器 287
7.4.3   堆管理 289
7.4.4   堆的自動(dòng)管理 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語(yǔ)言的運(yùn)行時(shí)環(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   用于實(shí)現(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   實(shí)際的代碼生成 314
8.2.3   從中間代碼生成目標(biāo)代碼 317
8.3   數(shù)據(jù)結(jié)構(gòu)引用的代碼生成 319
8.3.1   地址計(jì)算 319
8.3.2   數(shù)組引用 320
8.3.3   棧記錄結(jié)構(gòu)和指針引用 325
8.4   控制語(yǔ)句和邏輯表達(dá)式的代碼生成 328
8.4.1   if 和while 語(yǔ)句的代碼生成 328
8.4.2   標(biāo)號(hào)的生成和回填 330
8.4.3   邏輯表達(dá)式的代碼生成 330
8.4.4   if 和while 語(yǔ)句的代碼生成過(guò)程
樣例 331
8.5   過(guò)程和函數(shù)調(diào)用的代碼生成 334
8.5.1   過(guò)程和函數(shù)的中間代碼 334
8.5.2   函數(shù)定義和調(diào)用的代碼生成過(guò)程 336
8.6   商用編譯器中的代碼生成：兩個(gè)案
例研究 339
8.6.1   對(duì)于80×86的Borland 3.0版C編
譯器 339
8.6.2   Sun SparcStation的Sun 2.0 C編
譯器 343
8.7   TM：簡(jiǎn)單的目標(biāo)機(jī)器 346
8.7.1   Tiny Machine的基本結(jié)構(gòu) 347
8.7.2   TM模擬器 349
8.8   TINY語(yǔ)言的代碼生成器 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)化的主要來(lái)源 358
8.9.2   優(yōu)化分類 360
8.9.3   優(yōu)化的數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)技術(shù) 362
8.10   TINY代碼生成器的簡(jiǎn)單優(yōu)化 366
8.10.1   將臨時(shí)變量放入寄存器 366
8.10.2   在寄存器中保存變量 367
8.10.3   優(yōu)化測(cè)試表達(dá)式 367
練習(xí) 368
編程練習(xí) 371
注意與參考 372
附錄A   編譯器設(shè)計(jì)方案 373
附錄B   小型編譯器列表 381
附錄C   Tiny Machine模擬器列表 417