編譯原理（第四版）

第1章引論(1)

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

第3章有窮自動機(28)
3.1有窮自動機的形式定義(28)
3.1.1狀態(tài)轉(zhuǎn)換表(28)
3.1.2狀態(tài)轉(zhuǎn)換圖(29)
3.1.3自動機的等價性(29)
3.1.4非確定有窮自動機(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消除不可達狀態(tài)(36)
3.2.7DFA的化簡(37)
3.2.8從化簡后的DFA到程序表示(37)
3.3正規(guī)表達式與FA(38)
3.3.1正規(guī)表達式的定義(38)
3.3.2正規(guī)表達式與FA的對應(yīng)性(40)
3.3.3正規(guī)表達式到NFA的轉(zhuǎn)換(40)
3.3.4NFA到正規(guī)表達式的轉(zhuǎn)換(41)
3.4DFA在計算機中的表示(42)
3.4.1矩陣表示法(42)
3.4.2表結(jié)構(gòu)(43)
3.5小結(jié)(43)
習題三(44)
第4章詞法分析(46)
4.1詞法分析程序與單詞符號(46)
4.1.1詞法分析程序(46)
4.1.2單詞符號(46)
4.2掃描程序的設(shè)計(47)
4.2.1預處理(47)
4.2.2狀態(tài)轉(zhuǎn)換圖(48)
4.2.3根據(jù)狀態(tài)圖設(shè)計詞法分析程序(49)
4.3標識符的處理(50)
4.3.1類型的機內(nèi)表示(50)
4.3.2標識符的語義表示(51)
4.3.3符號表（標識符表）(51)
4.3.4標識符處理的基本思想(51)
4.4設(shè)計詞法分析程序的直接方法(52)
4.4.1由正規(guī)文法設(shè)計詞法分析程序(52)
4.4.2由正規(guī)表達式設(shè)計詞法分析程序(53)
4.4.3由狀態(tài)圖到詞法分析程序的流程圖(54)
4.4.4詞法分析程序的自動構(gòu)造(54)
4.5小結(jié)(54)
習題四(55)
第5章自上而下語法分析(56)
5.1消除左遞歸方法(56)
5.1.1文法的左遞歸性(56)
5.1.2用擴展的BNF表示法消除左遞歸(56)
5.1.3直接改寫法(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è)計(64)
5.4.1框圖設(shè)計(64)
5.4.2程序設(shè)計(65)
5.5帶回溯的自上而下分析法(66)
5.5.1文法在內(nèi)存中的存放形式(66)
5.5.2其他信息的存放(67)
5.5.3帶回溯的自上而下分析算法(67)
5.6小結(jié)(71)
習題五(71)
第6章自下而上分析和優(yōu)先分析方法(74)
6.1自下而上分析(74)
6.2短語和句柄(74)
6.3移進歸約方法(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簡單優(yōu)先分析方法(82)
6.5.1優(yōu)先關(guān)系(82)
6.5.2簡單優(yōu)先關(guān)系的形式化構(gòu)造方法(83)
6.5.3簡單優(yōu)先文法及其分析算法(87)
6.5.4簡單優(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素短語及句型的分析(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ōu)先函數(shù)進行分析(97)
6.8兩種優(yōu)先分析方法的比較(98)
6.9小結(jié)(98)
習題六(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)項目(105)
7.2.3文法G的拓廣文法(105)
7.2.4CLOSURE(I)函數(shù)(105)
7.2.5goto(I,X)函數(shù)(106)
7.2.6LR(0)項目集規(guī)范族(107)
7.2.7有效項目(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無二義性規(guī)則的使用(124)
7.7小結(jié)(126)
習題七(130)
第8章語法制導翻譯法(131)
8.1一般原理和樹變換(131)
8.1.1一般原理(131)
8.1.2樹變換(133)
8.2簡單SDTS和自上而下翻譯器(135)
8.3簡單后綴SDTS和自下而上翻譯器(137)
8.3.1后綴翻譯(138)
8.3.2IFTHENELSE控制語句(138)
8.3.3函數(shù)調(diào)用(139)
8.4抽象語法樹的構(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布爾表達式到四元式的翻譯(149)
8.7.4條件語句的翻譯(150)
8.7.5迭代語句的翻譯(151)
8.8小結(jié)(153)
習題八(154)
第9章運行時的存儲組織與管理(156)
9.1存儲分配基礎(chǔ)知識(156)
9.1.1運行時刻的存儲區(qū)域(156)
9.1.2過程活動與過程的活動記錄(156)
9.1.3靜態(tài)層次、靜態(tài)外層和動態(tài)外層(157)
9.1.4名字的作用域和生存期(158)
9.1.5名字的靜態(tài)屬性和動態(tài)屬性(159)
9.1.6常見數(shù)據(jù)類型的存儲分配(159)
9.2典型的存儲分配方案(160)
9.2.1靜態(tài)存儲分配方案(160)
9.2.2動態(tài)存儲分配方案(161)
9.2.3存儲分配時需考慮的問題(161)
9.3參數(shù)傳遞方式及其實現(xiàn)(162)
9.3.1傳地址(162)
9.3.2傳值(163)
9.3.3傳結(jié)果(163)
9.3.4傳名(163)
9.4棧式存儲分配(164)
9.4.1概述(164)
9.4.2簡單棧式存儲分配(166)
9.4.3嵌套結(jié)構(gòu)語言的棧式存儲分配(167)
9.4.4過程調(diào)用時的存儲管理(171)
9.4.5PL/0棧式存儲分配(171)
9.5堆式存儲分配方法(177)
9.6小結(jié)(177)
習題九(178)
0章符號表的組織和查找(180)
10.1符號表的一般組織形式(180)
10.2符號表中的數(shù)據(jù)(181)
10.3符號表的構(gòu)造與查找(181)
10.3.1線性查找(182)
10.3. 半法(182)
10.3.3雜湊技術(shù)(183)
10.4分程序結(jié)構(gòu)的符號表(185)
10.5小結(jié)(187)
習題十(188)
1章優(yōu)化(189)
11.1控制流圖(190)
11.2常見的冗余(193)
11.2.1公共子表達式(194)
11.2.2復制傳播(195)
11.2.3活躍變量分析及死代碼刪除(196)
11.3循環(huán)優(yōu)化(197)
11.3.1代碼外提(197)
11.3.2歸納變量與強度削弱(200)
11.3.3循環(huán)展開(202)
11.3.4指令調(diào)度(204)
習題十一(205)
2章代碼生成(208)
12.1假想的計算機模型(208)
12.2從四元式生成代碼(209)
12.3從三元式生成代碼(210)
12.4從樹形表示生成代碼(213)
12.5從逆波蘭表示生成代碼(215)
12.6寄存器的分配(215)
12.7小結(jié)(216)
習題十二(216)
3章詞法分析程序生成工具LEX(217)
13.1LEX簡介(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識別模式后處理(224)
13.6條件模式(227)
13.7FLEX的命令選項(228)
13.8舉例(228)
習題十三(229)
4章語法分析程序生成工具YACC(231)
14.1YACC簡介(231)
14.2YACC源文件的格式(234)
14.2.1單詞和非終結(jié)符(234)
14.2.2定義部分(235)
14.2.3語法規(guī)則部分(241)
14.3語義定義(241)
14.3.1單詞語義值的計算(242)
14.3.2非終結(jié)符語義值的計算(243)
14.3.3在規(guī)則中部的語義動作(244)
14.4歸約歸約沖突和上下文相關(guān)性的處理(246)
14.5出錯處理和恢復(248)
14.6輸出分析程序的調(diào)試(250)
14.7YACC和LEX的接口(250)
14.8BYACC的命令選項(251)
14.9舉例(252)
習題十四(257)
參考文獻(259)