編譯原理

第1章  引論1
1.1  編譯程序是一種特定的翻譯程序1
1.2  編譯程序的結(jié)構(gòu)2
1.2.1  詞法分析階段2
1.2.2  語法分析階段2
1.2.3  語義分析、中間代碼生成階段3
1.2.4  優(yōu)化階段3
1.2.5  目標代碼生成階段3
1.2.6  符號表管理3
1.2.7  出錯管理程序3
1.2.8  編譯階段的前端和后端4
1.2.9  遍4
1.3  編譯程序的生成5
1.3.1  自展5
1.3.2  移植6
1.3.3  對編譯程序的評價7
1.4  編譯程序的學(xué)習(xí)7
第2章  文法和語言8
2.1  基本概念8
2.1.1  語言8
2.1.2  文法10
2.1.3  歸約與句柄12
2.2  分析樹與二義性14
2.2.1  分析樹14
2.2.2  子樹14
2.2.3  二義性15
2.3  形式語言分類15
習(xí)題217
第3章  詞法分析19
3.1  構(gòu)造一個簡單的詞法分析器19
3.1.1  詞法分析器的功能19
3.1.2  掃描緩沖區(qū)22
3.1.3  超前搜索23
3.1.4  狀態(tài)轉(zhuǎn)換圖23
3.1.5  狀態(tài)轉(zhuǎn)換圖的實現(xiàn)24
3.2  正規(guī)表達式與正規(guī)集27
3.2.1  正規(guī)式與正規(guī)集的定義27
3.2.2  正規(guī)式的性質(zhì)29
3.2.3  正規(guī)式與正規(guī)文法30
3.3  有限自動機30
3.3.1  有限自動機的定義30
3.3.2  FA的表示31
3.3.3  FA M識別的的語言32
3.3.4  NFA M的確定化32
3.3.5  DFA M的簡化34
3.4  正規(guī)式與有限自動機35
3.4.1  正規(guī)式與有限自動機的等價性35
3.4.2  由正規(guī)式構(gòu)造等價的NFA M37
3.5  詞法分析器的自動生成38
習(xí)題339
第4章  語法分析41
4.1  語法分析概述41
4.2  遞歸下降分析方法41
4.2.1  試探分析法41
4.2.2  提取左因子42
4.2.3  消除左遞歸43
4.2.4  預(yù)測分析器45
4.3  非遞歸的預(yù)測分析方法45
4.3.1  表驅(qū)動的預(yù)測分析器45
4.3.2  FIRST集和FOLLW集48
4.3.3  LL(1)文法50
4.3.4  預(yù)測分析表的構(gòu)造51
4.3.5  錯誤處理52
4.4  算符優(yōu)先分析法52
4.4.1  算符優(yōu)先關(guān)系表53
4.4.2  算符優(yōu)先分析方法54
4.4.3  優(yōu)先關(guān)系表的構(gòu)造56
4.4.4  優(yōu)先函數(shù)57
4.4.5  錯誤處理58
4.5  LR分析器59
4.5.1  LR分析法59
4.5.2  識別活前綴的DFA61
4.5.3  SLR分析表的構(gòu)造66
4.5.4  LR(1)分析表的構(gòu)造67
4.5.5  LALR分析表的構(gòu)造70
4.6  二義文法的應(yīng)用75
4.7  分析表的自動生成77
習(xí)題478第1章  引論
1.1  編譯程序是一種特定的翻譯程序
1.2  編譯程序的結(jié)構(gòu)
1.2.1  詞法分析階段
1.2.2  語法分析階段
1.2.3  語義分析、中間代碼生成階段
1.2.4  優(yōu)化階段
1.2.5  目標代碼生成階段
1.2.6  符號表管理
1.2.7  出錯管理程序
1.2.8  編譯階段的前端和后端
1.2.9  遍
1.3  編譯程序的生成
1.3.1  自展
1.3.2  移植
1.3.3  對編譯程序的評價
1.4  編譯程序的學(xué)習(xí)
第2章  文法和語言
2.1  基本概念
2.1.1  語言
2.1.2  文法
2.1.3  歸約與句柄
2.2  分析樹與二義性
2.2.1  分析樹
2.2.2  子樹
2.2.3  二義性
2.3  形式語言分類
習(xí)題2
第3章  詞法分析
3.1  構(gòu)造一個簡單的詞法分析器
3.1.1  詞法分析器的功能
3.1.2  掃描緩沖區(qū)
3.1.3  超前搜索
3.1.4  狀態(tài)轉(zhuǎn)換圖
3.1.5  狀態(tài)轉(zhuǎn)換圖的實現(xiàn)
3.2  正規(guī)表達式與正規(guī)集
3.2.1  正規(guī)式與正規(guī)集的定義
3.2.2  正規(guī)式的性質(zhì)
3.2.3  正規(guī)式與正規(guī)文法
3.3  有限自動機
3.3.1  有限自動機的定義
3.3.2  FA的表示
3.3.3  FA M識別的語言
3.3.4  NFA M的確定化
3.3.5  DFA M的簡化
3.4  正規(guī)式與有限自動機
3.4.1  正規(guī)式與有限自動機的等價性
3.4.2  由正規(guī)式構(gòu)造等價的NFA M
3.5  詞法分析器的自動生成
習(xí)題3
第4章  語法分析
4.1  語法分析概述
4.2  遞歸下降分析方法
4.2.1  試探分析法
4.2.2  提取左因子
4.2.3  消除左遞歸
4.2.4  預(yù)測分析器
4.3  非遞歸的預(yù)測分析方法
4.3.1  表驅(qū)動的預(yù)測分析器
4.3.2  FIRST集和FOLLW集
4.3.3  LL(1)文法
4.3.4  預(yù)測分析表的構(gòu)造
4.3.5  錯誤處理
4.4  算符優(yōu)先分析法
4.4.1  算符優(yōu)先關(guān)系表
4.4.2  算符優(yōu)先分析方法
4.4.3  優(yōu)先關(guān)系表的構(gòu)造
4.4.4  優(yōu)先函數(shù)
4.4.5  錯誤處理
4.5  LR分析器
4.5.1  LR分析法
4.5.2  識別活前綴的DFA
4.5.3  SLR分析表的構(gòu)造
4.5.4  LR(1)分析表的構(gòu)造
4.5.5  LALR分析表的構(gòu)造
4.6  二義文法的應(yīng)用
4.7  分析表的自動生成
習(xí)題4
第5章  語法制導(dǎo)翻譯和中間代碼生成
5.1  翻譯概述
5.1.1  靜態(tài)語義檢查
5.1.2  語義制導(dǎo)翻譯的例子
5.1.3  翻譯要解決的問題
5.2  中間語言
5.2.1  后綴式表示
5.2.2  圖表示
5.2.3  三地址代碼
5.2.4  三地址語句的種類
5.2.5  三地址代碼的具體實現(xiàn)
5.3  說明語句
5.3.1  一類說明語句的翻譯方案
5.3.2  嵌套過程中的說明語句
5.3.3  記錄中的域名
5.4  賦值語句
5.4.1  只含簡單變量的賦值語句的翻譯
5.4.2  類型轉(zhuǎn)換
5.4.3  含數(shù)組元素的賦值語句的翻譯
5.4.4  訪問記錄結(jié)構(gòu)中的域
5.5  控制流語句
5.5.1  布爾表達式的兩種基本作用
5.5.2  布爾表達式的兩種翻譯方法
5.5.3  數(shù)值表示法翻譯方案
5.5.4  控制流語句中布爾表達式的翻譯
5.5.5  控制流語句的翻譯
5.5.6  轉(zhuǎn)向語句和語句標號
5.6  循環(huán)語句、過程調(diào)用語句及CASE語句
5.6.1  循環(huán)語句的翻譯
5.6.2  過程調(diào)用、函數(shù)調(diào)用語句的翻譯
5.6.3  CASE語句或switch語句的翻譯
5.7  屬性文法
5.7.1  語法制導(dǎo)定義
5.7.2  屬性的分類
5.7.3  依賴圖
5.7.4  語義規(guī)則的計算次序
5.7.5  屬性文法的兩個子類
習(xí)題5
第6章  運行時存儲空間管理
6.1  變量及存儲分配
6.1.1  程序的存儲空間
6.1.2  活動記錄
6.1.3  變量的存儲分配
6.1.4  存儲分配模式
6.2  靜態(tài)分配
6.2.1  FORTRAN程序運行時的結(jié)構(gòu)
6.2.2  運行環(huán)境的轉(zhuǎn)換
6.3  棧式分配
6.3.1  只含半靜態(tài)變量的棧式分配
6.3.2  半動態(tài)變量的棧式分配
6.3.3  動態(tài)變量的存儲分配
6.3.4  非局部環(huán)境
6.3.5  對非局部環(huán)境的引用
6.4  堆分配
6.5  參數(shù)傳遞
6.5.1  數(shù)據(jù)參數(shù)傳遞
6.5.2  過程參數(shù)的傳遞
6.6  符號表
6.6.1  符號表的組織
6.6.2  常用的符號表結(jié)構(gòu)
習(xí)題6
第7章  代碼優(yōu)化
7.1  優(yōu)化概述
7.1.1  優(yōu)化定義
7.1.2  不同階段的優(yōu)化
7.1.3  程序流圖的構(gòu)造
7.2  局部優(yōu)化
7.2.1  基本塊內(nèi)的優(yōu)化
7.2.2  基本塊的dag表示
7.2.3  dag的構(gòu)造
7.2.4  dag實現(xiàn)的優(yōu)化
7.2.5  對dag構(gòu)造算法的修正
7.3  控制流分析及循環(huán)的查找
7.3.1  循環(huán)的定義
7.3.2  必經(jīng)結(jié)點集
7.3.3  自然循環(huán)
7.3.4  可歸約流圖
7.3.5  深度優(yōu)先搜索
7.4  數(shù)據(jù)流分析
7.4.1  到達一定值數(shù)據(jù)流方程和ud鏈
7.4.2  活躍變量數(shù)據(jù)流方程和du鏈
7.4.3  可用表達式數(shù)據(jù)流方程與復(fù)寫傳播
7.4.4  非常忙表達式與代碼提升
7.4.5  數(shù)據(jù)流方程的求解
7.5  循環(huán)優(yōu)化
7.5.1  循環(huán)優(yōu)化的例子
7.5.2  代碼外提
7.5.3  歸納變量
7.5.4  強度削弱
7.5.5  刪除歸納變量
習(xí)題7
第8章  代碼生成
8.1  目標代碼
8.1.1  代碼生成器的輸入與輸出
8.1.2  目標機
8.2  一個簡單代碼生成器
8.2.1  待用信息
8.2.2  寄存器描述和地址描述
8.2.3  如何生成目標代碼
8.2.4  函數(shù)getreg(P:x:=y op z)
8.2.5  代碼生成算法
8.2.6  其他語句的代碼生成
8.3  寄存器分配
8.3.1  執(zhí)行代價的節(jié)省
8.3.2  固定分配寄存器的代碼生成
8.3.3  多重循環(huán)的寄存器分配
8.3.4  用圖的點著色法做寄存器分配
8.4  窺孔優(yōu)化
8.5  由dag生成代碼
8.5.1  重新安排計算次序
8.5.2  dag為樹時最優(yōu)代碼生成
習(xí)題8
第9章  并行編譯概述
9.1  并行計算機及其編譯系統(tǒng)
9.1.1  向量計算機
9.1.2  共享存儲器多處理機
9.1.3  分布存儲器大規(guī)模并行計算機
9.1.4  并行編譯系統(tǒng)的結(jié)構(gòu)
9.2  并行編譯技術(shù)
9.2.1  依賴關(guān)系
9.2.2  依賴測試
9.2.3 循環(huán)向量化與并行化
參考文獻