第1章引論(1)





1.1程序設計語言與翻譯程序(1)



1.1.1程序設計語言(1)



1.1.2翻譯程序(1)



1.2編譯程序的工作過程(2)



1.3編譯程序的結構(4)



1.4編譯程序的組織方式(5)



1.5編譯程序的自展、移植與自動化(6)



1.5.1高級語言的自編譯性(6)



1.5.2編譯程序的自展技術(6)



1.5.3編譯程序的移植(7)



1.5.4編譯程序的自動化(7)



1.6翻譯程序編寫繫統(8)



1.7並行編譯程序(9)



1.8小結(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推導和規範推導(16)



2.3.2句型、句子和語言(17)



2.3.3語法樹(18)



2.3.4產生式樹(19)



2.4關於文法和語言的幾點說明(20)



2.5分析方法簡介(21)



2.5.1自上而下分析方法(22)



2.5.2確定的自上而下分析方法(23)



2.5.3自下而上分析方法(24)



2.6小結(25)



習題二(26)





第3章有窮自動機(28)



3.1有窮自動機的形式定義(28)



3.1.1狀態轉換表(28)



3.1.2狀態轉換圖(29)



3.1.3自動機的等價性(29)



3.1.4非確定有窮自動機(30)



3.2NFA到DFA的轉換(31)



3.2.1空移環路的尋找和消除(31)



3.2.2消除空移(32)



3.2.3確定化——子集法(32)



3.2.4確定化——造表法(33)



3.2.5εNFA的確定化(35)



3.2.6消除不可達狀態(36)



3.2.7DFA的化簡(37)



3.2.8從化簡後的DFA到程序表示(37)



3.3正規表達式與FA(38)



3.3.1正規表達式的定義(38)



3.3.2正規表達式與FA的對應性(40)



3.3.3正規表達式到NFA的轉換(40)



3.3.4NFA到正規表達式的轉換(41)



3.4DFA在計算機中的表示(42)



3.4.1矩陣表示法(42)



3.4.2表結構(43)



3.5小結(43)



習題三(44)



第4章詞法分析(46)



4.1詞法分析程序與單詞符號(46)



4.1.1詞法分析程序(46)



4.1.2單詞符號(46)



4.2掃描程序的設計(47)



4.2.1預處理(47)



4.2.2狀態轉換圖(48)



4.2.3根據狀態圖設計詞法分析程序(49)



4.3標識符的處理(50)



4.3.1類型的機內表示(50)



4.3.2標識符的語義表示(51)



4.3.3符號表（標識符表）(51)



4.3.4標識符處理的基本思想(51)



4.4設計詞法分析程序的直接方法(52)



4.4.1由正規文法設計詞法分析程序(52)



4.4.2由正規表達式設計詞法分析程序(53)



4.4.3由狀態圖到詞法分析程序的流程圖(54)



4.4.4詞法分析程序的自動構造(54)



4.5小結(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的構造(59)



5.3確定的LL(1)分析程序的構造(61)



5.3.1構造分析表M的算法(61)



5.3.2LL(1)分析程序的總控算法(62)



5.4遞歸下降分析程序及其設計(64)



5.4.1框圖設計(64)



5.4.2程序設計(65)



5.5帶回溯的自上而下分析法(66)



5.5.1文法在內存中的存放形式(66)



5.5.2其他信息的存放(67)



5.5.3帶回溯的自上而下分析算法(67)



5.6小結(71)



習題五(71)



第6章自下而上分析和優先分析方法(74)



6.1自下而上分析(74)



6.2短語和句柄(74)



6.3移進歸約方法(76)



6.4有關文法的一些關繫(77)



6.4.1關繫(77)



6.4.2布爾矩陣和關繫(78)



6.4.3Warshall算法(79)



6.4.4關繫FIRST與LAST(80)



6.5簡單優先分析方法(82)



6.5.1優先關繫(82)



6.5.2簡單優先關繫的形式化構造方法(83)



6.5.3簡單優先文法及其分析算法(87)



6.5.4簡單優先分析方法的局限性(89)



6.6算符優先分析方法(90)



6.6.1算符優先文法(90)



6.6.2OPG優先關繫的構造(90)



6.6.3素短語及句型的分析(92)



6.6.4算符優先分析算法(92)



6.7優先函數及其構造(94)



6.7.1優先函數(94)



6.7.2Bell方法(95)



6.7.3Floyd方法(96)



6.7.4Bell和Floyd兩種方法的比較(97)



6.7.5運用優先函數進行分析(97)



6.8兩種優先分析方法的比較(98)



6.9小結(98)



習題六(99)



第7章自下而上的LR(k)分析方法

(101)



7.1LR(k)文法和LR(k)分析程序(101)



7.2LR(0)分析表的構造(104)



7.2.1規範句型的活前綴(105)



7.2.2LR(0)項目(105)



7.2.3文法G的拓廣文法(105)



7.2.4CLOSURE(I)函數(105)



7.2.5goto(I,X)函數(106)



7.2.6LR(0)項目集規範族(107)



7.2.7有效項目(108)



7.2.8舉例(110)



7.2.9LR(0)文法(112)



7.2.10構造LR(0)分析表的算法(112)



7.3SLR分析表的構造(113)



7.4規範LR(1)分析表的構造(116)



7.5LALR分析表的構造(121)



7.6無二義性規則的使用(124)



7.7小結(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函數調用(139)



8.4抽像語法樹的構造(140)



8.4.1自下而上構造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式(146)



8.6式(147)



8.7屬性翻譯文法的應用(147)



8.7.1綜合屬性與自下而上定值(147)



8.7.2繼承屬性和自上而下定值(148)



8.7.3布爾表達式的翻譯(149)



8.7.4條件語句的翻譯(150)



8.7.5迭代語句的翻譯(151)



8.8小結(153)



習題八(154)



第9章運行時的存儲組織與管理(156)



9.1存儲分配基礎知識(156)



9.1.1運行時刻的存儲區域(156)



9.1.2過程活動與過程的活動記錄(156)



9.1.3靜態層次、靜態外層和動態外層(157)



9.1.4名字的作用域和生存期(158)



9.1.5名字的靜態屬性和動態屬性(159)



9.1.6常見數據類型的存儲分配(159)



9.2典型的存儲分配方案(160)



9.2.1靜態存儲分配方案(160)



9.2.2動態存儲分配方案(161)



9.2.3存儲分配時需考慮的問題(161)



9.3參數傳遞方式及其實現(162)



9.3.1傳地址(162)



9.3.2傳值(163)



9.3.3傳結果(163)



9.3.4傳名(163)



9.4棧式存儲分配(164)



9.4.1概述(164)



9.4.2簡單棧式存儲分配(166)



9.4.3嵌套結構語言的棧式存儲分配(167)



9.4.4過程調用時的存儲管理(171)



9.4.5PL/0棧式存儲分配(171)



9.5堆式存儲分配方法(177)



9.6小結(177)



習題九(178)



第10章符號表的組織和查找(180)



10.1符號表的一般組織形式(180)



10.2符號表中的數據(181)



10.3符號表的構造與查找(181)



10.3.1線性查找(182)



10.3.2折半法(182)



10.3.3雜湊技術(183)



10.4分程序結構的符號表(185)



10.5小結(187)



習題十(188)



第11章優化(189)



11.1控制流圖(190)



11.2常見的冗餘(193)



11.2.1公共子表達式(194)



11.2.2復制傳播(195)



11.2.3活躍變量分析及死代碼刪除(196)



11.3循環優化(197)



11.3.1代碼外提(197)



11.3.2歸納變量與強度削弱(200)



11.3.3循環展開(202)



11.3.4指令調度(204)



習題十一(205)



第12章代碼生成(208)



12.1假想的計算機模型(208)



12.式生成代碼(209)



12.式生成代碼(210)



12.4從樹形表示生成代碼(213)



12.5從逆波蘭表示生成代碼(215)



12.6寄存器的分配(215)



12.7小結(216)



習題十二(216)



第13章詞法分析程序生成工具LEX(217)



13.1LEX簡介(217)



13.2LEX源文件的格式(219)



13.2.1模式(219)



13.2.2定義部分(221)



13.2.3規則部分(222)



13.2.4用戶代碼部分(223)



13.3LEX的工作原理(223)



13.4yylex()函數的匹配原則(224)



13.5識別模式後處理(224)



13.6條件模式(227)



13.7FLEX的命令選項(228)



13.8舉例(228)



習題十三(229)



第14章語法分析程序生成工具YACC(231)



14.1YACC簡介(231)



14.2YACC源文件的格式(234)



14.2.1單詞和非終結符(234)



14.2.2定義部分(235)



14.2.3語法規則部分(241)



14.3語義定義(241)



14.3.1單詞語義值的計算(242)



14.3.2非終結符語義值的計算(243)



14.3.3在規則中部的語義動作(244)



14.4歸約歸約衝突和上下文相關性的處理(246)



14.5出錯處理和恢復(248)



14.6輸出分析程序的調試(250)



14.7YACC和LEX的接口(250)



14.8BYACC的命令選項(251)



14.9舉例(252)



習題十四(257)



參考文獻(259) 

編譯程序(compiler),又稱編譯器,是計算機的重要繫統軟件,是高級程序設計語言的支撐基礎。本書主要介紹設計和構造編譯程序的基本原理和方法。本書共分 14 章。第1章講述編譯程序的功能、結構、工作過程、組織方式、編譯程序與高級語言的關繫,以及編譯自動化方面的基本知識。第2章介紹形式語言理論,我們僅僅給出了便於理解、有助於研究各種分析方法和設計構造編譯程序的形式語言理論，並著重介紹了上下文無關文法。有窮自動機是描述詞法的有效工具,也是進行詞法分析的主要理論基礎。因此,第3章專門討論有窮自動機,它與正規文法、正規表達式之間的對應關繫,以及它的確定化和*小化方面的知識，略去了圖靈機及可計算性理論方面的內容。第4章討論詞法分析的功能和詞法分析程序的設計方法。上下文無關文法可用於描述現今大多數高級程序設計語言的語法，也是語法分析的主要理論支柱。為此,在接下來的幾章裡,主要討論了與上下文無關文法相關的各類語法分析方法。第5章介紹自上而下分析方法,句括 LL(k)文法、LL(1)分析方法和應用十分廣泛的遞歸下降分析方法。第6章討論自下而上分析方法的一般原理和優先分析方法,包括簡單優先分析方法和算符優先分析方法。第7章專門討論自下而上的LR(k)分析方法,包括 LR(O)、SLR(1)、規範 LR(1)及 LALR 分析表的構造算法第8章介紹語法制導翻譯方法,主要討論了 SDTS 的基本原理、屬性翻譯文法,以及它們在中間代碼生成中的應用。第9章討論運行時的存儲組織與管理,其中考慮了一些重要的語言特征,如過程調用、參數傳遞、數組和記錄的存取方式及多種存儲分配技術。第10章討論符號表的組織和存取符號表的各種方法。第11章介紹常用的優化方法。第12章簡單討論代碼生成的原理。第13章、第14章中花了較大篇幅分別介紹了詞法分析器生成工具 LEX 和語法分器生成工具 YACC,以便於本課程的教學實習和課程設計。我們認為某些形式語言理論和自動機理論對設計構造編譯程序是極其有用的,但現有的不少形式語言理論及自動機理論與設計和構造編譯程序的關繫不大。本書試圖在溝通設計和構造編譯程序的理論與實踐、原理與方法等方面做一點嘗試。編譯原理這門課程是計算機專業的主干課和必修課,也是計算機專業高年級課程中較難學習的一門課程,其先導課程是彙編語言程序設計、計算機組成原理、數據結構、高級語言程序設計和離散數學等。本課程的參考學時數為72,使用者可根據具體情況對教材內容進行取舍,例如,工科院校的學生可略過第7章、第8章並可精簡第2章的內容,從而使授課學時數減至54。本次再版工作主要是針對《編譯原理(第三版)》中的差錯進行修正,對過時的章節進行刪除,對必要的內容進行補充等。其中,第1~3章由袁夢霆負責修訂,第 4~6 章由杜卓敏負責修訂,第7~8章由何炎祥負責修訂,第9~10章由伍春香負責修訂,第11~14章基本沒動。*後由何炎祥對全書進行了審定。同時,適當配套一些電子資源,包括 PPT 課件、習題答案、部分章節的相關視頻。本書可作為高等院校計算機專業的教材，也可供教師、研究生及有關科技工作者學習和參本書成書過程中,得到了華中科技大學出版社的鼎力協助，此外,書中還引用了一些專家學者的研究成果,在此一並表示感謝。作 者2023 年5月於武昌珞珈山