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

第1章  緒論        1
1.1  概述和歷史        1
1.2  編譯器可以做什么        2
1.3  編譯器結(jié)構(gòu)        5
1.4  程序設(shè)計(jì)語言的語法和語義        8
1.5  編譯器設(shè)計(jì)與程序設(shè)計(jì)語言設(shè)計(jì)        10
1.6  編譯器分類        11
1.7  影響編譯器設(shè)計(jì)的因素        12
練習(xí)        13
第2章  一個(gè)簡單編譯器        15
2.1  Micro編譯器結(jié)構(gòu)        15
2.2  Micro詞法分析器        15
2.3  Micro 語法        19
2.4  遞歸下降語法分析        21
2.5  翻譯 Micro        25
2.5.1  目標(biāo)語言        25
2.5.2  臨時(shí)變量        25
2.5.3  動(dòng)作符號        25
2.5.4  語義信息        25
2.5.5  Micro動(dòng)作符號        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í)考慮的問題        45
3.5.1  保留字        45
3.5.2  編譯器指示與源程序行列表        47
3.5.3  符號表中的標(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章  文法和語法分析        59
4.1  上下文無關(guān)文法：概念與記號        59
4.2  上下文無關(guān)文法中的錯(cuò)誤        61
4.3  轉(zhuǎn)換擴(kuò)展 BNF文法        62
4.4  語法分析器與識(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)作符號        77
5.6  文法的LL(1)化        78
5.7  LL(1)分析中的If-Then-Else問題        81
5.8  LLGen—LL(1)語法分析器生成器        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)用語義例程        113
6.7  使用語法分析器生成器        114
6.7.1  LALRGen語法分析器生成器        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)先級技術(shù)        128
6.12.3  一般的上下文無關(guān)分析器        130
練習(xí)        132
第7章  語義處理        137
7.1  語法制導(dǎo)翻譯        137
7.1.1  使用分析的語法樹表示        137
7.1.2  編譯器組織的候選形式        138
7.1.3  一遍編譯中的分析、檢查和翻譯        142
7.2  語義處理技術(shù)        143
7.2.1  LL分析器和動(dòng)作符號        143
7.2.2  LR分析器和動(dòng)作符號        143
7.2.3  語義記錄表示        144
7.2.4  實(shí)現(xiàn)動(dòng)作控制的語義棧        146
7.2.5  分析器控制的語義棧        149
7.3  中間表示和代碼生成        155
7.3.1  比較中間表示和直接代碼生成        155
7.3.2  中間表示的形式        155
7.3.3  一個(gè)元組語言        157
練習(xí)        157
第8章  符號表        161
8.1  符號表接口        161
8.2  基本實(shí)現(xiàn)技術(shù)        162
8.2.1  二叉搜索樹        162
8.2.2  哈希表        163
8.2.3  串空間數(shù)組        164
8.3  塊結(jié)構(gòu)符號表        165
8.4  塊結(jié)構(gòu)符號表的擴(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  塊級與過程級活動(dòng)記錄        187
9.3  堆分配        188
9.3.1  無空間釋放        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  形式過程        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  符號表中的屬性        203
10.1.2  類型描述符結(jié)構(gòu)        204
10.1.3  語義棧中的列表結(jié)構(gòu)        205
10.2  簡單聲明的動(dòng)作例程        207
10.2.1  變量聲明        207
10.2.2  類型定義、聲明和引用        209
10.2.3  記錄類型        212
10.2.4  靜態(tài)數(shù)組        214
10.3  高級特性的動(dòng)作例程        216
10.3.1  變量和常量聲明        216
10.3.2  枚舉類型        218
10.3.3  子類型        220
10.3.4  數(shù)組類型        221
10.3.5  變體記錄        227
10.3.6  訪問類型        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  簡單名字、表達(dá)式和數(shù)據(jù)結(jié)構(gòu)的動(dòng)作例程        242
11.2.1  處理簡單標(biāo)識(shí)符和文字常量        242
11.2.2  處理表達(dá)式        243
11.2.3  簡單的記錄和數(shù)組引用        246
11.2.4  記錄和數(shù)組示例        249
11.2.5  串        250
11.3  高級特性的動(dòng)作例程        250
11.3.1  多維數(shù)組的組織和引用        250
11.3.2  含動(dòng)態(tài)對象的記錄        258
11.3.3  變體記錄        261
11.3.4  訪問類型的引用        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語句        271
12.2  循環(huán)        274
12.2.1  while循環(huán)        274
12.2.2  for循環(huán)        275
12.3  編譯exit語句        280
12.4  case語句        282
12.5  編譯goto語句        287
12.6  異常處理        290
12.7  短路計(jì)算布爾表達(dá)式        294
12.7.1  單地址短路計(jì)算        299
練習(xí)        305
第13章  翻譯過程和函數(shù)        309
13.1  簡單子程序        309
13.1.1  聲明無參子程序        309
13.1.2  調(diào)用無參過程        311
13.2  向子程序傳遞參數(shù)        312
13.2.1  值、結(jié)果和值-結(jié)果參數(shù)        313
13.2.2  引用和只讀參數(shù)        314
13.2.3  處理參數(shù)聲明的語義例程        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)號參數(shù)        321
13.6  名字參數(shù)        323
練習(xí)        324
第14章  屬性文法和多遍翻譯        327
14.1  屬性文法        327
14.1.1  簡單賦值形式和動(dòng)作符號        329
14.1.2  樹遍歷的屬性計(jì)算程序        331
14.1.3  直接屬性計(jì)算程序        335
14.1.4  屬性文法示例        340
14.2  樹結(jié)構(gòu)的中間表示        342
14.2.1  抽象語法樹接口        343
14.2.2  語法樹抽象接口        344
14.2.3  實(shí)現(xiàn)樹        348
練習(xí)        349
第15章  代碼生成和局部代碼優(yōu)化        351
15.1  概述        351
15.2  寄存器和臨時(shí)變量管理        352
15.2.1  臨時(shí)變量的分類        353
15.2.2  分配和釋放臨時(shí)變量        353
15.3  簡單的代碼生成器        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  從樹結(jié)構(gòu)生成代碼        368
15.7  從dag生成代碼        371
15.7.1  別名        376
15.8  代碼生成器的生成器        377
15.8.1  基于文法的代碼生成器        380
15.8.2  在代碼生成器中使用語義屬性        382
15.8.3  生成窺孔優(yōu)化器        385
15.8.4  基于樹重寫的代碼生成器的生成器        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)展開        397
16.2.2  優(yōu)化對封閉子例程的調(diào)用        399
16.2.3  過程間數(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ù)流問題的分類        416
16.4.4  其他重要的數(shù)據(jù)流問題        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í)世界中的語法分析        437
17.1  壓縮表        437
17.1.1  壓縮LL(1)分析表        439
17.2  語法錯(cuò)誤的恢復(fù)與修復(fù)        440
17.2.1  即時(shí)錯(cuò)誤檢測        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語言定義        467
附錄B  ScanGen        487
附錄C  LLGen用戶手冊        493
附錄D  LALRGen用戶手冊        499
附錄E  LLGen和LALRGen錯(cuò)誤修復(fù)特性        507
附錄F  編譯器開發(fā)實(shí)用工具        511
參考文獻(xiàn)        517
索引        523