編譯原理（第二版）

第1章引論
1.1翻譯程序
1.1.1程序設(shè)計(jì)語(yǔ)言
1.1.2翻譯程序
1.2編譯程序的工作過程
1.3編譯程序的結(jié)構(gòu)
1.4編譯程序的組織方式
1.5編譯程序的自展.移植與自動(dòng)化
1.5.1高級(jí)語(yǔ)言的自編譯性
1.5.2編譯程序的自展技術(shù)
1.5.3編譯程序的移植
1.5.4編譯程序的自動(dòng)化
1.6翻譯程序編寫系統(tǒng)
1.7并行編譯程序
1.8小結(jié)
習(xí)題一
第2章形式語(yǔ)言概論
2.1字母表和符號(hào)串
2.2文法及其分類
2.2.1文法
2.2.2文法分類
2.2.3文法舉例
2.3語(yǔ)言和語(yǔ)法樹
2.3.1推導(dǎo)和規(guī)范推導(dǎo)
2.3.2句型.句子和語(yǔ)言
2.3.3語(yǔ)法樹
2.3.4產(chǎn)生式樹
2.4關(guān)于文法和語(yǔ)言的幾點(diǎn)說明
2.5分析方法簡(jiǎn)介
2.5.1自上而下分析方法
2.5.2確定的自上而下分析方法
2.5.3自下而上分析方法
2.6小結(jié)
習(xí)題二
第3章有窮自動(dòng)機(jī)
3.1有窮自動(dòng)機(jī)的形式定義
3.1.1狀態(tài)轉(zhuǎn)換表
3.1.2狀態(tài)轉(zhuǎn)換圖
3.1.3自動(dòng)機(jī)的等價(jià)性
3.1.4非確定有窮自動(dòng)機(jī)
3.2NDFA到DFA的轉(zhuǎn)換
3.2.1空移環(huán)路的尋找和消除
3.2.2消除空移
3.2.3確定化--子集法
3.2.4確定化--造表法
3.2.5NDFA的確定化
3.2.6消除不可達(dá)狀態(tài)
3.2.7DFA的化簡(jiǎn)
3.2.8從化簡(jiǎn)后的DFA到程序表示
3.3正規(guī)文法與有窮自動(dòng)機(jī)
3.3.1從正規(guī)文法到FA
3.3.2從FA到正規(guī)文法
3.4正規(guī)表達(dá)式與FA
3.4.1正規(guī)表達(dá)式的定義
3.4.2正規(guī)表達(dá)式與FA的對(duì)應(yīng)性
3.4.3正規(guī)表達(dá)式到NDFA的轉(zhuǎn)換
3.4.4NDFA到正規(guī)表達(dá)式的轉(zhuǎn)換
3.4.5從正規(guī)文法到正規(guī)表達(dá)式
3.5DFA在計(jì)算機(jī)中的表示
3.5.1矩陣表示法
3.5.2表結(jié)構(gòu)
3.6小結(jié)
習(xí)題三
第4章詞法分析
4.1詞法分析器與單詞符號(hào)
4.1.1詞法分析器
4.1.2單詞符號(hào)
4.2掃描程序的設(shè)計(jì)
4.2.1預(yù)處理
4.2.2狀態(tài)轉(zhuǎn)換圖
4.2.3根據(jù)狀態(tài)圖設(shè)計(jì)詞法分析程序
4.3標(biāo)識(shí)符的處理
4.3.1類型的機(jī)內(nèi)表示
4.3.2標(biāo)識(shí)符的語(yǔ)義表示
4.3.3符號(hào)表(標(biāo)識(shí)符表)
4.3.4標(biāo)識(shí)符處理的基本思想
4.4設(shè)計(jì)詞法分析程序的直接方法
4.4.1由正規(guī)文法設(shè)計(jì)詞法分析程序
4.4.2由正規(guī)表達(dá)式設(shè)計(jì)詞法分析程序
4.5小結(jié)
習(xí)題四
第5章自上而下語(yǔ)法分析
5.1消除左遞歸方法
5.1.1文法的左遞歸性
5.1.2用擴(kuò)展的BNF表示法消除左遞歸
5.1.3直接改寫法
5.1.4消除左遞歸算法
5.2LL(k)文法
5.2.1LL(1)文法的判斷條件
5.2.2集合F)RST.FOLLOW與SELECT的構(gòu)造
5.3確定的LL(1)分析器的構(gòu)造
5.3.1構(gòu)造分析表M的算法
5.3.2LL(1)分析器的總控算法
5.4遞歸下降分析程序及其設(shè)計(jì)
5.4.1框圖設(shè)計(jì)
5.4.2程序設(shè)計(jì)
5.5帶回溯的自上而下分析法
5.5.l文法在內(nèi)存中的存放形式
5.5.2其它信息的存放
5.5.3帶回溯的自上而下分析算法
5.6小結(jié)
習(xí)題五
第6章自下而上分析和優(yōu)先分析方法
6.1自下而上分析
6.2短語(yǔ)和句柄
6.3移進(jìn)·歸約方法
6.4有關(guān)文法的一些關(guān)系
6.4.1關(guān)系
6.4.2布爾矩陣和關(guān)系
6.4.3Warshall算法
6.4.4關(guān)系F1RST與LAST
6.5簡(jiǎn)單優(yōu)先分析方法
6.5.1優(yōu)先關(guān)系
6.5.2簡(jiǎn)單優(yōu)先關(guān)系的形式化構(gòu)造方法
6.5.3簡(jiǎn)單優(yōu)先文法及其分析算法
6.5.4簡(jiǎn)單優(yōu)先分析方法的局限性
6.6算符優(yōu)先分析方法
6.6.1算符優(yōu)先文法
6.6.2OPG優(yōu)先關(guān)系的構(gòu)造
6.6.3素短語(yǔ)及句型的分析
6.6.4算符優(yōu)先分析算法
6.7優(yōu)先函數(shù)及其構(gòu)造
6.7.1優(yōu)先函數(shù)
6.7.2Bell方法
6.7.3Floyd方法
6.7.4兩種方法的比較
6.7.5運(yùn)用優(yōu)先函數(shù)進(jìn)行分析
6.8兩種優(yōu)先分析方法的比較
6.9小結(jié)
習(xí)題六
第7章自-F而上的LR(k)分析方法
7.1LR(k)文法和LR(k)分析器
7.2LR(0)分析表的構(gòu)造
7.2.1規(guī)范句型的活前綴
7.2.2LR(p)項(xiàng)目
7.2.3文法G的拓廣文法
7.2.4CL()SURE(1)函數(shù)
7.2.5goto(I.X)函數(shù)
7.2.6LR(0)項(xiàng)目集規(guī)范族
7.2.7有效項(xiàng)目
7.2.8舉例
7.2.9LR(0)文法
7.2.10構(gòu)造LR(0)分析表的算法
7.2.11構(gòu)造LR(0)分析表的步驟小結(jié)
7.3SLR分析表的構(gòu)造
7.4規(guī)范LR(1)分析表的構(gòu)造
7.5LALR分析表的構(gòu)造
7.6無(wú)二義性規(guī)則的使用
7.7小結(jié)
7.7.1LR分析程序
7.7.2LR分析表的自動(dòng)構(gòu)造
7.7.3文法間的關(guān)系
7.7.4LR文法舉例
7.7.5有關(guān)LR文法的幾個(gè)結(jié)論
習(xí)題七
第8章語(yǔ)法制導(dǎo)翻譯法
8.1一般原理和樹變換
8.1.1一般原理
8.1.2樹變換
8.2簡(jiǎn)單SDTS和自上而下翻譯器
8.3簡(jiǎn)單后綴SDTS和自下而上翻譯器
8.3.1后綴翻譯
8.3.2IF-THEN-ELSE控制語(yǔ)句
8.3.3函數(shù)調(diào)用
8.4抽象語(yǔ)法樹的構(gòu)造
8.4.1自下而上構(gòu)造AST
8.4.2AST的拓廣
8.5屬性文法
8.5.1L屬性文法
8.5.2S屬性文法
8.6中間代碼形式
8.6.1逆波蘭表示法
8.6.2逆波蘭表示法的推廣
8.6.3四元式
8.6.4三元式
8.7屬性翻譯文法的應(yīng)用
8.7.1綜合屬性與自下而上定值
8.7.2繼承屬性和自上而下定值
8.7.3布爾表達(dá)式到四元式的翻譯
8.7.4條件語(yǔ)句的翻譯
8.7.5迭代語(yǔ)句的翻譯
8.8小結(jié)
習(xí)題八
第9章運(yùn)行時(shí)的存儲(chǔ)組織與管理
9.1數(shù)據(jù)區(qū)和屬性字
9.2基本數(shù)據(jù)類型的存儲(chǔ)分配
9.3數(shù)組的存儲(chǔ)分配
9.3.1單塊存儲(chǔ)方式
9.3.2信息向量與數(shù)組分配程序
9.3.3多塊存儲(chǔ)方式
9.4記錄結(jié)構(gòu)的存儲(chǔ)分配
9.5參數(shù)傳遞方式及其實(shí)現(xiàn)
9.5.1換名
9.5.2傳值
9.5.3傳地址
9.5.4傳結(jié)果
9.5.5數(shù)組名用做實(shí)參
9.5.6過程名用做實(shí)參
9.6棧式存儲(chǔ)分配方法
9.6.1概述
9.6.2現(xiàn)行DISPLAY和現(xiàn)行數(shù)據(jù)區(qū)
9.6.3標(biāo)識(shí)符的作用域
9.6.4分程序的人口和出口工作
9.6.5過程調(diào)用時(shí)的存儲(chǔ)管理
9.7堆式存儲(chǔ)分配方法
9.8臨時(shí)工作單元的存儲(chǔ)分配
9.9小結(jié)
習(xí)題九
第10章符號(hào)表的組織和查找
10.1符號(hào)表的一般組織形式
10.2符號(hào)表中的數(shù)據(jù)
10.3符號(hào)表的構(gòu)造與查找
10.2.1線性查找
10.3.2折半法
10.3.3雜湊技術(shù)
10.4分程序結(jié)構(gòu)的符號(hào)表
10.5小結(jié)
習(xí)題十
第11章優(yōu)化
11.1基本塊及其求法
11.2優(yōu)化舉例
11.3利用變量的定義點(diǎn)進(jìn)行優(yōu)化
11.3.1變量的定義點(diǎn)
11.3.2循環(huán)中不變式的外提
11.3.3運(yùn)算強(qiáng)度削弱
11.3.4公共表達(dá)式的消除
11.3.5常量合并
11.4循環(huán)優(yōu)化
11.5借助DAG進(jìn)行優(yōu)化
11.6并行分支的優(yōu)化
11.7窺孔優(yōu)化
11.8小結(jié)
習(xí)題十一
第12章代碼生成
12.1假想的計(jì)算機(jī)模型
12.2從四元式生成代碼
12.3從三元式生成代碼
12.4從樹型表示生成代碼
12.5從逆波蘭表示生成代碼
12.6寄存器的分配
12.7小結(jié)
習(xí)題十二
第13章詞法分析器生成工具LEX
13.1LEX簡(jiǎn)介
13.2LEX源文件的格式
13.2.1模式
13.2.2定義部分
13.2.3規(guī)則部分
13.2.4用戶代碼部分
13.3LEX的工作原理
13.4yylex()函數(shù)的匹配原則
13.5識(shí)別模式后處理
13.6條件模式
13.7FLEX的命令選項(xiàng)
13.8舉例
習(xí)題十三
第14章語(yǔ)法分析器生成工具YACC
14.1YACC簡(jiǎn)介
14.2YACC源文件的格式
14.2.1單詞和非終結(jié)符
14.2.2定義部分
14.2.3語(yǔ)法規(guī)則部分
14.3語(yǔ)義定義
14.3.1單詞語(yǔ)義值的汁算
14.3.2非終結(jié)符語(yǔ)義值的計(jì)算
14.3.3在規(guī)則中部的語(yǔ)義動(dòng)作
14.4歸約-歸約沖突和上下文相關(guān)性的處理
14.5出錯(cuò)處理和恢復(fù)
14.6輸出分析器的調(diào)試
14.7YACC和LEX的接口
14.8BYACC的命令選項(xiàng)
14.9舉例
習(xí)題十四
參考文獻(xiàn)