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