編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)

第一章編譯程序概述
1.1編譯程序和解釋程序
1.2編譯程序的功能分解和組織結(jié)構(gòu)
1.3編譯程序的復(fù)雜性
1.4編譯程序的設(shè)計(jì)實(shí)現(xiàn)
1.5編譯程序的測試與維護(hù)
1.6幾個經(jīng)典編譯程序
第二章一個微小編譯器
2.1微小語言Micro
2.2Micro的詞法分析
2.3Micro的語法分析
2.4Micro的語義分析
2.5Micro的目標(biāo)代碼
練習(xí)題
第三章有限自動機(jī)與詞法分析器
3.1詞法分析
3.1.1詞法分析器的功能
3.1.2單詞的內(nèi)部表示
3.1.3保留字
3.1.4空格符.制表符和換行符
3.1.5括號類配對預(yù)檢
3.1.6向前看多個字符的處理
3.1.7字符串空間
3.1.8詞法錯誤校正
3.1.9詞法分析的結(jié)束
3.2正則表達(dá)式
3.2.1基本概念
3.2.2正則表達(dá)式及其一些性質(zhì)
3.2.3正則定義
3.2.4正則表達(dá)式的局限性
3.3有限自動機(jī)(FA)
3.3.1確定有限自動機(jī)(DFA)
3.3.2確定有限自動機(jī)的實(shí)現(xiàn)
3.3.3非確定有限自動機(jī)(NFA)
3.3.4NFA到DFA的轉(zhuǎn)換
3.3.5確定有限自動機(jī)的化簡
3.3.6正則表達(dá)式到DFA的轉(zhuǎn)換
3.4詞法分析器的構(gòu)造
3.4.1用DFA人工構(gòu)造詞法分析器
3.4.2使用詞法分析器的生成器ScanGen
3.4.3Lex
練習(xí)題
第四章文法與語法分析
4.1語法分析的功能
4.1.1語法分析器和識別器
4.1.2語法分析器的輸入
4.1.3語法錯誤類別及關(guān)鍵性錯誤
4.1.4語法錯誤處理
4.2上下文無關(guān)文法
4.2.1文法和語言
4.2.2最左推導(dǎo)和最右推導(dǎo)
4.2.3語法分析樹與二義性
4.2.4文法分析算法
4.2.5自頂向下方法概述
4.2.6自底向上方法概述
4.3遞歸下降法--自頂向下分析
4.3.1遞歸下降法原理
4.3.2消除公共前綴
4.3.3消除左遞歸
4.4LL分析方法--自頂向下分析
4.4.1LL(1)文法
4.4.2LL(1)分析表
4.4.3LL(1)分析的驅(qū)動器
4.4.4LL(1)中的if-then-else問題
4.4.5LL(1)分析器的自動生成器LLGen
4.5LR方法--自底向上分析
4.5.1句柄
4.5.2活前綴和歸約活前綴
4.5.3線性正則式的狀態(tài)機(jī)
4.5.4LR狀態(tài)機(jī)的構(gòu)造
4.5.5LR(0)和SLR(1)文法
4.5.6LR(1)文法
4.5.7LALR(1)文法
4.5.8二義性文法的處理
4.5.9另一種Shift-Reduce分析技術(shù)
4.5.10LL(1)與LALR(1)的比較
4.6LR分析器的生成器
4.6.1LALR分析器的生成器Yacc
4.6.2LALR分析器的生成器LALRGen
4.7語法錯誤處理
4.7.1錯誤恢復(fù)和錯誤修復(fù)
4.7.2遞歸下降分析的錯誤恢復(fù)
4.7.3LL分析的錯誤恢復(fù)
4.7.4LR分析的錯誤恢復(fù)
練習(xí)題
第五章語義分析
5.1語義分析基礎(chǔ)
5.1.1語義分析內(nèi)容
5.1.2標(biāo)識符的內(nèi)部表示
5.1.3類型的內(nèi)部表示
5.1.4值的內(nèi)部表示
5.2符號表
5.2.1表處理技術(shù)
5.2.2符號表的局部化
5.2.3二叉式局部符號表
5.2.4散列式全局符號表
5.2.5嵌套式局部符號表
5.2.6符號表界面
5.3類型表達(dá)式
5.3.1類型的等價性和相容性
5.3.2類型的分析
5.3.3枚舉類型--EnumTYPE
5.3.4子界類型--SubRangeTYPE
5.3.5數(shù)組類型--ArrayTYPE
5.3.6集合類型--SetTYPE
5.3.7文件類型--FileTYPE
5.3.8指針類型--PointerTYPE
5.3.9記錄類RecordTYPE
5.4聲明的語義分析
5.4.1標(biāo)號聲明部分--kabelDecPart
5.4.2常量聲明部分--ConstDecPart
5.4.3類型聲明部分--TypeDecPart
5.4.4變量聲明部分--VarDecPart
5.4.5子程序首部--RoutHead
5.4.6過程／函數(shù)的向前聲明
5.5執(zhí)行體Body的語義分析
5.5.1表達(dá)式分析
5.5.2定位性標(biāo)號和使用性標(biāo)號
5.5.3賦值語句和調(diào)用語句分析
5.5.4結(jié)構(gòu)語句分析
練習(xí)題
第六章運(yùn)行時的存儲空間
6.1運(yùn)行時的存儲空間結(jié)構(gòu)
6.2運(yùn)行時的存儲空間分配
6.2.1靜態(tài)區(qū)的存儲分配
6.2.2棧區(qū)的存儲分配
6.2.3堆區(qū)的存儲分配
6.2.4堆區(qū)空間管理
6.3運(yùn)行時的過程活動記錄與棧區(qū)的組織結(jié)構(gòu)
6.3.1過程活動記錄(ActivationRecord)
6.3.2動態(tài)鏈(DynamicChain)
6.3.3活躍活動記錄
6.4運(yùn)行時的變量訪問
6.4.1變量的訪問環(huán)境
6.4.2局部Display表方法
6.4.3靜態(tài)鏈方法(StaticChain)
6.4.4全局Display表方法和寄存器方法
6.5非正常出口和形式過程語句
6.5.1非正常出口的動態(tài)鏈和Display表
6.5.2形式過程語句和Display表
6.5.3奇特型調(diào)用和DisplaY表
6.6分程序記錄和動態(tài)數(shù)組空間
6.6.1分程序的記錄
6.6.2動態(tài)數(shù)組的分配
練習(xí)題
第七章動作文法和屬性文法
7.1動作文法(ActionGrammar)
7.1.1動作符(ActionSymb01)
7.1.2動作文法(ActionGrammar)
7.1.3尾動作文法
7.1.4抽象動作文法
7.2動作文法的實(shí)現(xiàn)
7.2.1動作文法的LL實(shí)現(xiàn)
7.2.2動作文法的LR實(shí)現(xiàn)
7.2.3Yacc--LALR分析器的生成器
7.3屬性文法
7.3.1屬性文法的定義
7.3.2繼承屬性和綜合屬性
7.3.3屬性規(guī)則
7.3.4屬性樹和屬性依賴圖
7,3.5屬性求值
7.3.6拷貝型屬性文法
7.4屬性文法在編譯器設(shè)計(jì)中的應(yīng)用
7.4.1類型分析的屬性文法描述
7.4.2聲明分析的屬性文法描述
7.4.3語句分析的屬性文法描述
7.5S--屬性文法及其屬性求值
7.5.1S--屬性文法
7.5.2S--屬性文法的遞歸實(shí)現(xiàn)--自頂向下求值
7.5.3S--屬性文法的LL實(shí)現(xiàn)--自頂向下求值
7.5.4S--屬性文法的LR實(shí)現(xiàn)--自底向上求值
7.6L--屬性文法及其屬性求值
7.6.1L--屬性文法
7.6.2LL--L屬性文法的遞歸實(shí)現(xiàn)--自頂向下求值
7.6.3LL--L屬性文法的LL實(shí)現(xiàn)--自頂向下求值
7.6.4L--屬性文法的棧式遍歷樹實(shí)現(xiàn)
7.6.5LR--L屬性文法的LR實(shí)現(xiàn)--自底向上求值
7.6.6LALR分析器的生成器LALRGen
練習(xí)題
第八章中間代碼生成
8.1中間語言
8.1.1中間語言設(shè)置和直接代碼生成
8.1.2棧式中間代碼--后綴式
8.1.3三地址中間代碼
8.1.4抽象語法樹和DAG
8.1.5多元式中間代碼
8.2簡單表達(dá)式的中間代碼生成
8.2.1表達(dá)式的語義信息
8.2.2表達(dá)式的中間代碼結(jié)構(gòu)
8.2.3類型轉(zhuǎn)換
8.2.4表達(dá)式中間代碼的生成
8.2.5布爾表達(dá)式的短路中間代碼
8.2.6變量的中間代碼
8,3多維下標(biāo)變量的中間代碼生成
8.3.1多維下標(biāo)變量
8.3.2多維下標(biāo)變量的地址公式
8.3.3多維下標(biāo)變量的中間代碼結(jié)構(gòu)
8.4原子語句的中間代碼
8.4.1輸入輸出語句的中間代碼
8.4.2賦值語句的中間代碼
8.4.3過程調(diào)用和函數(shù)調(diào)用的中間代碼
8.4.4GOTD語句和標(biāo)號定位的中間代碼
8.5結(jié)構(gòu)語句的中間代碼
8.5.1條件語句的中間代碼
8.5.2While語句的中間代碼
8.5.3Repeat語句的中間代碼
8.5.4For語句的中間代碼
8.5.5Case語句的中間代碼
8.6聲明的中間代碼
8.6.1變量聲明的中間代碼
8.6.2過程和函數(shù)的中間代碼
練習(xí)題
第九章中間代碼優(yōu)化
9.1引言
9.1.1優(yōu)化目標(biāo)和要求
9.1.2優(yōu)化的必要性
9.1.3優(yōu)化內(nèi)容和難點(diǎn)
9.1.4局部優(yōu)化和全局優(yōu)化
9.1.5基本塊和程序流圖
9.2常量表達(dá)式優(yōu)化
9.2.1常量表達(dá)式的局部優(yōu)化
9.2.2基于常量定值分析的常量表達(dá)式全局優(yōu)化
9.2.3可用常量定值的數(shù)據(jù)流分析
9.3公共表達(dá)式優(yōu)化
9.3.1基于相似性的公共表達(dá)式局部優(yōu)化
9.3.2基于值編碼的公共表達(dá)式局部優(yōu)化
9.3.3基于DAG的公共表達(dá)式局部優(yōu)化
9.3.4基于可用表達(dá)式分析的公共表達(dá)式全局優(yōu)化
9.3.5可用表達(dá)式定值的數(shù)據(jù)流分析
9.4循環(huán)不變表達(dá)式外提
9.4.1循環(huán)識別
9.4.2外提對象和安全性
9.4.3不變式外提的實(shí)現(xiàn)原理
9.4.4過程／函數(shù)的副作用分析
9.4.5一種簡單的外提優(yōu)化
9.4.6循環(huán)必經(jīng)點(diǎn)分析
9.5循環(huán)內(nèi)歸納表達(dá)式的優(yōu)化
9.5.1歸納變量和歸納表達(dá)式
9.5.2歸納表達(dá)式的優(yōu)化原理
9.5.3乘法運(yùn)算的強(qiáng)度削減優(yōu)化
練習(xí)題
第十章目標(biāo)代碼生成
10.1目標(biāo)代碼
10.1.1虛擬目標(biāo)代碼
10.1.2實(shí)際目標(biāo)代碼
10.1.3窺孔優(yōu)化
10.2臨時變量
10.2.1臨時變量的特點(diǎn)
10.2.2臨時變量的存儲空間
10.2.3變量的狀態(tài)描述
10.3寄存器
10.3.1寄存器分類
10.3.2寄存器的狀態(tài)描述
10.3.3寄存器的分配
10.3.4寄存器的釋放代價
10.4基于多元式的代碼生成
10.4.1編址模式(AddressingMode)
10.4.2間接編址模式的轉(zhuǎn)換
10.4.3目標(biāo)代碼生成基本技術(shù)
10.4.4其他寄存器的狀態(tài)追蹤
10.5基于樹結(jié)構(gòu)的代碼生成
10.5.1多元式到樹的轉(zhuǎn)換
10.5.2計(jì)算寄存器個數(shù)
10.5.3從帶寄存器個數(shù)標(biāo)記的樹生成代碼
10.6基于DAG的代碼生成
10.6.1從樹構(gòu)造DAG
10.6.2給DAG結(jié)點(diǎn)標(biāo)上序號和虛寄存器
10.6.3從帶排序和虛寄存器標(biāo)記的DAG生成代碼
10.7代碼生成器的生成器
10.7.1代碼生成器的自動化
10.7.2基于指令模板匹配的代碼生成技術(shù)
10.7.3基于語法分析的代碼生成技術(shù)
10.8其他
10.8.1標(biāo)號和GOTO的代碼生成
10.8.2過程／函數(shù)調(diào)用的代碼生成
練習(xí)題
參考文獻(xiàn)