編譯程序設計原理與技術

第1章形式語言與自動機基礎
1.1語言和文法
1.1.1字母表和符號串
1.1.2語言
1.1.3文法及其形式定義
1.1.4推導和短語
1.1.5分析樹及二義性
1.1.6文法的變換
1.2自動機與正規(guī)表達式
1.2.1確定的有限自動機(DFA)
1.2.2非確定的有限自動機(NFA)
1.2.3具有-轉移的非確定的有限自動機
1.2.4正規(guī)文法與有限自動機的等價性
1.2.5正規(guī)表達式與有限自動機的等價性
1.2.6正規(guī)表達式與正規(guī)文法
1.2.7DFA的化簡
習題
第2章編譯概述
2.1翻譯和解釋
2.1.1程序設計語言
2.1.2翻譯程序
2.2編譯的階段
2.2.1分析階段
2.2.2綜合階段
2.2.3符號表管理
2.2.4錯誤處理
2.2.5前端和后端
2.2.6“遍”的概念
2.3編譯程序的前后處理器
2.3.1預處理器
2.3.2匯編程序
2.3.3連接裝配程序
2.4編譯原理和技術的應用
習題
第3章詞法分析
3.1詞法分析器的作用
3.1.1詞法分析器與語法分析器的關系
3.1.2分離詞法分析器的好處
3.2詞法分析器的輸入與輸出
3.2.1設置輸入緩沖器的必要性
3.2.2配對緩沖器
3.2.3詞法分析器的輸出
3.3記號的描述和識別
3.3.1詞法與正規(guī)文法
3.3.2記號的文法
3.3.3狀態(tài)轉換圖與記號的識別
3.4詞法分析程序的設計與實現(xiàn)
3.4.1文法及狀態(tài)轉換圖
3.4.2詞法分析器的構造
3.4.3詞法分析器的實現(xiàn)
3.5軟件工具LEX
3.5.1LEX規(guī)格說明
3.5.2LEX的工作原理
習題
第4章語法分析
4.1語法分析器的作用
4.1.1語法分析器的地位
4.1.2常用的分析方法
4.1.3語法錯誤的處理
4.2自頂向下分析
4.2.1遞歸下降分析方法
4.2.2預測分析器
4.2.3非遞歸的預測分析器
4.3自底向上分析
4.3.1規(guī)范歸約
4.3.2“移進-歸約”方法的實現(xiàn)
4.4LR分析器
4.4.1LR分析器的模型及工作過程
4.4.2SLR分析表的構造
4.4.3LR(1)分析表的構造
4.4.4LALR分析表的構造
4.4.5LR分析方法對二義文法的應用
4.4.6LR分析的錯誤處理與恢復
4.5軟件工具YACC
4.5.1YACC說明文件
4.5.2用YACC處理二義文法
4.5.3用LEX建立YACC的詞法分析器
4.5.4YACC內部名稱
習題
第5章語法制導翻譯技術
5.1語法制導定義
5.1.1語法制導定義的形式
5.1.2綜合屬性
5.1.3繼承屬性
5.1.4依賴圖
5.1.5計算次序
5.2S屬性定義的自底向上翻譯
5.2.1語法樹
5.2.2構造表達式的語法樹
5.2.3構造表達式的語法樹的語法制導定義
5.2.4表達式的有向非循環(huán)圖(dag)
5.2.5S屬性定義的自底向上實現(xiàn)
5.3L屬性定義
5.3.1L屬性定義
5.3.2翻譯方案
5.4L屬性定義的自頂向下翻譯
5.4.1消除翻譯方案中的左遞歸
5.4.2預測翻譯器的設計
5.5L屬性定義的自底向上翻譯
5.5.1從翻譯方案中去掉嵌入的動作
5.5.2分析棧中的繼承屬性
5.5.3模擬繼承屬性的計算
5.5.4用綜合屬性代替繼承屬性
5.6非L屬性定義的翻譯
5.6.1從左到右遍歷子結點
5.6.2其他遍歷順序
習題
第6章類型檢查
6.1語義分析的概念
6.2類型體制
6.2.1類型表達式
6.2.2類型體制
6.2.3靜態(tài)和動態(tài)類型檢查
6.2.4錯誤恢復
6.3簡單類型檢查器的說明
6.3.1語言說明
6.3.2確定標識符的類型
6.3.3表達式的類型檢查
6.3.4語句的類型檢查
6.4類型表達式的等價
6.4.1類型表達式的結構等價
6.4.2類型表達式的名字等價
6.4.3類型表示中的環(huán)
6.5類型檢查有關的其他主題
6.5.1函數(shù)和運算符的重載
6.5.2類型轉換
6.5.3多態(tài)函數(shù)
6.6符號表
6.6.1建立和訪問符號表的時機
6.6.2符號表的內容
6.6.3在符號表上的操作
6.6.4符號表的組織
習題
第7章運行時刻環(huán)境
7.1基本概念
7.1.1過程
7.1.2活動樹
7.1.3控制棧
7.1.4聲明的作用域
7.1.5名字的聯(lián)編
7.2存儲組織
7.2.1運行時刻內存的劃分
7.2.2活動記錄
7.2.3編譯時局部數(shù)據(jù)的安排
7.3存儲分配策略
7.3.1靜態(tài)存儲分配
7.3.2棧式存儲分配
7.3.3堆式存儲分配
7.4訪問非局部名字
7.4.1程序塊
7.4.2非嵌套過程的靜態(tài)作用域
7.4.3嵌套過程的靜態(tài)作用域
7.4.4動態(tài)作用域規(guī)則
7.5參數(shù)傳遞方式
7.5.1傳值調用
7.5.2引用調用
7.5.3復制恢復
7.5.4傳名調用
習題
第8章中間代碼生成
8.1中間語言
8.1.1圖示法
8.1.2三地址代碼
8.1.3語法制導翻譯生成三地址代碼
8.2聲明語句的翻譯
8.2.1過程中的聲明語句
8.2.2過程定義的處理
8.2.3記錄聲明的處理
8.3賦值語句的翻譯
8.3.1表達式中僅涉及簡單變量的情況
8.3.2表達式中涉及數(shù)組元素的情況
8.3.3記錄中域的訪問
8.4布爾表達式的翻譯
8.4.1翻譯布爾表達式的方法
8.4.2數(shù)值表示法
8.4.3控制流語句
8.4.4布爾表達式的控制流翻譯
8.5CASE語句的翻譯
8.6回填技術
8.6.1使用回填技術翻譯布爾表達式
8.6.2使用回填技術翻譯控制流語句
8.6.3標號和轉移語句的翻譯
8.7過程調用語句的翻譯
習題
第9章目標代碼生成
9.1代碼生成器設計時要考慮的問題
9.1.1代碼生成器的輸入
9.1.2代碼生成器的輸出
9.1.3存儲管理
9.1.4指令選擇
9.1.5寄存器分配
9.1.6計算次序的選擇
9.1.7代碼生成器的設計
9.2目標機器
9.2.1目標機器
9.2.2指令代價
9.3運行時的存儲管理
9.3.1靜態(tài)存儲分配
9.3.2棧式存儲分配
9.3.3運行時名字的地址
9.4基本塊與控制流圖
9.4.1基本塊
9.4.2控制流圖
9.5下次引用信息
9.6一個簡單的代碼生成器
9.6.1寄存器描述器和地址描述器
9.6.2函數(shù)getreg
9.6.3代碼生成算法
9.6.4為其他類型的語句生成目標代碼
習題
第10章代碼優(yōu)化
10.1優(yōu)化概述
10.1.1程序優(yōu)化
10.1.2優(yōu)化器的組織
10.1.3優(yōu)化的主要種類
10.2基本塊的優(yōu)化
10.2.1常數(shù)合并及常數(shù)傳播
10.2.2刪除冗余的公共表達式
10.2.3復寫傳播
10.2.4刪除死代碼
10.2.5削弱計算強度
10.2.6臨時變量改名
10.2.7交換語句的位置
10.3循環(huán)優(yōu)化
10.3.1循環(huán)展開
10.3.2頻度削弱／代碼外提
10.3.3歸納變量的刪除
10.3.4削弱計算強度
10.4窺孔優(yōu)化
10.4.1冗余傳送
10.4.2死代碼
10.4.3控制流優(yōu)化
10.4.4代數(shù)化簡
10.4.5強度削弱
10.4.6利用機器的特點
10.5dag在代碼優(yōu)化中的應用
10.5.1基本塊的dag的構造
10.5.2dag的應用
習題
第11章編譯程序的設計與實現(xiàn)
11.1設計與實現(xiàn)方法
11.1.1編譯程序的實現(xiàn)語言
11.1.2構造編譯程序的自展方法
11.1.3構造編譯程序的移植方法
11.1.4編譯程序構造舉例
11.2編譯實踐
11.2.1Sub_P語言說明
11.2.2Sub_P編譯程序的設計說明
11.2.3Sub_P編譯程序的測試
11.2.4設計報告要求
參考文獻