編譯原理

編譯原理是計算機專業設置的一門重要的專業課程。雖然只有少數人從事編譯方面的工作，但是這門課在理論、技術、方法上都對學生提供了系統而有效的訓練，有利於提高軟件人員的素質和能力。 為了用有限的篇幅較深入地討論編譯的主要內容，本書儘可能用較簡潔的方式描述這些內容。讀者在學習編譯原理時應努力在頭腦中構造一台虛擬機，編譯所涉及的各個環節都能在虛擬機中運作。完成各章後的習題對理解所涉及的內容是有益的。就某個虛擬語言（如PL/0）構造它的編譯程序，對掌握編譯技術是十分重要的。

編譯原理是計算機專業的一門重要專業課，本書旨在介紹編譯程序構造的一般原理和基本方法。內容包括語言和文法、詞法分析、語法分析、語法制導翻譯、中間代碼生成、存儲管理、代碼優化和目標代碼生成。本書較系統地介紹了經典的、廣泛應用的技術，特別注重詞法分析器、語法分析器的自動生成，以及語法制導的翻譯方法和以控制流分析與數據流分析為基礎的代碼優化，並概要介紹了屬性文法和並行編譯。各章之後附有習題，其中包括要求用C語言實現相應的分析器、翻譯器、優化器、代碼生成器的習題。 本書可作為高等院校計算機科學專業的教材，也可作為教師、研究生、軟件技術人員的參考書。

第1章 引論 1

1.1 編譯程序是一種特定的翻譯程序 1

1.2 編譯程序的結構 2

1.2.1 詞法分析階段 2

1.2.2 語法分析階段 2

1.2.3 語義分析、中間代碼生成階段 3

1.2.4 優化階段 3

1.2.5 目標代碼生成階段 3

1.2.6 符號表管理 3

1.2.7 出錯管理程序 3

1.2.8 編譯階段的前端和後端 4

1.2.9 遍 4

1.3 編譯程序的生成 5

1.3.1 自展 5

1.3.2 移植 6

1.3.3 對編譯程序的評價 7

1.4 編譯程序的學習 7

第2章 文法和語言 8

2.1 基本概念 8

2.1.1 語言 8

2.1.2 文法 10

2.1.3 歸約與句柄 12

2.2 分析樹與二義性 14

2.2.1 分析樹 14

2.2.2 子樹 14

2.2.3 二義性 15

2.3 形式語言分類 15

習題2 17

第3章 詞法分析 19

3.1 構造一個簡單的詞法分析器 19

3.1.1 詞法分析器的功能 19

3.1.2 掃描緩衝區 22

3.1.3 超前搜索 23

3.1.4 狀態轉換圖 23

3.1.5 狀態轉換圖的實現 24

3.2 正規表達式與正規集 27

3.2.1 正規式與正規集的定義 27

3.2.2 正規式的性質 29

3.2.3 正規式與正規文法 30

3.3 有限自動機 30

3.3.1 有限自動機的定義 30

3.3.2 FA的表示 31

3.3.3 FA M識別的的語言 32

3.3.4 NFA M的確定化 32

3.3.5 DFA M的簡化 34

3.4 正規式與有限自動機 35

3.4.1 正規式與有限自動機的等價性 35

3.4.2 由正規式構造等價的NFA M 37

3.5 詞法分析器的自動生成 38

習題3 39

第4章 語法分析 41

4.1 語法分析概述 41

4.2 遞歸下降分析方法 41

4.2.1 試探分析法 41

4.2.2 提取左因子 42

4.2.3 消除左遞歸 43

4.2.4 預測分析器 45

4.3 非遞歸的預測分析方法 45

4.3.1 表驅動的預測分析器 45

4.3.2 FIRST集和FOLLW集 48

4.3.3 LL(1)文法 50

4.3.4 預測分析表的構造 51

4.3.5 錯誤處理 52

