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

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