編譯程序設計算法

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