4.4 算符優先分析法 52

4.4.1 算符優先關係表 53

4.4.2 算符優先分析方法 54

4.4.3 優先關係表的構造 56

4.4.4 優先函數 57

4.4.5 錯誤處理 58

4.5 LR分析器 59

4.5.1 LR分析法 59

4.5.2 識別活前綴的DFA 61

4.5.3 SLR分析表的構造 66

4.5.4 LR(1)分析表的構造 67

4.5.5 LALR分析表的構造 70

4.6 二義文法的應用 75

4.7 分析表的自動生成 77

習題4 78第1章 引論

1.1 編譯程序是一種特定的翻譯程序

1.2 編譯程序的結構

1.2.1 詞法分析階段

1.2.2 語法分析階段

1.2.3 語義分析、中間代碼生成階段

1.2.4 優化階段

1.2.5 目標代碼生成階段

1.2.6 符號表管理

1.2.7 出錯管理程序

1.2.8 編譯階段的前端和後端

1.2.9 遍

1.3 編譯程序的生成

1.3.1 自展

1.3.2 移植

1.3.3 對編譯程序的評價

1.4 編譯程序的學習

第2章 文法和語言

2.1 基本概念

2.1.1 語言

2.1.2 文法

2.1.3 歸約與句柄

2.2 分析樹與二義性

2.2.1 分析樹

2.2.2 子樹

2.2.3 二義性

2.3 形式語言分類

習題2

第3章 詞法分析

3.1 構造一個簡單的詞法分析器

3.1.1 詞法分析器的功能

3.1.2 掃描緩衝區

3.1.3 超前搜索

3.1.4 狀態轉換圖

3.1.5 狀態轉換圖的實現

3.2 正規表達式與正規集

3.2.1 正規式與正規集的定義

3.2.2 正規式的性質

3.2.3 正規式與正規文法

3.3 有限自動機

3.3.1 有限自動機的定義

3.3.2 FA的表示

3.3.3 FA M識別的語言

3.3.4 NFA M的確定化

3.3.5 DFA M的簡化

3.4 正規式與有限自動機

3.4.1 正規式與有限自動機的等價性

3.4.2 由正規式構造等價的NFA M

3.5 詞法分析器的自動生成

習題3

第4章 語法分析

4.1 語法分析概述

4.2 遞歸下降分析方法

4.2.1 試探分析法

4.2.2 提取左因子

4.2.3 消除左遞歸

4.2.4 預測分析器

4.3 非遞歸的預測分析方法

4.3.1 表驅動的預測分析器

4.3.2 FIRST集和FOLLW集

4.3.3 LL(1)文法

4.3.4 預測分析表的構造

4.3.5 錯誤處理

4.4 算符優先分析法

4.4.1 算符優先關係表

4.4.2 算符優先分析方法

4.4.3 優先關係表的構造

4.4.4 優先函數

4.4.5 錯誤處理

4.5 LR分析器

4.5.1 LR分析法

4.5.2 識別活前綴的DFA

4.5.3 SLR分析表的構造

4.5.4 LR(1)分析表的構造

4.5.5 LALR分析表的構造

4.6 二義文法的應用

4.7 分析表的自動生成

習題4

第5章 語法制導翻譯和中間代碼生成

5.1 翻譯概述

5.1.1 靜態語義檢查

5.1.2 語義制導翻譯的例子

5.1.3 翻譯要解決的問題

5.2 中間語言

5.2.1 後綴式表示

5.2.2 圖表示

5.2.3 三地址代碼

5.2.4 三地址語句的種類

5.2.5 三地址代碼的具體實現

5.3 説明語句

5.3.1 一類説明語句的翻譯方案

5.3.2 嵌套過程中的説明語句

5.3.3 記錄中的域名

5.4 賦值語句

5.4.1 只含簡單變量的賦值語句的翻譯

5.4.2 類型轉換

