編譯器構造：C語言描述

第1章  緒論        1
1.1  概述和歷史        1
1.2  編譯器可以做什么        2
1.3  編譯器結構        5
1.4  程序設計語言的語法和語義        8
1.5  編譯器設計與程序設計語言設計        10
1.6  編譯器分類        11
1.7  影響編譯器設計的因素        12
練習        13
第2章  一個簡單編譯器        15
2.1  Micro編譯器結構        15
2.2  Micro詞法分析器        15
2.3  Micro 語法        19
2.4  遞歸下降語法分析        21
2.5  翻譯 Micro        25
2.5.1  目標語言        25
2.5.2  臨時變量        25
2.5.3  動作符號        25
2.5.4  語義信息        25
2.5.5  Micro動作符號        26
練習        31
第3章  詞法分析—理論和實踐        33
3.1  概述        33
3.2  正則表達式        34
3.3  有限自動機和詞法分析器        35
3.4  使用詞法分析器生成器        38
3.4.1  ScanGen        38
3.4.2  Lex        43
3.5  實現(xiàn)時考慮的問題        45
3.5.1  保留字        45
3.5.2  編譯器指示與源程序行列表        47
3.5.3  符號表中的標識符條目        47
3.5.4  詞法分析器的終止        48
3.5.5  多字符的超前搜索        48
3.5.6  詞法錯誤恢復        49
3.6  將正則表達式轉換為有限自動機        51
3.6.1  構造確定的有限自動機        52
3.6.2  優(yōu)化有限自動機        54
練習        55
第4章  文法和語法分析        59
4.1  上下文無關文法：概念與記號        59
4.2  上下文無關文法中的錯誤        61
4.3  轉換擴展 BNF文法        62
4.4  語法分析器與識別器        63
4.5  文法分析算法        64
練習        69
第5章  LL(1)文法及分析器        71
5.1  LL(1) Predict函數(shù)        71
5.2  LL(1)分析表        73
5.3  從LL(1)分析表構造遞歸下降分析器        74
5.4  LL(1)分析器驅動程序        77
5.5  LL(1)動作符號        77
5.6  文法的LL(1)化        78
5.7  LL(1)分析中的If-Then-Else問題        81
5.8  LLGen—LL(1)語法分析器生成器        82
5.9  LL(1)分析器的性質        85
5.10  LL(k)分析        85
練習        87
第6章  LR分析        89
6.1  移進-歸約分析器        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)技術的局限性        104
6.5  LALR(1)分析        105
6.5.1  構造LALR(1)分析器        108
6.5.2  LALR(1)分析的正確性        112
6.6  在移進-歸約分析器中調用語義例程        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  實用的LR(1)分析器        123
6.10  LR分析的性質        125
6.11  LL(1)和LALR(1)分析方法的比較        125
6.12  其他的移進-歸約技術        128
6.12.1  擴展的超前搜索技術        128
6.12.2  優(yōu)先級技術        128
6.12.3  一般的上下文無關分析器        130
練習        132
第7章  語義處理        137
7.1  語法制導翻譯        137
7.1.1  使用分析的語法樹表示        137
7.1.2  編譯器組織的候選形式        138
7.1.3  一遍編譯中的分析、檢查和翻譯        142
7.2  語義處理技術        143
7.2.1  LL分析器和動作符號        143
7.2.2  LR分析器和動作符號        143
7.2.3  語義記錄表示        144
7.2.4  實現(xiàn)動作控制的語義棧        146
7.2.5  分析器控制的語義棧        149
7.3  中間表示和代碼生成        155
7.3.1  比較中間表示和直接代碼生成        155
7.3.2  中間表示的形式        155
7.3.3  一個元組語言        157
練習        157
第8章  符號表        161
8.1  符號表接口        161
8.2  基本實現(xiàn)技術        162
8.2.1  二叉搜索樹        162
8.2.2  哈希表        163
8.2.3  串空間數(shù)組        164
8.3  塊結構符號表        165
8.4  塊結構符號表的擴展        169
8.4.1  域和記錄        169
8.4.2  導出規(guī)則        170
8.4.3  導入規(guī)則        174
8.4.4  可更改的搜索規(guī)則        175
8.5  隱式聲明        177
8.6  重載        177
8.7  前向引用        178
8.8  小結        180
練習        180
第9章  運行時存儲組織        183
9.1  靜態(tài)分配        183
9.2  棧分配        183
9.2.1  顯示表        185
9.2.2  塊級與過程級活動記錄        187
9.3  堆分配        188
9.3.1  無空間釋放        188
9.3.2  顯式釋放        188
9.3.3  隱式釋放        189
9.3.4  管理堆空間        190
9.4  內存中的程序布局        191
9.5  靜態(tài)鏈簇和動態(tài)鏈簇        193
9.6  形式過程        195
9.6.1  靜態(tài)鏈簇        196
9.6.2  顯示表        197
9.6.3  一些看法        198
練習        199
第10章  處理聲明        203
10.1  聲明處理的基本原則        203
10.1.1  符號表中的屬性        203
10.1.2  類型描述符結構        204
10.1.3  語義棧中的列表結構        205
10.2  簡單聲明的動作例程        207
10.2.1  變量聲明        207
10.2.2  類型定義、聲明和引用        209
10.2.3  記錄類型        212
10.2.4  靜態(tài)數(shù)組        214
10.3  高級特性的動作例程        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結構        236
練習        239
第11章  處理表達式和數(shù)據(jù)結構引用        241
11.1  概述        241
11.2  簡單名字、表達式和數(shù)據(jù)結構的動作例程        242
11.2.1  處理簡單標識符和文字常量        242
11.2.2  處理表達式        243
11.2.3  簡單的記錄和數(shù)組引用        246
11.2.4  記錄和數(shù)組示例        249
11.2.5  串        250
11.3  高級特性的動作例程        250
11.3.1  多維數(shù)組的組織和引用        250
11.3.2  含動態(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
練習        269
第12章  翻譯控制結構        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  短路計算布爾表達式        294
12.7.1  單地址短路計算        299
練習        305
第13章  翻譯過程和函數(shù)        309
13.1  簡單子程序        309
13.1.1  聲明無參子程序        309
13.1.2  調用無參過程        311
13.2  向子程序傳遞參數(shù)        312
13.2.1  值、結果和值-結果參數(shù)        313
13.2.2  引用和只讀參數(shù)        314
13.2.3  處理參數(shù)聲明的語義例程        314
13.3  處理子程序調用和參數(shù)表        316
13.4  子程序調用        317
13.4.1  保存和恢復寄存器        317
13.4.2  子程序的入口和出口        318
13.5  標號參數(shù)        321
13.6  名字參數(shù)        323
練習        324
第14章  屬性文法和多遍翻譯        327
14.1  屬性文法        327
14.1.1  簡單賦值形式和動作符號        329
14.1.2  樹遍歷的屬性計算程序        331
14.1.3  直接屬性計算程序        335
14.1.4  屬性文法示例        340
14.2  樹結構的中間表示        342
14.2.1  抽象語法樹接口        343
14.2.2  語法樹抽象接口        344
14.2.3  實現(xiàn)樹        348
練習        349
第15章  代碼生成和局部代碼優(yōu)化        351
15.1  概述        351
15.2  寄存器和臨時變量管理        352
15.2.1  臨時變量的分類        353
15.2.2  分配和釋放臨時變量        353
15.3  簡單的代碼生成器        354
15.4  解釋性代碼生成        356
15.4.1  優(yōu)化地址計算        357
15.4.2  避免冗余計算        359
15.4.3  寄存器追蹤        361
15.5  窺孔優(yōu)化        367
15.6  從樹結構生成代碼        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
練習        387
第16章  全局優(yōu)化        393
16.1  概述—目標與限制        393
16.1.1  理想的優(yōu)化編譯器結構        394
16.1.2  優(yōu)化展望        397
16.2  優(yōu)化子程序調用        397
16.2.1  子程序調用的內聯(lián)展開        397
16.2.2  優(yōu)化對封閉子例程的調用        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)中強度削弱        409
16.4  全局數(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)化技術        430
練習        431
第17章  現(xiàn)實世界中的語法分析        437
17.1  壓縮表        437
17.1.1  壓縮LL(1)分析表        439
17.2  語法錯誤的恢復與修復        440
17.2.1  即時錯誤檢測        442
17.2.2  遞歸下降分析器中的錯誤恢復        443
17.2.3  LL(1)分析器中的錯誤恢復        445
17.2.4  FMQ LL(1)錯誤修復算法        446
17.2.5  在FMQ修復算法中添加刪除操作        449
17.2.6  FMQ算法的擴展        450
17.2.7  利用LLGen進行錯誤修復        454
17.2.8  LR錯誤恢復        455
17.2.9  Yacc中的錯誤恢復        455
17.2.10  自動生成的LR修復技術        456
17.2.11  利用LALRGen進行錯誤修復        462
17.2.12  其他LR錯誤修復技術        462
練習        463
附錄A  Ada/CS語言定義        467
附錄B  ScanGen        487
附錄C  LLGen用戶手冊        493
附錄D  LALRGen用戶手冊        499
附錄E  LLGen和LALRGen錯誤修復特性        507
附錄F  編譯器開發(fā)實用工具        511
參考文獻        517
索引        523