編譯原理

第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  目標(biāo)代碼生成階段3
1.2.6  符號(hào)表管理3
1.2.7  出錯(cuò)管理程序3
1.2.8  編譯階段的前端和后端4
1.2.9  遍4
1.3  編譯程序的生成5
1.3.1  自展5
1.3.2  移植6
1.3.3  對(duì)編譯程序的評(píng)價(jià)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)造一個(gè)簡單的詞法分析器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)換圖的實(shí)現(xiàn)24
3.2  正規(guī)表達(dá)式與正規(guī)集27
3.2.1  正規(guī)式與正規(guī)集的定義27
3.2.2  正規(guī)式的性質(zhì)29
3.2.3  正規(guī)式與正規(guī)文法30
3.3  有限自動(dòng)機(jī)30
3.3.1  有限自動(dòng)機(jī)的定義30
3.3.2  FA的表示31
3.3.3  FA M識(shí)別的的語言32
3.3.4  NFA M的確定化32
3.3.5  DFA M的簡化34
3.4  正規(guī)式與有限自動(dòng)機(jī)35
3.4.1  正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性35
3.4.2  由正規(guī)式構(gòu)造等價(jià)的NFA M37
3.5  詞法分析器的自動(dòng)生成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ū)動(dòng)的預(yù)測分析器45
4.3.2  FIRST集和FOLLW集48
4.3.3  LL(1)文法50
4.3.4  預(yù)測分析表的構(gòu)造51
4.3.5  錯(cuò)誤處理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  錯(cuò)誤處理58
4.5  LR分析器59
4.5.1  LR分析法59
4.5.2  識(shí)別活前綴的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  分析表的自動(dòng)生成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  目標(biāo)代碼生成階段
1.2.6  符號(hào)表管理
1.2.7  出錯(cuò)管理程序
1.2.8  編譯階段的前端和后端
1.2.9  遍
1.3  編譯程序的生成
1.3.1  自展
1.3.2  移植
1.3.3  對(duì)編譯程序的評(píng)價(jià)
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)造一個(gè)簡單的詞法分析器
3.1.1  詞法分析器的功能
3.1.2  掃描緩沖區(qū)
3.1.3  超前搜索
3.1.4  狀態(tài)轉(zhuǎn)換圖
3.1.5  狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn)
3.2  正規(guī)表達(dá)式與正規(guī)集
3.2.1  正規(guī)式與正規(guī)集的定義
3.2.2  正規(guī)式的性質(zhì)
3.2.3  正規(guī)式與正規(guī)文法
3.3  有限自動(dòng)機(jī)
3.3.1  有限自動(dòng)機(jī)的定義
3.3.2  FA的表示
3.3.3  FA M識(shí)別的語言
3.3.4  NFA M的確定化
3.3.5  DFA M的簡化
3.4  正規(guī)式與有限自動(dòng)機(jī)
3.4.1  正規(guī)式與有限自動(dòng)機(jī)的等價(jià)性
3.4.2  由正規(guī)式構(gòu)造等價(jià)的NFA M
3.5  詞法分析器的自動(dòng)生成
習(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ū)動(dòng)的預(yù)測分析器
4.3.2  FIRST集和FOLLW集
4.3.3  LL(1)文法
4.3.4  預(yù)測分析表的構(gòu)造
4.3.5  錯(cuò)誤處理
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  錯(cuò)誤處理
4.5  LR分析器
4.5.1  LR分析法
4.5.2  識(shí)別活前綴的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  分析表的自動(dòng)生成
習(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  三地址代碼的具體實(shí)現(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  布爾表達(dá)式的兩種基本作用
5.5.2  布爾表達(dá)式的兩種翻譯方法
5.5.3  數(shù)值表示法翻譯方案
5.5.4  控制流語句中布爾表達(dá)式的翻譯
5.5.5  控制流語句的翻譯
5.5.6  轉(zhuǎn)向語句和語句標(biāo)號(hào)
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ī)則的計(jì)算次序
5.7.5  屬性文法的兩個(gè)子類
習(xí)題5
第6章  運(yùn)行時(shí)存儲(chǔ)空間管理
6.1  變量及存儲(chǔ)分配
6.1.1  程序的存儲(chǔ)空間
6.1.2  活動(dòng)記錄
6.1.3  變量的存儲(chǔ)分配
6.1.4  存儲(chǔ)分配模式
6.2  靜態(tài)分配
6.2.1  FORTRAN程序運(yùn)行時(shí)的結(jié)構(gòu)
6.2.2  運(yùn)行環(huán)境的轉(zhuǎn)換
6.3  棧式分配
6.3.1  只含半靜態(tài)變量的棧式分配
6.3.2  半動(dòng)態(tài)變量的棧式分配
6.3.3  動(dòng)態(tài)變量的存儲(chǔ)分配
6.3.4  非局部環(huán)境
6.3.5  對(duì)非局部環(huán)境的引用
6.4  堆分配
6.5  參數(shù)傳遞
6.5.1  數(shù)據(jù)參數(shù)傳遞
6.5.2  過程參數(shù)的傳遞
6.6  符號(hào)表
6.6.1  符號(hào)表的組織
6.6.2  常用的符號(hào)表結(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實(shí)現(xiàn)的優(yōu)化
7.2.5  對(duì)dag構(gòu)造算法的修正
7.3  控制流分析及循環(huán)的查找
7.3.1  循環(huán)的定義
7.3.2  必經(jīng)結(jié)點(diǎn)集
7.3.3  自然循環(huán)
7.3.4  可歸約流圖
7.3.5  深度優(yōu)先搜索
7.4  數(shù)據(jù)流分析
7.4.1  到達(dá)一定值數(shù)據(jù)流方程和ud鏈
7.4.2  活躍變量數(shù)據(jù)流方程和du鏈
7.4.3  可用表達(dá)式數(shù)據(jù)流方程與復(fù)寫傳播
7.4.4  非常忙表達(dá)式與代碼提升
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  強(qiáng)度削弱
7.5.5  刪除歸納變量
習(xí)題7
第8章  代碼生成
8.1  目標(biāo)代碼
8.1.1  代碼生成器的輸入與輸出
8.1.2  目標(biāo)機(jī)
8.2  一個(gè)簡單代碼生成器
8.2.1  待用信息
8.2.2  寄存器描述和地址描述
8.2.3  如何生成目標(biāo)代碼
8.2.4  函數(shù)getreg(P:x:=y op z)
8.2.5  代碼生成算法
8.2.6  其他語句的代碼生成
8.3  寄存器分配
8.3.1  執(zhí)行代價(jià)的節(jié)省
8.3.2  固定分配寄存器的代碼生成
8.3.3  多重循環(huán)的寄存器分配
8.3.4  用圖的點(diǎn)著色法做寄存器分配
8.4  窺孔優(yōu)化
8.5  由dag生成代碼
8.5.1  重新安排計(jì)算次序
8.5.2  dag為樹時(shí)最優(yōu)代碼生成
習(xí)題8
第9章  并行編譯概述
9.1  并行計(jì)算機(jī)及其編譯系統(tǒng)
9.1.1  向量計(jì)算機(jī)
9.1.2  共享存儲(chǔ)器多處理機(jī)
9.1.3  分布存儲(chǔ)器大規(guī)模并行計(jì)算機(jī)
9.1.4  并行編譯系統(tǒng)的結(jié)構(gòu)
9.2  并行編譯技術(shù)
9.2.1  依賴關(guān)系
9.2.2  依賴測試
9.2.3 循環(huán)向量化與并行化
參考文獻(xiàn)