編譯原理（第四版）

第1章引論(1)

1.1程序設(shè)計(jì)語(yǔ)言與翻譯程序(1)
1.1.1程序設(shè)計(jì)語(yǔ)言(1)
1.1.2翻譯程序(1)
1.2編譯程序的工作過(guò)程(2)
1.3編譯程序的結(jié)構(gòu)(4)
1.4編譯程序的組織方式(5)
1.5編譯程序的自展、移植與自動(dòng)化(6)
1.5.1 語(yǔ)言的自編譯性(6)
1.5.2編譯程序的自展技術(shù)(6)
1.5.3編譯程序的移植(7)
1.5.4編譯程序的自動(dòng)化(7)
1.6翻譯程序編寫(xiě)系統(tǒng)(8)
1.7并行編譯程序(9)
1.8小結(jié)(10)
習(xí)題一(10)
第2章形式語(yǔ)言理論(12)
2.1字母表和符號(hào)串(12)
2.2文法及其分類(lèi)(13)
2.2.1文法(13)
2.2.2文法分類(lèi)(14)
2.2.3文法舉例(15)
2.3語(yǔ)言和語(yǔ)法樹(shù)(16)
2.3.1推導(dǎo)和規(guī)范推導(dǎo)(16)
2.3.2句型、句子和語(yǔ)言(17)
2.3.3語(yǔ)法樹(shù)(18)
2.3.4產(chǎn)生式樹(shù)(19)
2.4關(guān)于文法和語(yǔ)言的幾點(diǎn)說(shuō)明(20)
2.5分析方法簡(jiǎn)介(21)
2.5.1自上而下分析方法(22)
2.5.2確定的自上而下分析方法(23)
2.5.3自下而上分析方法(24)
2.6小結(jié)(25)
習(xí)題二(26)

