編譯器構(gòu)造：C語(yǔ)言描述

第1章  緒論        1
1.1  概述和歷史        1
1.2  編譯器可以做什么        2
1.3  編譯器結(jié)構(gòu)        5
1.4  程序設(shè)計(jì)語(yǔ)言的語(yǔ)法和語(yǔ)義        8
1.5  編譯器設(shè)計(jì)與程序設(shè)計(jì)語(yǔ)言設(shè)計(jì)        10
1.6  編譯器分類(lèi)        11
1.7  影響編譯器設(shè)計(jì)的因素        12
練習(xí)        13
第2章  一個(gè)簡(jiǎn)單編譯器        15
2.1  Micro編譯器結(jié)構(gòu)        15
2.2  Micro詞法分析器        15
2.3  Micro 語(yǔ)法        19
2.4  遞歸下降語(yǔ)法分析        21
2.5  翻譯 Micro        25
2.5.1  目標(biāo)語(yǔ)言        25
2.5.2  臨時(shí)變量        25
2.5.3  動(dòng)作符號(hào)        25
2.5.4  語(yǔ)義信息        25
2.5.5  Micro動(dòng)作符號(hào)        26
練習(xí)        31
第3章  詞法分析—理論和實(shí)踐        33
3.1  概述        33
3.2  正則表達(dá)式        34
3.3  有限自動(dòng)機(jī)和詞法分析器        35
3.4  使用詞法分析器生成器        38
3.4.1  ScanGen        38
3.4.2  Lex        43
3.5  實(shí)現(xiàn)時(shí)考慮的問(wèn)題        45
3.5.1  保留字        45
3.5.2  編譯器指示與源程序行列表        47
3.5.3  符號(hào)表中的標(biāo)識(shí)符條目        47
3.5.4  詞法分析器的終止        48
3.5.5  多字符的超前搜索        48
3.5.6  詞法錯(cuò)誤恢復(fù)        49
3.6  將正則表達(dá)式轉(zhuǎn)換為有限自動(dòng)機(jī)        51
3.6.1  構(gòu)造確定的有限自動(dòng)機(jī)        52
3.6.2  優(yōu)化有限自動(dòng)機(jī)        54
練習(xí)        55
第4章  文法和語(yǔ)法分析        59
4.1  上下文無(wú)關(guān)文法：概念與記號(hào)        59
4.2  上下文無(wú)關(guān)文法中的錯(cuò)誤        61
4.3  轉(zhuǎn)換擴(kuò)展 BNF文法        62
4.4  語(yǔ)法分析器與識(shí)別器        63
4.5  文法分析算法        64
練習(xí)        69
第5章  LL(1)文法及分析器        71
5.1  LL(1) Predict函數(shù)        71
5.2  LL(1)分析表        73
5.3  從LL(1)分析表構(gòu)造遞歸下降分析器        74
5.4  LL(1)分析器驅(qū)動(dòng)程序        77
5.5  LL(1)動(dòng)作符號(hào)        77
5.6  文法的LL(1)化        78
5.7  LL(1)分析中的If-Then-Else問(wèn)題        81
5.8  LLGen—LL(1)語(yǔ)法分析器生成器        82
5.9  LL(1)分析器的性質(zhì)        85
5.10  LL(k)分析        85
練習(xí)        87
第6章  LR分析        89
6.1  移進(jìn)-歸約分析器        89
6.2  LR分析器        91
6.2.1  LR(0)分析        92
6.2.2  如何判定LR(0)分析程序工作的正確性        96
6.3  LR(1)分析        98
6.3.1  LR(1)分析的正確性        101
6.4  SLR(1)分析        102
6.4.1  SLR(1)分析的正確性        103
6.4.2  SLR(1)技術(shù)的局限性        104
6.5  LALR(1)分析        105
6.5.1  構(gòu)造LALR(1)分析器        108
6.5.2  LALR(1)分析的正確性        112
6.6  在移進(jìn)-歸約分析器中調(diào)用語(yǔ)義例程        113
6.7  使用語(yǔ)法分析器生成器        114
6.7.1  LALRGen語(yǔ)法分析器生成器        114
6.7.2  Yacc        116
6.7.3  可控二義性的使用和誤用        117
6.8  優(yōu)化分析表        120
6.9  實(shí)用的LR(1)分析器        123
6.10  LR分析的性質(zhì)        125
6.11  LL(1)和LALR(1)分析方法的比較        125
6.12  其他的移進(jìn)-歸約技術(shù)        128
6.12.1  擴(kuò)展的超前搜索技術(shù)        128
6.12.2  優(yōu)先級(jí)技術(shù)        128
6.12.3  一般的上下文無(wú)關(guān)分析器        130
練習(xí)        132
第7章  語(yǔ)義處理        137
7.1  語(yǔ)法制導(dǎo)翻譯        137
7.1.1  使用分析的語(yǔ)法樹(shù)表示        137
7.1.2  編譯器組織的候選形式        138
7.1.3  一遍編譯中的分析、檢查和翻譯        142
7.2  語(yǔ)義處理技術(shù)        143
7.2.1  LL分析器和動(dòng)作符號(hào)        143
7.2.2  LR分析器和動(dòng)作符號(hào)        143
7.2.3  語(yǔ)義記錄表示        144
7.2.4  實(shí)現(xiàn)動(dòng)作控制的語(yǔ)義棧        146
7.2.5  分析器控制的語(yǔ)義棧        149
7.3  中間表示和代碼生成        155
7.3.1  比較中間表示和直接代碼生成        155
7.3.2  中間表示的形式        155
7.3.3  一個(gè)元組語(yǔ)言        157
練習(xí)        157
第8章  符號(hào)表        161
8.1  符號(hào)表接口        161
8.2  基本實(shí)現(xiàn)技術(shù)        162
8.2.1  二叉搜索樹(shù)        162
8.2.2  哈希表        163
8.2.3  串空間數(shù)組        164
8.3  塊結(jié)構(gòu)符號(hào)表        165
8.4  塊結(jié)構(gòu)符號(hào)表的擴(kuò)展        169
8.4.1  域和記錄        169
8.4.2  導(dǎo)出規(guī)則        170
8.4.3  導(dǎo)入規(guī)則        174
8.4.4  可更改的搜索規(guī)則        175
8.5  隱式聲明        177
8.6  重載        177
8.7  前向引用        178
8.8  小結(jié)        180
練習(xí)        180
第9章  運(yùn)行時(shí)存儲(chǔ)組織        183
9.1  靜態(tài)分配        183
9.2  棧分配        183
9.2.1  顯示表        185
9.2.2  塊級(jí)與過(guò)程級(jí)活動(dòng)記錄        187
9.3  堆分配        188
9.3.1  無(wú)空間釋放        188
9.3.2  顯式釋放        188
9.3.3  隱式釋放        189
9.3.4  管理堆空間        190
9.4  內(nèi)存中的程序布局        191
9.5  靜態(tài)鏈簇和動(dòng)態(tài)鏈簇        193
9.6  形式過(guò)程        195
9.6.1  靜態(tài)鏈簇        196
9.6.2  顯示表        197
9.6.3  一些看法        198
練習(xí)        199
第10章  處理聲明        203
10.1  聲明處理的基本原則        203
10.1.1  符號(hào)表中的屬性        203
10.1.2  類(lèi)型描述符結(jié)構(gòu)        204
10.1.3  語(yǔ)義棧中的列表結(jié)構(gòu)        205
10.2  簡(jiǎn)單聲明的動(dòng)作例程        207
10.2.1  變量聲明        207
10.2.2  類(lèi)型定義、聲明和引用        209
10.2.3  記錄類(lèi)型        212
10.2.4  靜態(tài)數(shù)組        214
10.3  高級(jí)特性的動(dòng)作例程        216
10.3.1  變量和常量聲明        216
10.3.2  枚舉類(lèi)型        218
10.3.3  子類(lèi)型        220
10.3.4  數(shù)組類(lèi)型        221
10.3.5  變體記錄        227
10.3.6  訪問(wèn)類(lèi)型        232
10.3.7  包        233
10.3.8  attributes和semantics_record結(jié)構(gòu)        236
練習(xí)        239
第11章  處理表達(dá)式和數(shù)據(jù)結(jié)構(gòu)引用        241
11.1  概述        241
11.2  簡(jiǎn)單名字、表達(dá)式和數(shù)據(jù)結(jié)構(gòu)的動(dòng)作例程        242
11.2.1  處理簡(jiǎn)單標(biāo)識(shí)符和文字常量        242
11.2.2  處理表達(dá)式        243
11.2.3  簡(jiǎn)單的記錄和數(shù)組引用        246
11.2.4  記錄和數(shù)組示例        249
11.2.5  串        250
11.3  高級(jí)特性的動(dòng)作例程        250
11.3.1  多維數(shù)組的組織和引用        250
11.3.2  含動(dòng)態(tài)對(duì)象的記錄        258
11.3.3  變體記錄        261
11.3.4  訪問(wèn)類(lèi)型的引用        262
11.3.5  Ada中其他名字的使用        263
11.3.6  記錄和數(shù)組聚合        265
11.3.7  重載解析        266
練習(xí)        269
第12章  翻譯控制結(jié)構(gòu)        271
12.1  if語(yǔ)句        271
12.2  循環(huán)        274
12.2.1  while循環(huán)        274
12.2.2  for循環(huán)        275
12.3  編譯exit語(yǔ)句        280
12.4  case語(yǔ)句        282
12.5  編譯goto語(yǔ)句        287
12.6  異常處理        290
12.7  短路計(jì)算布爾表達(dá)式        294
12.7.1  單地址短路計(jì)算        299
練習(xí)        305
第13章  翻譯過(guò)程和函數(shù)        309
13.1  簡(jiǎn)單子程序        309
13.1.1  聲明無(wú)參子程序        309
13.1.2  調(diào)用無(wú)參過(guò)程        311
13.2  向子程序傳遞參數(shù)        312
13.2.1  值、結(jié)果和值-結(jié)果參數(shù)        313
13.2.2  引用和只讀參數(shù)        314
13.2.3  處理參數(shù)聲明的語(yǔ)義例程        314
13.3  處理子程序調(diào)用和參數(shù)表        316
13.4  子程序調(diào)用        317
13.4.1  保存和恢復(fù)寄存器        317
13.4.2  子程序的入口和出口        318
13.5  標(biāo)號(hào)參數(shù)        321
13.6  名字參數(shù)        323
練習(xí)        324
第14章  屬性文法和多遍翻譯        327
14.1  屬性文法        327
14.1.1  簡(jiǎn)單賦值形式和動(dòng)作符號(hào)        329
14.1.2  樹(shù)遍歷的屬性計(jì)算程序        331
14.1.3  直接屬性計(jì)算程序        335
14.1.4  屬性文法示例        340
14.2  樹(shù)結(jié)構(gòu)的中間表示        342
14.2.1  抽象語(yǔ)法樹(shù)接口        343
14.2.2  語(yǔ)法樹(shù)抽象接口        344
14.2.3  實(shí)現(xiàn)樹(shù)        348
練習(xí)        349
第15章  代碼生成和局部代碼優(yōu)化        351
15.1  概述        351
15.2  寄存器和臨時(shí)變量管理        352
15.2.1  臨時(shí)變量的分類(lèi)        353
15.2.2  分配和釋放臨時(shí)變量        353
15.3  簡(jiǎn)單的代碼生成器        354
15.4  解釋性代碼生成        356
15.4.1  優(yōu)化地址計(jì)算        357
15.4.2  避免冗余計(jì)算        359
15.4.3  寄存器追蹤        361
15.5  窺孔優(yōu)化        367
15.6  從樹(shù)結(jié)構(gòu)生成代碼        368
15.7  從dag生成代碼        371
15.7.1  別名        376
15.8  代碼生成器的生成器        377
15.8.1  基于文法的代碼生成器        380
15.8.2  在代碼生成器中使用語(yǔ)義屬性        382
15.8.3  生成窺孔優(yōu)化器        385
15.8.4  基于樹(shù)重寫(xiě)的代碼生成器的生成器        387
練習(xí)        387
第16章  全局優(yōu)化        393
16.1  概述—目標(biāo)與限制        393
16.1.1  理想的優(yōu)化編譯器結(jié)構(gòu)        394
16.1.2  優(yōu)化展望        397
16.2  優(yōu)化子程序調(diào)用        397
16.2.1  子程序調(diào)用的內(nèi)聯(lián)展開(kāi)        397
16.2.2  優(yōu)化對(duì)封閉子例程的調(diào)用        399
16.2.3  過(guò)程間數(shù)據(jù)流分析        402
16.3  循環(huán)優(yōu)化        406
16.3.1  外提循環(huán)不變式        406
16.3.2  循環(huán)中強(qiáng)度削弱        409
16.4  全局?jǐn)?shù)據(jù)流分析        411
16.4.1  單路徑流分析        411
16.4.2  全路徑流分析        415
16.4.3  數(shù)據(jù)流問(wèn)題的分類(lèi)        416
16.4.4  其他重要的數(shù)據(jù)流問(wèn)題        416
16.4.5  使用數(shù)據(jù)流信息的全局優(yōu)化        418
16.4.6  求解數(shù)據(jù)流方程        422
16.5  集成優(yōu)化技術(shù)        430
練習(xí)        431
第17章  現(xiàn)實(shí)世界中的語(yǔ)法分析        437
17.1  壓縮表        437
17.1.1  壓縮LL(1)分析表        439
17.2  語(yǔ)法錯(cuò)誤的恢復(fù)與修復(fù)        440
17.2.1  即時(shí)錯(cuò)誤檢測(cè)        442
17.2.2  遞歸下降分析器中的錯(cuò)誤恢復(fù)        443
17.2.3  LL(1)分析器中的錯(cuò)誤恢復(fù)        445
17.2.4  FMQ LL(1)錯(cuò)誤修復(fù)算法        446
17.2.5  在FMQ修復(fù)算法中添加刪除操作        449
17.2.6  FMQ算法的擴(kuò)展        450
17.2.7  利用LLGen進(jìn)行錯(cuò)誤修復(fù)        454
17.2.8  LR錯(cuò)誤恢復(fù)        455
17.2.9  Yacc中的錯(cuò)誤恢復(fù)        455
17.2.10  自動(dòng)生成的LR修復(fù)技術(shù)        456
17.2.11  利用LALRGen進(jìn)行錯(cuò)誤修復(fù)        462
17.2.12  其他LR錯(cuò)誤修復(fù)技術(shù)        462
練習(xí)        463
附錄A  Ada/CS語(yǔ)言定義        467
附錄B  ScanGen        487
附錄C  LLGen用戶手冊(cè)        493
附錄D  LALRGen用戶手冊(cè)        499
附錄E  LLGen和LALRGen錯(cuò)誤修復(fù)特性        507
附錄F  編譯器開(kāi)發(fā)實(shí)用工具        511
參考文獻(xiàn)        517
索引        523