編譯原理

《編譯原理》主要介紹設計和構造編譯程序的基本原理和方法。內容包括形式語言理論和自動機理論、常用的詞法分析方法、各種經典的語法分析方法、語法制導翻譯方法、存儲器的組織與管理方法、符號表的組織與造查表方法、代碼優化和代碼生成方法、並行編譯程序及編譯自動化技術等。

《編譯原理》注重理論與實踐、原理與方法的互通，基本概念闡述清晰，講授深入淺出，循序漸進，系統性強。各章之後還附有難度不一的習題供複習、思考和探索之用。《編譯原理》既可作為高等院校計算機專業的教材，也可供相關專業師生和科技工作者及軟件研發人學習和參考。

何炎祥，男，1952年1月生，武漢大學計算機學院院長、教授、博士生導師。先後獲得寶鋼教育優秀教師獎、國務院政府特殊津貼、湖北省青少年科技教育工作先進個人和湖北省優秀研究生導師。國家自然科學基金委、國家科學技術獎和教育部科學技術獎評審專家，國家重點基礎研究發展規劃（973）項目“下一代互聯網信息存儲的組織模式與核心技術研究”項目專家組專家。現為國家教育部科技委信息學部委員，全國高校計算機教育研究會副理事長，中國計算機學會教育專委會副主任。一直堅持主講本科生《編譯原理》、《計算機導論》等課程。主講課程“編譯原理”2005年獲評國家精品課程。2006年評為“武漢大學教學名師”，2009年獲湖北省“湖北名師”稱號。獲省級教學成果二等獎、三等獎。《程序設計基礎》、《計算機操作系統》、《編譯原理》評為國家級“十一五”規劃教材。《編譯原理》、《編譯原理及其習題解答》和《分佈式操作系統》及《操作系統原理學習指導與題解》已被國內幾十所高校和科學院的計算機專業或相關專業用作教材或教學參考書。主要研究方向為分佈並行處理（含移動計算、網格計算與Web服務）、可信軟件、知識挖掘與數據開採、軟件工程等。 ^[2] 

第1章 引論

1.1 翻譯程序

1.1.1 程序設計語言

1.1.2 翻譯程序

1.2 為什麼需要編譯程序

1.3 編譯程序的工作過程

1.3.1 分析

1.3.2 綜合

1.4 編譯程序的結構

1.5 編譯程序的組織方式

1.6 編譯程序的其他有關技術

1.6.1 編譯程序的自展技術

1.6.2 編譯程序的移植技術

1.6.3 編譯程序自動化

1.6.4 程序的可再入性

1.7 翻譯程序編寫系統

1.8 並行編譯程序

1.9 小結

習題

第2章 形式語言概論

2.1 語言成分

2.2 產生式文法和語言

2.2.1 產生式文法

2.2.2 上下文無關文法

2.2.3 上下文無關文法定義的語言

2.3 文法的分類

2.3.1 文法分類

2.3.2 文法分類的意義

2.3.3 文法舉例

2.4 語言和語法

2.4.1 句型、句子和語言

2.4.2 語法樹

2.4.3 語法樹的生成過程

2.5 文法和語言的一些特性

2.5.1 無用非終結符號

2.5.2 不可達文法符號

2.5.3 可空非終結符

2.5.4 最左、最右推導和規範推導

2.5.5 二義性

2.6 分析方法簡介

2.6.1 自上而下分析方法

2.6.2 確定的自上而下分析方法

2.6.3 自下而上分析方法

2.6.4 文法在內存中的表示

2.7 小結

習題二

第3章 有窮自動機

3.1 概述

3.2 有窮自動機的形式定義

3.2.1 狀態轉換表

3.2.2 狀態轉換圖

3.2.3 構形和移動

3.2.4 自動機的等價性

3.2.5 非確定有窮自動機

3.3 ndfsa到dfsa的轉換

3.3.1 空移環路的尋找和消除

3.3.2 消除空移

3.3.3 利用狀態轉換表消除空移

3.3.4 確定化——子集法

3.3.5 確定化——造表法

3.3.6 消除不可達狀態

3.3.7 確定的有窮自動機的化簡

3.3.8 從化簡後的dfsa到程序表示

3.3.9 小結

3.4 正規文法和有窮自動機

3.4.1 從正規文法到fsa

3.4.2 從fsa到正規文法

3.5 正規表達式與fsa

3.5.1 正規表達式的定義

3.5.2 正規表達式的cfg

3.5.3 正規表達式與fsa的對應性

3.5.4 正規表達式到ndfsa的轉換

3.5.5 ndfsa m到正規表達式的轉換

3.5.6 從正規文法到正規表達式

3.6 dfsa在計算機中的表示

3.6.1 矩陣表示法

3.6.2 表結構

3.6.3 程序表示法

3.7 小結

習題三

第4章 詞法分析

4.1 詞法分析概述

4.2 單詞符號

4.3 掃描程序的設計

4.4 標識符的處理

4.4.1 類型的機內表示

4.4.2 標識符的語義表示

4.4.3 符號表（標識符表）

4.4.4 標識符表處理的基本思想

4.5 設計詞法分析程序的直接方法

4.6 與設計掃描程序相關的幾個問題

4.7 小結

習題四

第5章 自上而下語法分析

5.1 非確定的下推自動機

5.1.1 pda的形式定義

5.1.2 pda的構形和移動

