編譯程序設(shè)計(jì)算法

第1章 緒論
編譯程序的基本概念
編譯程序的結(jié)構(gòu)
編譯程序的翻譯過(guò)程
遍
編譯程序的基本構(gòu)成
預(yù)備知識(shí)
字符串
集合運(yùn)算
關(guān)系
第2章 有窮狀態(tài)自動(dòng)機(jī)和正則表達(dá)式
有窮狀態(tài)自動(dòng)機(jī)
非確定性有窮狀態(tài)自動(dòng)機(jī)(NFA)
帶有s弧的非確定性有窮狀態(tài)自動(dòng)機(jī)
從NFA到DFA的轉(zhuǎn)換
狀態(tài)集合的g一閉包
子集構(gòu)造
DFA的化簡(jiǎn)
刪除不可達(dá)狀態(tài)的算法
識(shí)別并合并等價(jià)狀態(tài)
刪除死狀態(tài)的算法
正則集與正則表達(dá)式
正則表達(dá)式與有限自動(dòng)機(jī)
從正則表達(dá)式到有限自動(dòng)機(jī)
從有限自動(dòng)機(jī)到正則表達(dá)式
詞法分析器的設(shè)計(jì)
詞法分析器的設(shè)計(jì)步驟
正則表達(dá)式的LEX約定
LEX輸入文件的格式
第3章 上下文無(wú)關(guān)文法和語(yǔ)法分析
語(yǔ)法分析
上下文無(wú)關(guān)文法
推導(dǎo)
推導(dǎo)樹
上下文無(wú)關(guān)文法的化簡(jiǎn)
識(shí)別和刪除無(wú)用文法符號(hào)的算法
e一產(chǎn)生式和可空非終結(jié)符
消除單位產(chǎn)生式
消除左遞歸
正則文法
第4章 自頂向下的語(yǔ)法分析
自頂向下的語(yǔ)法分析方法
帶預(yù)測(cè)的自頂向下語(yǔ)法分析器
表驅(qū)動(dòng)預(yù)測(cè)語(yǔ)法分析器的實(shí)現(xiàn)
例題
第5章 自底向上的語(yǔ)法分析
右句型中的句柄
自底向上的語(yǔ)法分析的實(shí)現(xiàn)
LR語(yǔ)法分析器
擴(kuò)展文法
尋找LR(0)項(xiàng)目集規(guī)范族的算法
SLR(1)語(yǔ)法分析器的Action表和Goto表
計(jì)算LR(1)項(xiàng)目集規(guī)范族的算法
LR(1)語(yǔ)法分析器的ActionIGoto表
LALR的語(yǔ)法分析表
語(yǔ)法分析器的沖突
處理二義性文法
語(yǔ)法分析表的數(shù)據(jù)結(jié)構(gòu)
Action表的數(shù)據(jù)結(jié)構(gòu)
Goto表的數(shù)據(jù)結(jié)構(gòu)
LR語(yǔ)法分析器的優(yōu)點(diǎn)和缺點(diǎn)
第6章 語(yǔ)法制導(dǎo)的定義和翻譯
翻譯規(guī)范
通過(guò)語(yǔ)法制導(dǎo)定義實(shí)現(xiàn)指定翻譯
綜合屬性
繼承屬性
虛擬綜合屬性
L-屬性定義
語(yǔ)法制導(dǎo)翻譯方案
生成中間代碼
后綴表示法
語(yǔ)法樹
三地址代碼
三地址語(yǔ)句表示
四元式表示
三元式表示
間接三元式表示
比較
不同程序設(shè)計(jì)語(yǔ)言結(jié)構(gòu)的語(yǔ)法制導(dǎo)翻譯方案
算術(shù)表達(dá)式
布爾表達(dá)式
邏輯表達(dá)式的短路代碼
遞增和遞減運(yùn)算符的實(shí)現(xiàn)
數(shù)組引用
SWITC：H／CASE
過(guò)程調(diào)用
舉例
第7章 符號(hào)表管理
符號(hào)表
添加信息到符號(hào)表中
組織符號(hào)表的方法
線性表
查找樹
哈希表
描述符號(hào)表中的域信息
第8章 存儲(chǔ)管理
存儲(chǔ)分配
過(guò)程激活與活動(dòng)記錄
靜態(tài)分配
堆棧分配
調(diào)用和返回順序
訪問(wèn)非局部名字
設(shè)置訪問(wèn)鏈
第9章 出錯(cuò)處理
錯(cuò)誤恢復(fù)
詞法階段的錯(cuò)誤恢復(fù)
語(yǔ)法階段的錯(cuò)誤恢復(fù)
LR分析中的錯(cuò)誤恢復(fù)
YACC中的自動(dòng)錯(cuò)誤恢復(fù)
預(yù)測(cè)性分析的錯(cuò)誤恢復(fù)
語(yǔ)義錯(cuò)誤恢復(fù)
第10章 代碼優(yōu)化
什么是代碼優(yōu)化
循環(huán)優(yōu)化
消除循環(huán)不變量的計(jì)算
將三地址代碼分成基本塊的算法
尋找循環(huán)
尋找回邊
可化簡(jiǎn)的流圖
消除歸納變量
刪除本地公共子表達(dá)式
刪除全局公共子表達(dá)式
打開(kāi)循環(huán)
循環(huán)擁塞
第11章 代碼生成
高效代碼生成中隱含的主要問(wèn)題
目標(biāo)機(jī)器模型
直接代碼生成
DAG的目標(biāo)代碼生成
啟發(fā)式DAG排序算法
標(biāo)記算法
利用代數(shù)性質(zhì)來(lái)減少寄存器的需要數(shù)量
窺孔優(yōu)化
冗余存取
控制流程優(yōu)化
刪除不可達(dá)代碼
代數(shù)簡(jiǎn)化
強(qiáng)制削弱