第3章有窮自動(dòng)機(jī)(28)
3.1有窮自動(dòng)機(jī)的形式定義(28)
3.1.1狀態(tài)轉(zhuǎn)換表(28)
3.1.2狀態(tài)轉(zhuǎn)換圖(29)
3.1.3自動(dòng)機(jī)的等價(jià)性(29)
3.1.4非確定有窮自動(dòng)機(jī)(30)
3.2NFA到DFA的轉(zhuǎn)換(31)
3.2.1空移環(huán)路的尋找和消除(31)
3.2.2消除空移(32)
3.2.3確定化——子集法(32)
3.2.4確定化——造表法(33)
3.2.5εNFA的確定化(35)
3.2.6消除不可達(dá)狀態(tài)(36)
3.2.7DFA的化簡(jiǎn)(37)
3.2.8從化簡(jiǎn)后的DFA到程序表示(37)
3.3正規(guī)表達(dá)式與FA(38)
3.3.1正規(guī)表達(dá)式的定義(38)
3.3.2正規(guī)表達(dá)式與FA的對(duì)應(yīng)性(40)
3.3.3正規(guī)表達(dá)式到NFA的轉(zhuǎn)換(40)
3.3.4NFA到正規(guī)表達(dá)式的轉(zhuǎn)換(41)
3.4DFA在計(jì)算機(jī)中的表示(42)
3.4.1矩陣表示法(42)
3.4.2表結(jié)構(gòu)(43)
3.5小結(jié)(43)
習(xí)題三(44)
第4章詞法分析(46)
4.1詞法分析程序與單詞符號(hào)(46)
4.1.1詞法分析程序(46)
4.1.2單詞符號(hào)(46)
4.2掃描程序的設(shè)計(jì)(47)
4.2.1預(yù)處理(47)
4.2.2狀態(tài)轉(zhuǎn)換圖(48)
4.2.3根據(jù)狀態(tài)圖設(shè)計(jì)詞法分析程序(49)
4.3標(biāo)識(shí)符的處理(50)
4.3.1類(lèi)型的機(jī)內(nèi)表示(50)
4.3.2標(biāo)識(shí)符的語(yǔ)義表示(51)
4.3.3符號(hào)表（標(biāo)識(shí)符表）(51)
4.3.4標(biāo)識(shí)符處理的基本思想(51)
4.4設(shè)計(jì)詞法分析程序的直接方法(52)
4.4.1由正規(guī)文法設(shè)計(jì)詞法分析程序(52)
4.4.2由正規(guī)表達(dá)式設(shè)計(jì)詞法分析程序(53)
4.4.3由狀態(tài)圖到詞法分析程序的流程圖(54)
4.4.4詞法分析程序的自動(dòng)構(gòu)造(54)
4.5小結(jié)(54)
習(xí)題四(55)
第5章自上而下語(yǔ)法分析(56)
5.1消除左遞歸方法(56)
5.1.1文法的左遞歸性(56)
5.1.2用擴(kuò)展的BNF表示法消除左遞歸(56)
5.1.3直接改寫(xiě)法(57)
5.1.4消除左遞歸算法(58)
5.2LL(k)文法(59)
5.2.1LL(1)文法的判斷條件(59)
5.2.2集合FIRST、FOLLOW與SELECT的構(gòu)造(59)
5.3確定的LL(1)分析程序的構(gòu)造(61)
5.3.1構(gòu)造分析表M的算法(61)
5.3.2LL(1)分析程序的總控算法(62)
5.4遞歸下降分析程序及其設(shè)計(jì)(64)
5.4.1框圖設(shè)計(jì)(64)
5.4.2程序設(shè)計(jì)(65)
5.5帶回溯的自上而下分析法(66)
5.5.1文法在內(nèi)存中的存放形式(66)
5.5.2其他信息的存放(67)
5.5.3帶回溯的自上而下分析算法(67)
5.6小結(jié)(71)
習(xí)題五(71)
第6章自下而上分析和優(yōu)先分析方法(74)
6.1自下而上分析(74)
6.2短語(yǔ)和句柄(74)
6.3移進(jìn)歸約方法(76)
6.4有關(guān)文法的一些關(guān)系(77)
6.4.1關(guān)系(77)
6.4.2布爾矩陣和關(guān)系(78)
6.4.3Warshall算法(79)
6.4.4關(guān)系FIRST與LAST(80)
6.5簡(jiǎn)單優(yōu)先分析方法(82)
6.5.1優(yōu)先關(guān)系(82)
6.5.2簡(jiǎn)單優(yōu)先關(guān)系的形式化構(gòu)造方法(83)
6.5.3簡(jiǎn)單優(yōu)先文法及其分析算法(87)
6.5.4簡(jiǎn)單優(yōu)先分析方法的局限性(89)
6.6算符優(yōu)先分析方法(90)
6.6.1算符優(yōu)先文法(90)
6.6.2OPG優(yōu)先關(guān)系的構(gòu)造(90)
6.6.3素短語(yǔ)及句型的分析(92)
6.6.4算符優(yōu)先分析算法(92)
6.7優(yōu)先函數(shù)及其構(gòu)造(94)
6.7.1優(yōu)先函數(shù)(94)
6.7.2Bell方法(95)
6.7.3Floyd方法(96)
6.7.4Bell和Floyd兩種方法的比較(97)
6.7.5運(yùn)用優(yōu)先函數(shù)進(jìn)行分析(97)
6.8兩種優(yōu)先分析方法的比較(98)
6.9小結(jié)(98)
習(xí)題六(99)
第7章自下而上的LR(k)分析方法
(101)
7.1LR(k)文法和LR(k)分析程序(101)
7.2LR(0)分析表的構(gòu)造(104)
7.2.1規(guī)范句型的活前綴(105)
7.2.2LR(0)項(xiàng)目(105)
7.2.3文法G的拓廣文法(105)
7.2.4CLOSURE(I)函數(shù)(105)
7.2.5goto(I,X)函數(shù)(106)
7.2.6LR(0)項(xiàng)目集規(guī)范族(107)
7.2.7有效項(xiàng)目(108)
7.2.8舉例(110)
7.2.9LR(0)文法(112)
7.2.10構(gòu)造LR(0)分析表的算法(112)
7.3SLR分析表的構(gòu)造(113)
7.4規(guī)范LR(1)分析表的構(gòu)造(116)
7.5LALR分析表的構(gòu)造(121)
7.6無(wú)二義性規(guī)則的使用(124)
7.7小結(jié)(126)
習(xí)題七(130)
第8章語(yǔ)法制導(dǎo)翻譯法(131)
8.1一般原理和樹(shù)變換(131)
8.1.1一般原理(131)
8.1.2樹(shù)變換(133)
8.2簡(jiǎn)單SDTS和自上而下翻譯器(135)
8.3簡(jiǎn)單后綴SDTS和自下而上翻譯器(137)
8.3.1后綴翻譯(138)
8.3.2IFTHENELSE控制語(yǔ)句(138)
8.3.3函數(shù)調(diào)用(139)
8.4抽象語(yǔ)法樹(shù)的構(gòu)造(140)
8.4.1自下而上構(gòu)造AST(141)
8.4.2AST的拓廣(142)
8.5屬性文法(143)
8.5.1L屬性文法(143)
8.5.2S屬性文法(143)
8.6中間代碼形式(144)
8.6.1逆波蘭表示法(144)
8.6.2逆波蘭表示法的推廣(144)
8.6.3四元式(146)
8.6.4三元式(147)
8.7屬性翻譯文法的應(yīng)用(147)
8.7.1綜合屬性與自下而上定值(147)
8.7.2繼承屬性和自上而下定值(148)
8.7.3布爾表達(dá)式到四元式的翻譯(149)
8.7.4條件語(yǔ)句的翻譯(150)
8.7.5迭代語(yǔ)句的翻譯(151)
8.8小結(jié)(153)
習(xí)題八(154)
第9章運(yùn)行時(shí)的存儲(chǔ)組織與管理(156)
9.1存儲(chǔ)分配基礎(chǔ)知識(shí)(156)
9.1.1運(yùn)行時(shí)刻的存儲(chǔ)區(qū)域(156)
9.1.2過(guò)程活動(dòng)與過(guò)程的活動(dòng)記錄(156)
9.1.3靜態(tài)層次、靜態(tài)外層和動(dòng)態(tài)外層(157)
9.1.4名字的作用域和生存期(158)
9.1.5名字的靜態(tài)屬性和動(dòng)態(tài)屬性(159)
9.1.6常見(jiàn)數(shù)據(jù)類(lèi)型的存儲(chǔ)分配(159)
9.2典型的存儲(chǔ)分配方案(160)
9.2.1靜態(tài)存儲(chǔ)分配方案(160)
9.2.2動(dòng)態(tài)存儲(chǔ)分配方案(161)
9.2.3存儲(chǔ)分配時(shí)需考慮的問(wèn)題(161)
9.3參數(shù)傳遞方式及其實(shí)現(xiàn)(162)
9.3.1傳地址(162)
9.3.2傳值(163)
9.3.3傳結(jié)果(163)
9.3.4傳名(163)
9.4棧式存儲(chǔ)分配(164)
9.4.1概述(164)
9.4.2簡(jiǎn)單棧式存儲(chǔ)分配(166)
9.4.3嵌套結(jié)構(gòu)語(yǔ)言的棧式存儲(chǔ)分配(167)
9.4.4過(guò)程調(diào)用時(shí)的存儲(chǔ)管理(171)
9.4.5PL/0棧式存儲(chǔ)分配(171)
9.5堆式存儲(chǔ)分配方法(177)
9.6小結(jié)(177)
習(xí)題九(178)
0章符號(hào)表的組織和查找(180)
10.1符號(hào)表的一般組織形式(180)
10.2符號(hào)表中的數(shù)據(jù)(181)
10.3符號(hào)表的構(gòu)造與查找(181)
10.3.1線性查找(182)
10.3. 半法(182)
10.3.3雜湊技術(shù)(183)
10.4分程序結(jié)構(gòu)的符號(hào)表(185)
10.5小結(jié)(187)
習(xí)題十(188)
1章優(yōu)化(189)
11.1控制流圖(190)
11.2常見(jiàn)的冗余(193)
11.2.1公共子表達(dá)式(194)
11.2.2復(fù)制傳播(195)
11.2.3活躍變量分析及死代碼刪除(196)
11.3循環(huán)優(yōu)化(197)
11.3.1代碼外提(197)
11.3.2歸納變量與強(qiáng)度削弱(200)
11.3.3循環(huán)展開(kāi)(202)
11.3.4指令調(diào)度(204)
習(xí)題十一(205)
2章代碼生成(208)
12.1假想的計(jì)算機(jī)模型(208)
12.2從四元式生成代碼(209)
12.3從三元式生成代碼(210)
12.4從樹(shù)形表示生成代碼(213)
12.5從逆波蘭表示生成代碼(215)
12.6寄存器的分配(215)
12.7小結(jié)(216)
習(xí)題十二(216)
3章詞法分析程序生成工具LEX(217)
13.1LEX簡(jiǎn)介(217)
13.2LEX源文件的格式(219)
13.2.1模式(219)
13.2.2定義部分(221)
13.2.3規(guī)則部分(222)
13.2.4用戶代碼部分(223)
13.3LEX的工作原理(223)
13.4yylex()函數(shù)的匹配原則(224)
13.5識(shí)別模式后處理(224)
13.6條件模式(227)
13.7FLEX的命令選項(xiàng)(228)
13.8舉例(228)
習(xí)題十三(229)
4章語(yǔ)法分析程序生成工具YACC(231)
14.1YACC簡(jiǎn)介(231)
14.2YACC源文件的格式(234)
14.2.1單詞和非終結(jié)符(234)
14.2.2定義部分(235)
14.2.3語(yǔ)法規(guī)則部分(241)
14.3語(yǔ)義定義(241)
14.3.1單詞語(yǔ)義值的計(jì)算(242)
14.3.2非終結(jié)符語(yǔ)義值的計(jì)算(243)
14.3.3在規(guī)則中部的語(yǔ)義動(dòng)作(244)
14.4歸約歸約沖突和上下文相關(guān)性的處理(246)
14.5出錯(cuò)處理和恢復(fù)(248)
14.6輸出分析程序的調(diào)試(250)
14.7YACC和LEX的接口(250)
14.8BYACC的命令選項(xiàng)(251)
14.9舉例(252)
習(xí)題十四(257)
參考文獻(xiàn)(259)