編譯原理簡明教程

目錄 

1章緒論1 
1.1 程序設計語言和編譯程序1 
1.2 編譯程序的歷史及發展3 
1.3 編譯過程和編譯程序結構4 
1.4 編譯程序的開發6 
1.5 構造編譯程序所應具備的知識內容7 
習題1 8 
2章詞法分析10 
2.1 詞法分析器的設計方法10 
2.1.1 單詞符號的分類與輸出形式10 
2.1.2 狀態轉換圖11 
2.2 一個簡單的詞法分析器示例13 
2.2.1 C語言子集的單詞符號表示13 
2.2.2 C語言子集對應的狀態轉換圖14 
2.2.3 狀態轉換圖的實現15 
2.3 正規表達式與有限自動機簡介17 
2.3.1 正規表達式與正規集17 
2.3.2 有限自動機18 
2.4 正規表達式到有限自動機的構造21 
2.4.1 由正規表達式構造等價的非確定有限自動機21 
2.4.2 NFA的確定化22 
2.4.3 確定有限自動機（DFA）的化簡24 
2.4.4 正規表達式到有限自動機構造示例26 
2.5 詞法分析器的自動生成31 
習題2 33 
3章文法和語言36 
3.1 基本概念36 
3.1.1 文法和語言的定義36 
3.1.2 文法產生的語言38 
3.2 形式語言分類39 
3.2.1 類文法的劃分39 
3.2.2 類文法的關係與區別40 
3.2.3 正規表達式與上下文無關文法42 
3.3 推導與語法樹43 
3.3.1 推導與短語43 
3.3.2 語法樹與二義性44 
習題3 49 
4章語法分析—自頂向下分析方法51 
4.1 自頂向下分析原理51 
4.1.1 自頂向下分析存在的不確定性51 
4.1.2 確定的自頂向下分析52 
4.2 遞歸下降分析法56 
4.2.1 算術表達式的遞歸下降分析器56 
4.2.2 無二義性的算術表達式遞歸下降分析器58 
4.3 LL(1)分析法59 
4.3.1 表驅動的LL(1)分析器59 
4.3.2 LL(1)分析表的構造62 
習題4 66 
5章語法分析—自底向上分析方法68 
5.1 自底向上分析原理68 
5.2 算符優先分析法70 
5.2.1 算符優先文法70 
5.2.2 算符優先關係表的構造71 
5.2.3 算符優先分析算法的設計74 
5.2.4 優先函數78 
5.3 LR分析器的工作原理80 
5.4 LR(0)分析器86 
5.4.1 LR(0)項目集規範族的構造86 
5.4.2 LR(0)分析表的構造88 
5.5 SLR(1)分析器93 
5.6 二義文法的應用99 
習題5 103 
6章語義分析和中間代碼生成107 
6.1 概述107 
6.1.1 語義分析的概念107 
6.1.2 語法制導翻譯方法107 
6.2 屬性文法109 
6.2.1 文法的屬性109 
6.2.2 屬性文法110 
6.3 幾種常見的中間語言111 
6.3.1 抽象語法樹111 
6.3.2 逆波蘭表示法112 
6.3.3 三地址代碼114 
6.4 表達式及賦值語句的翻譯116 
6.4.1 簡單算術表達式和賦值語句的翻譯116 
6.4.2 布爾表達式的翻譯118 
6.5 控制語句的翻譯123 
6.5.1 條件語句if的翻譯123 
6.5.2 循環語句的翻譯125 
6.5.3 三種基本控制結構的翻譯127 
6.5.4 多分支控制語句case的翻譯132 
6.5.5 語句標號和轉移語句的翻譯134 
6.6 數組元素的翻譯134 
6.6.1 數組元素的地址計算及中間代碼形式135 
6.6.2 賦值語句中數組元素的翻譯135 
6.6.3 數組元素翻譯示例136 
6.7 過程或函數調用語句的翻譯139 
6.7.1 過程或函數調用的方法139 
6.7.2 過程或函數調用語句的元式生成140 
6.8 說明語句的翻譯141 
6.8.1 變量說明的翻譯141 
6.8.2 數組說明的翻譯141 
6.9 遞歸下降語法制導翻譯方法簡介142 
習題6 143 
7章代碼優化147 
7.1 局部優化147 
7.1.1 基本塊的劃分方法147 
7.1.2 基本塊的DAG方法148 
7.1.3 用DAG進行基本塊的優化處理152 
7.1.4 DAG構造算法的進一步討論153 
7.2 循環優化154 
7.2.1 程序流圖與循環154 
7.2.2 循環的查找156 
7.2.3 循環優化161 
習題7 169 
8章目標程序運行時存儲空間的組織173 
8.1 靜態存儲分配173 
8.2 簡單的棧式存儲分配174 
8.2.1 棧式存儲分配與活動記錄175 
8.2.2 過程的執行176 
8.3 嵌套過程語言的棧式實現179 
8.3.1 嵌套層次顯示表和活動記錄179 
8.3.2 嵌套過程的執行180 
8.3.3 訪問非局部名的另一種實現方法182 
8.4 堆式動態存儲分配185 
8.4.1 堆式存儲的概念185 
8.4.2 堆式存儲的管理方法186 
習題8 188 
9章目標代碼生成190 
9.1 簡單代碼生成器190 
9.1.1 待用信息與活躍信息191 
9.1.2 代碼生成算法193 
9.1.3 寄存器分配194 
9.1.4 源程序到目標代碼生成示例196 
9.2 彙編指令到機器代碼翻譯概述198 
習題9 204 
10章符號表與錯誤處理206 
10.1 符號表206 
10.1.1 符號表的作用206 
10.1.2 符號表的組織207 
10.1.3 分程序結構語言符號表建立208 
10.1.4 非分程序結構語言符號表建立211 
10.1.5 常用符號表結構212 
10.1.6 符號表內容213 
10.2 錯誤處理214 
10.2.1 語法錯誤校正214 
10.2.2 語義錯誤校正220 
習題10 221 
附錄A 8086/8088指令碼匯總表223 
附錄B 8086/8088指令編碼空間表228 
附錄C 習題解答230 
參考文獻290