編譯器設(shè)計(jì)（第2版）

第1章 　編譯概觀
1.1 　簡(jiǎn)介
1.2 　編譯器結(jié)構(gòu)
1.3 　轉(zhuǎn)換概述
1.3.1 　前端
1.3.2 　優(yōu)化器
1.3.3 　后端
1.4 　小結(jié)和展望
第2章 　詞法分析器
2.1 　簡(jiǎn)介
2.2 　識(shí)別單詞
2.2.1 　識(shí)別器的形式化
2.2.2 　識(shí)別更復(fù)雜的單詞
2.3 　正則表達(dá)式
2.3.1 　符號(hào)表示法的形式化
2.3.2 　示例
2.3.3 　RE的閉包性質(zhì)
2.4 　從正則表達(dá)式到詞法分析器
2.4.1 　非確定性有限自動(dòng)機(jī)
2.4.2 　從正則表達(dá)式到NFA：Thompson構(gòu)造法
2.4.3 　從NFA到DFA：子集構(gòu)造法
2.4.4 　從DFA到最小DFA：Hopcroft算法
2.4.5 　將DFA用做識(shí)別器
2.5 　實(shí)現(xiàn)詞法分析器
2.5.1 　表驅(qū)動(dòng)詞法分析器
2.5.2 　直接編碼的詞法分析器
2.5.3 　手工編碼的詞法分析器
2.5.4 　處理關(guān)鍵字
2.6 　高級(jí)主題
2.6.1 　從DFA到正則表達(dá)式
2.6.2 　DFA最小化的另一種方法：Brzozowski算法
2.6.3 　無(wú)閉包的正則表達(dá)式
2.7 　小結(jié)和展望
第3章 　語(yǔ)法分析器
3.1 　簡(jiǎn)介
3.2 　語(yǔ)法的表示
3.2.1 　為什么不使用正則表達(dá)式
3.2.2 　上下文無(wú)關(guān)語(yǔ)法
3.2.3 　更復(fù)雜的例子
3.2.4 　將語(yǔ)義編碼到結(jié)構(gòu)中
3.2.5 　為輸入符號(hào)串找到推導(dǎo)
3.3 　自頂向下語(yǔ)法分析
3.3.1 　為進(jìn)行自頂向下語(yǔ)法分析而轉(zhuǎn)換語(yǔ)法
3.3.2 　自頂向下的遞歸下降語(yǔ)法分析器
3.3.3 　表驅(qū)動(dòng)的LL(1)語(yǔ)法分析器
3.4 　自底向上語(yǔ)法分析
3.4.1 　LR(1)語(yǔ)法分析算法
3.4.2 　構(gòu)建LR(1)表
3.4.3 　表構(gòu)造過(guò)程中的錯(cuò)誤
3.5 　實(shí)際問(wèn)題
3.5.1 　出錯(cuò)恢復(fù)
3.5.2 　一元運(yùn)算符
3.5.3 　處理上下文相關(guān)的二義性
3.5.4 　左遞歸與右遞歸
3.6 　高級(jí)主題
3.6.1 　優(yōu)化語(yǔ)法
3.6.2 　減小LR(1)表的規(guī)模
3.7 　小結(jié)和展望
第4章 　上下文相關(guān)分析
4.1 　簡(jiǎn)介
4.2 　類(lèi)型系統(tǒng)簡(jiǎn)介
4.2.1 　類(lèi)型系統(tǒng)的目標(biāo)
4.2.2 　類(lèi)型系統(tǒng)的組件
4.3 　屬性語(yǔ)法框架
4.3.1 　求值的方法
4.3.2 　環(huán)
4.3.3 　擴(kuò)展實(shí)例
4.3.4 　屬性語(yǔ)法方法的問(wèn)題
4.4 　特設(shè)語(yǔ)法制導(dǎo)轉(zhuǎn)換
4.4.1 　特設(shè)語(yǔ)法制導(dǎo)轉(zhuǎn)換的實(shí)現(xiàn)
4.4.2 　例子
4.5 　高級(jí)主題
4.5.1 　類(lèi)型推斷中更困難的問(wèn)題
4.5.2 　改變結(jié)合性
4.6 　小結(jié)和展望
第5章 　中間表示
5.1 　簡(jiǎn)介
5.2 　圖IR
5.2.1 　與語(yǔ)法相關(guān)的樹(shù)
5.2.2 　圖
5.3 　線性IR
5.3.1 　堆棧機(jī)代碼
5.3.2 　三地址代碼
5.3.3 　線性代碼的表示
5.3.4 　根據(jù)線性代碼建立控制流圖
5.4 　將值映射到名字
5.4.1 　臨時(shí)值的命名
5.4.2 　靜態(tài)單賦值形式
5.4.3 　內(nèi)存模型
5.5 　符號(hào)表
5.5.1 　散列表
5.5.2 　建立符號(hào)表
5.5.3 　處理嵌套的作用域
5.5.4 　符號(hào)表的許多用途
5.5.5 　符號(hào)表技術(shù)的其他用途
5.6 　小結(jié)和展望
第6章 　過(guò)程抽象
6.1 　簡(jiǎn)介
6.2 　過(guò)程調(diào)用
6.3 　命名空間
6.3.1 　類(lèi)Algol語(yǔ)言的命名空間
6.3.2 　用于支持類(lèi)Algol語(yǔ)言的運(yùn)行時(shí)結(jié)構(gòu)
6.3.3 　面向?qū)ο笳Z(yǔ)言的命名空間
6.3.4 　支持面向?qū)ο笳Z(yǔ)言的運(yùn)行時(shí)結(jié)構(gòu)
6.4 　過(guò)程之間值的傳遞
6.4.1 　傳遞參數(shù)
6.4.2 　返回值
6.4.3 　確定可尋址性
6.5 　標(biāo)準(zhǔn)化鏈接
6.6 　高級(jí)主題
6.6.1 　堆的顯式管理
6.6.2 　隱式釋放
6.7 　小結(jié)和展望
第7章 　代碼形式
7.1 　簡(jiǎn)介
7.2 　分配存儲(chǔ)位置
7.2.1 　設(shè)定運(yùn)行時(shí)數(shù)據(jù)結(jié)構(gòu)的位置
7.2.2 　數(shù)據(jù)區(qū)的布局
7.2.3 　將值保持在寄存器中
7.3 　算術(shù)運(yùn)算符
7.3.1 　減少對(duì)寄存器的需求
7.3.2 　訪問(wèn)參數(shù)值
7.3.3 　表達(dá)式中的函數(shù)調(diào)用
7.3.4 　其他算術(shù)運(yùn)算符
7.3.5 　混合類(lèi)型表達(dá)式
7.3.6 　作為運(yùn)算符的賦值操作
7.4 　布爾運(yùn)算符和關(guān)系運(yùn)算符
7.4.1 　表示
7.4.2 　對(duì)關(guān)系操作的硬件支持
7.5 　數(shù)組的存儲(chǔ)和訪問(wèn)
7.5.1 　引用向量元素
7.5.2 　數(shù)組存儲(chǔ)布局
7.5.3 　引用數(shù)組元素
7.5.4 　范圍檢查
7.6 　字符串
7.6.1 　字符串表示
7.6.2 　字符串賦值
7.6.3 　字符串連接
7.6.4 　字符串長(zhǎng)度
7.7 　結(jié)構(gòu)引用
7.7.1 　理解結(jié)構(gòu)布局
7.7.2 　結(jié)構(gòu)數(shù)組
7.7.3 　聯(lián)合和運(yùn)行時(shí)標(biāo)記
7.7.4 　指針和匿名值
7.8 　控制流結(jié)構(gòu)
7.8.1 　條件執(zhí)行
7.8.2 　循環(huán)和迭代
7.8.3 　case語(yǔ)句
7.9 　過(guò)程調(diào)用
7.9.1 　實(shí)參求值
7.9.2 　保存和恢復(fù)寄存器
7.10 　小結(jié)和展望
第8章 　優(yōu)化簡(jiǎn)介
8.1 　簡(jiǎn)介
8.2 　背景
8.2.1 　例子
8.2.2 　對(duì)優(yōu)化的考慮
8.2.3 　優(yōu)化的時(shí)機(jī)
8.3 　優(yōu)化的范圍
8.4 　局部?jī)?yōu)化
8.4.1 　局部值編號(hào)
8.4.2 　樹(shù)高平衡
8.5 　區(qū)域優(yōu)化
8.5.1 　超局部值編號(hào)
8.5.2 　循環(huán)展開(kāi)
8.6 　全局優(yōu)化
8.6.1 　利用活動(dòng)信息查找未初始化變量
8.6.2 　全局代碼置放
8.7 　過(guò)程間優(yōu)化
8.7.1 　內(nèi)聯(lián)替換
8.7.2 　過(guò)程置放
8.7.3 　針對(duì)過(guò)程間優(yōu)化的編譯器組織結(jié)構(gòu)
8.8 　小結(jié)和展望
第9章 　數(shù)據(jù)流分析
9.1 　簡(jiǎn)介
9.2 　迭代數(shù)據(jù)流分析
9.2.1 　支配性
9.2.2 　活動(dòng)變量分析
9.2.3 　數(shù)據(jù)流分析的局限性
9.2.4 　其他數(shù)據(jù)流問(wèn)題
9.3 　靜態(tài)單賦值形式
9.3.1 　構(gòu)造靜態(tài)單賦值形式的簡(jiǎn)單方法
9.3.2 　支配邊界
9.3.3 　放置 函數(shù)
9.3.4 　重命名
9.3.5 　從靜態(tài)單賦值形式到其他形式的轉(zhuǎn)換
9.3.6 　使用靜態(tài)單賦值形式
9.4 　過(guò)程間分析
9.4.1 　構(gòu)建調(diào)用圖
9.4.2 　過(guò)程間常量傳播
9.5 　高級(jí)主題
9.5.1 　結(jié)構(gòu)性數(shù)據(jù)流算法和可歸約性
9.5.2 　加速計(jì)算支配性的迭代框架算法的執(zhí)行
9.6 　小結(jié)和展望
第10章 　標(biāo)量?jī)?yōu)化
10.1 　簡(jiǎn)介
10.2 　消除無(wú)用和不可達(dá)代碼
10.2.1 　消除無(wú)用代碼
10.2.2 　消除無(wú)用控制流
10.2.3 　消除不可達(dá)代碼
10.3 　代碼移動(dòng)
10.3.1 　緩式代碼移動(dòng)
10.3.2 　代碼提升
10.4 　特化
10.4.1 　尾調(diào)用優(yōu)化
10.4.2 　葉調(diào)用優(yōu)化
10.4.3 　參數(shù)提升
10.5 　冗余消除
10.5.1 　值相同與名字相同
10.5.2 　基于支配者的值編號(hào)算法
10.6 　為其他變換制造時(shí)機(jī)
10.6.1 　超級(jí)塊復(fù)制
10.6.2 　過(guò)程復(fù)制
10.6.3 　循環(huán)外提
10.6.4 　重命名
10.7 　高級(jí)主題
10.7.1 　合并優(yōu)化
10.7.2 　強(qiáng)度削減
10.7.3 　選擇一種優(yōu)化序列
10.8 　小結(jié)和展望
第11章 　指令選擇
11.1 　簡(jiǎn)介
11.2 　代碼生成
11.3 　擴(kuò)展簡(jiǎn)單的樹(shù)遍歷方案
11.4 　通過(guò)樹(shù)模式匹配進(jìn)行指令選擇
11.4.1 　重寫(xiě)規(guī)則
11.4.2 　找到平鋪方案
11.4.3 　工具
11.5 　通過(guò)窺孔優(yōu)化進(jìn)行指令選擇
11.5.1 　窺孔優(yōu)化
11.5.2 　窺孔變換程序
11.6 　高級(jí)主題
11.6.1 　學(xué)習(xí)窺孔模式
11.6.2 　生成指令序列
11.7 　小結(jié)和展望
第12章 　指令調(diào)度
12.1 　簡(jiǎn)介
12.2 　指令調(diào)度問(wèn)題
12.2.1 　度量調(diào)度質(zhì)量的其他方式
12.2.2 　是什么使調(diào)度這樣難
12.3 　局部表調(diào)度
12.3.1 　算法
12.3.2 　調(diào)度具有可變延遲的操作
12.3.3 　擴(kuò)展算法
12.3.4 　在表調(diào)度算法中打破平局
12.3.5 　前向表調(diào)度與后向表調(diào)度
12.3.6 　提高表調(diào)度的效率
12.4 　區(qū)域性調(diào)度
12.4.1 　調(diào)度擴(kuò)展基本程序塊
12.4.2 　跟蹤調(diào)度
12.4.3 　通過(guò)復(fù)制構(gòu)建適當(dāng)?shù)纳舷挛沫h(huán)境
12.5 　高級(jí)主題
12.5.1 　軟件流水線的策略
12.5.2 　用于實(shí)現(xiàn)軟件流水線的算法
12.6 　小結(jié)和展望
第13章 　寄存器分配
13.1 　簡(jiǎn)介
13.2 　背景問(wèn)題
13.2.1 　內(nèi)存與寄存器
13.2.2 　分配與指派
13.2.3 　寄存器類(lèi)別
13.3 　局部寄存器分配和指派
13.3.1 　自頂向下的局部寄存器分配
13.3.2 　自底向上的局部寄存器分配
13.3.3 　超越單個(gè)程序塊
13.4 　全局寄存器分配和指派
13.4.1 　找到全局活動(dòng)范圍
13.4.2 　估算全局逐出代價(jià)
13.4.3 　沖突和沖突圖
13.4.4 　自頂向下著色
13.4.5 　自底向上著色
13.4.6 　合并副本以減小度數(shù)
13.4.7 　比較自頂向下和自底向上全局分配器
13.4.8 　將機(jī)器的約束條件編碼到?jīng)_突圖中
13.5 　高級(jí)主題
13.5.1 　圖著色寄存器分配方法的變體
13.5.2 　靜態(tài)單賦值形式上的全局寄存器分配
13.6 　小結(jié)和展望
附錄A 　ILOC
附錄B 　數(shù)據(jù)結(jié)構(gòu)
參考文獻(xiàn)
索引