5.1.3 上下文無關語言與pda

5.2 消除左遞歸方法

5.2.1 文法的左遞歸性

5.2.2 用擴展的bnf表示法消除左遞歸

5.2.3 直接改寫法

5.2.4 消除所有左遞歸的算法

5.3 LL（k）文法

5.3.1 LL（1）文法的判斷條件

5.3.2 集合first、follow和select的構造

5.4 確定的LL（1）分析器的構造

5.4.1 構造分析表m的算法

5.4.2 LL（1）分析器的總控算法

5.5 LL（k）文法的幾個結論

5.6 遞歸下降分析程序及其設計

5.6.1 框圖設計

5.6.2 程序設計

5.7 帶回溯的自上而下分析法

5.7.1 文法在內存中的存放形式

5.7.2 其他信息的存放

5.7.3 帶回溯的自上而下分析算法

5.8 小結

習題五

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

6.1 短浯和句柄

6.2 移進-歸約方法

6.3 非確定的自下而上分析器

6.4 有關文法的一些關係

6.4.1 關係

6.4.2 布爾矩陣和關係

6.4.3 warshall算法

6.4.4 關係first和last

6.5 簡單優先分析方法

6.5.1 優先關係

6.5.2 簡單優先關係的形式化構造方法

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

6.5.4 簡單優先分析方法的侷限性

6.6 算符優先分析方法

6.6.1 算符優先文法

6.6.2 opg優先關係的構造

6.6.3 素短語及句型的分析

6.6.4 算符優先分析算法

6.7 優先函數及其構造

6.7.1 bell方法

6.7.2 floyd方法

6.7.3 兩種方法的比較

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

6.9 小結

習題六

第7章 自下而上的lr（k）分析方法

7.1 lr（k）文法和lr（k）分析器

7.2 lr（0）分析表的構造

7.2.1 規範句型的活前綴

7.2.2 lr（0）項目

7.2.3 文法g的拓廣文法

7.2.4 closure（1）函數

7.2.5 goto（1，x）函數

7.2.6 lr（0）項目集規範族

7.2.7 有效項目

7.2.8 舉例

7.2.9 lr（0）文法

7.2.10 構造lr（0）分析表的算法

7.2.11 構造lr（0）分析表步驟小結

7.3 slr分析表的構造

7.4 規範lr（1）分析表的構造

7.5 lalr分析表的構造

7.6 無二義性規則的使用

7.7 小結

7.7.1 lr分析程序

7.7.2 lr分析表的自動構造

7.7.3 文法間的關係

7.7.4 lr文法舉例

7.7.5 有關lr文法的幾個結論

習題七

第8章 語法制導翻譯法

8.1 一般原理和樹變換

8.1.1 一般原理

8.1.2 樹變換

8.2 簡單sdts和自上而下翻譯器

8.3 簡單後綴sdts和自下而上翻譯器

8.3.1 後綴翻譯

8.3.2 if-then-else控制語句

8.3.3 函數調用

8.4 抽象語法樹的構造

8.4.1 自下而上構造ast

8.4.2 ast的拓廣

8.5 屬性文法

8.5.1 l屬性文法

8.5.2 s屬性文法

8.6 中間代碼形式

8.6.1 逆波蘭表示法

8.6.2 逆波蘭表示法的推廣

8.6.3 四元式

8.6.4 三元式

8.7 屬性翻譯文法的應用

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

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

8.7.3 布爾表達式到四元式的翻譯

8.7.4 條件語句的翻譯

8.7.5 迭代語句的翻譯

8.8 小結

習題八

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

9.1 數據區和屬性字

9.2 基本數據類型的存儲分配

9.3 數組的存儲分配

9.3.1 單塊存儲方式

9.3.2 信息向量與數組分配程序

9.3.3 多塊存儲方式

9.4 記錄結構的存儲分配

9.5 參數傳遞方式及其實現

9.5.1 換名

9.5.2 傳值

9.5.3 傳地址

9.5.4 傳結果

9.5.5 數組名用做實參

9.5.6 過程名用做實參

9.6 棧式存儲分配方法

9.6.1 概述

9.6.2 現行display和現行數據區

9.6.3 標識符的作用域

9.6.4 分程序的人口和出口工作

9.6.5 過程調用時的存儲管理

9.7 堆式存儲分配方法

9.8 臨時工作單元的存儲分配

9.9 小結

習題九

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

10.1 符號表的一般組織形式

10.2 符號表中的數據

10.3 符號表的構造與查找

10.3.1 線性查找

10.3.2 折半法

10.3.3 雜湊技術

10.4 分程序結構的符號表

10.5 小結

習題十

第11章 優化

11.1 基本塊及其求法

11.2 優化舉例

11.3 利用變量的定義點進行優化

11.3.1 變量的定義點

11.3.2 循環中不變式的外提

11.3.3 運算強度削弱

11.3.4 公共表達式的消除

11.3.5 常量合併

11.4 循環優化

11.5 藉助dag進行優化

11.6 並行分支的優化

11.7 窺孔優化

11.8 小結

習題十一

第12章 代碼生成

12.1 假想的計算機模型

12.2 從四元式生成代碼

12.3 從三元式生成代碼

12.4 從樹形表示生成代碼

12.5 從逆波蘭表示生成代碼

12.6 寄存器的分配

12.7 小結

習題十二

參考文獻