5.4.3 含數組元素的賦值語句的翻譯

5.4.4 訪問記錄結構中的域

5.5 控制流語句

5.5.1 布爾表達式的兩種基本作用

5.5.2 布爾表達式的兩種翻譯方法

5.5.3 數值表示法翻譯方案

5.5.4 控制流語句中布爾表達式的翻譯

5.5.5 控制流語句的翻譯

5.5.6 轉向語句和語句標號

5.6 循環語句、過程調用語句及CASE語句

5.6.1 循環語句的翻譯

5.6.2 過程調用、函數調用語句的翻譯

5.6.3 CASE語句或switch語句的翻譯

5.7 屬性文法

5.7.1 語法制導定義

5.7.2 屬性的分類

5.7.3 依賴圖

5.7.4 語義規則的計算次序

5.7.5 屬性文法的兩個子類

習題5

第6章 運行時存儲空間管理

6.1 變量及存儲分配

6.1.1 程序的存儲空間

6.1.2 活動記錄

6.1.3 變量的存儲分配

6.1.4 存儲分配模式

6.2 靜態分配

6.2.1 FORTRAN程序運行時的結構

6.2.2 運行環境的轉換

6.3 棧式分配

6.3.1 只含半靜態變量的棧式分配

6.3.2 半動態變量的棧式分配

6.3.3 動態變量的存儲分配

6.3.4 非局部環境

6.3.5 對非局部環境的引用

6.4 堆分配

6.5 參數傳遞

6.5.1 數據參數傳遞

6.5.2 過程參數的傳遞

6.6 符號表

6.6.1 符號表的組織

6.6.2 常用的符號表結構

習題6

第7章 代碼優化

7.1 優化概述

7.1.1 優化定義

7.1.2 不同階段的優化

7.1.3 程序流圖的構造

7.2 局部優化

7.2.1 基本塊內的優化

7.2.2 基本塊的dag表示

7.2.3 dag的構造

7.2.4 dag實現的優化

7.2.5 對dag構造算法的修正

7.3 控制流分析及循環的查找

7.3.1 循環的定義

7.3.2 必經結點集

7.3.3 自然循環

7.3.4 可歸約流圖

7.3.5 深度優先搜索

7.4 數據流分析

7.4.1 到達一定值數據流方程和ud鏈

7.4.2 活躍變量數據流方程和du鏈

7.4.3 可用表達式數據流方程與複寫傳播

7.4.4 非常忙表達式與代碼提升

7.4.5 數據流方程的求解

7.5 循環優化

7.5.1 循環優化的例子

7.5.2 代碼外提

7.5.3 歸納變量

7.5.4 強度削弱

7.5.5 刪除歸納變量

習題7

第8章 代碼生成

8.1 目標代碼

8.1.1 代碼生成器的輸入與輸出

8.1.2 目標機

8.2 一個簡單代碼生成器

8.2.1 待用信息

8.2.2 寄存器描述和地址描述

8.2.3 如何生成目標代碼

8.2.4 函數getreg(P:x:=y op z)

8.2.5 代碼生成算法

8.2.6 其他語句的代碼生成

8.3 寄存器分配

8.3.1 執行代價的節省

8.3.2 固定分配寄存器的代碼生成

8.3.3 多重循環的寄存器分配

8.3.4 用圖的點着色法做寄存器分配

8.4 窺孔優化

8.5 由dag生成代碼

8.5.1 重新安排計算次序

8.5.2 dag為樹時最優代碼生成

習題8

第9章 並行編譯概述

9.1 並行計算機及其編譯系統

9.1.1 向量計算機

9.1.2 共享存儲器多處理機

9.1.3 分佈存儲器大規模並行計算機

9.1.4 並行編譯系統的結構

9.2 並行編譯技術

9.2.1 依賴關係

9.2.2 依賴測試

9.2.3 循環向量化與並行化

參考文獻 ^[2]