第1章 編譯簡(jiǎn)述 1 1.1 程序的翻譯 1 1.1.1 程序設(shè)計(jì)語(yǔ)言 1 1.1.2 編譯程序 2 1.1.3 實(shí)現(xiàn)高級(jí)語(yǔ)言的編譯方式 2 1.2 編譯程序的組成 3 1.2.1 編譯程序的構(gòu)成 4 1.2.2 遍 5 1.2.3 編譯程序前端和后端 5 1.3 編譯程序的構(gòu)造 5 1.4 小結(jié) 6 復(fù)習(xí)思考題 7 第2章 形式語(yǔ)言與詞法分析 8 2.1 字母表和符號(hào)串的基本概念 8 2.1.1 字母表和符號(hào)串 9 2.1.2 符號(hào)串的運(yùn)算 10 2.2 文法和語(yǔ)言的形式定義 11 2.2.1 形式語(yǔ)言 12 2.2.2 文法的形式定義 13 2.2.3 語(yǔ)言的形式定義 14 2.3 語(yǔ)法樹與文法二義性 17 2.3.1 語(yǔ)法樹 17 2.3.2 文法二義性 18 2.4 文法和語(yǔ)言的分類 19 2.5 詞法分析的任務(wù) 20 2.5.1 詞法分析的任務(wù)描述 20 2.5.2 詞法分析器與語(yǔ)法分析器的接口 20 2.6 詞法分析程序的輸出形式 21 2.6.1 單詞符號(hào)的分類 21 2.6.2 詞法分析程序單詞的輸出形式 22 2.6.3 詞法錯(cuò)誤 23 2.7 詞法分析程序的設(shè)計(jì)與實(shí)現(xiàn) 24 2.7.1 輸入和預(yù)處理功能 24 2.7.2 單詞符號(hào)的識(shí)別 25 2.7.3 狀態(tài)轉(zhuǎn)換圖 26 2.7.4 狀態(tài)轉(zhuǎn)換圖的實(shí)現(xiàn) 26 2.8 正規(guī)表達(dá)式與有限自動(dòng)機(jī) 27 2.8.1 正規(guī)表達(dá)式與正規(guī)集 28 2.8.2 有限自動(dòng)機(jī) 31 2.9 詞法分析程序的自動(dòng)生成工具Lex 40 2.10 實(shí)例語(yǔ)言的詞法分析程序 43 2.10.1 微小語(yǔ)言Micro 43 2.10.2 Micro的詞法分析 43 2.11 小結(jié) 45 復(fù)習(xí)思考題 46 第3章 自頂向下語(yǔ)法分析 50 3.1 自頂向下分析的一般方法 51 3.2 LL(1)文法 52 3.2.1 消除左遞歸 52 3.2.2 提取左因子 53 3.3 遞歸下降分析法 58 3.4 LL(1)分析法 60 3.4.1 非遞歸預(yù)測(cè)分析器 60 3.4.2 構(gòu)造預(yù)測(cè)分析表 62 3.5 預(yù)測(cè)分析中的錯(cuò)誤處理 63 3.6 小結(jié) 64 復(fù)習(xí)思考題 64 第4章 自底向上語(yǔ)法分析 66 4.1 自底向上分析的基本概念 66 4.1.1 歸約 66 4.1.2 句柄 67 4.1.3 用棧實(shí)現(xiàn)自底向上分析 68 4.1.4 移進(jìn)-歸約分析的沖突 69 4.2 算符優(yōu)先分析 70 4.2.1 直觀算符優(yōu)先分析法 71 4.2.2 算符優(yōu)先文法的定義 73 4.2.3 算符優(yōu)先關(guān)系表的構(gòu)造 74 4.2.4 算符優(yōu)先分析算法 75 4.2.5 優(yōu)先函數(shù) 76 4.2.6 算符優(yōu)先分析法的局限性 78 4.3 LR分析法 78 4.3.1 LR分析算法 79 4.3.2 LR文法和LR分析方法的特點(diǎn) 81 4.3.3 構(gòu)造LR(0)分析表 82 4.3.4 構(gòu)造SLR(1)分析表 88 4.3.5 構(gòu)造規(guī)范的LR分析表 92 4.3.6 構(gòu)造LALR分析表 95 4.3.7 二義文法的應(yīng)用 97 4.4 語(yǔ)法分析程序的自動(dòng)生成工具YACC 101 4.5 實(shí)例語(yǔ)言編譯程序的語(yǔ)法分析 104 4.6 小結(jié) 106 復(fù)習(xí)思考題 107 第5章 語(yǔ)義分析與中間代碼的生成 110 5.1 語(yǔ)義分析的任務(wù) 110 5.1.1 語(yǔ)義分析的概念 110 5.1.2 語(yǔ)義分析的任務(wù) 111 5.2 語(yǔ)法制導(dǎo)翻譯 111 5.2.1 屬性文法 111 5.2.2 語(yǔ)法制導(dǎo)翻譯方法 111 5.3 中間代碼 112 5.3.1 逆波蘭表示法 112 5.3.2 四元式 112 5.3.3 三元式 113 5.3.4 間接三元式 113 5.3.5 抽象語(yǔ)法樹 114 5.4 說明語(yǔ)句的翻譯 114 5.4.1 簡(jiǎn)單說明語(yǔ)句的翻譯 114 5.4.2 過程中的說明 115 5.5 賦值語(yǔ)句的翻譯 115 5.5.1 簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯 115 5.5.2 數(shù)組的翻譯 117 5.6 布爾表達(dá)式的翻譯 117 5.7 控制語(yǔ)句的翻譯 120 5.7.1 條件語(yǔ)句if的翻譯 121 5.7.2 循環(huán)語(yǔ)句while的翻譯 122 5.7.3 三種基本控制結(jié)構(gòu)的翻譯 123 5.8 過程調(diào)用的翻譯 124 5.9 實(shí)例編譯程序的語(yǔ)義分析 125 5.10 小結(jié) 127 復(fù)習(xí)思考題 127 第6章 符號(hào)表管理 131 6.1 符號(hào)表的作用 131 6.1.1 收集標(biāo)識(shí)符屬性信息 131 6.1.2 符號(hào)表內(nèi)容為上下文語(yǔ)義的合法性檢查提供依據(jù) 132 6.1.3 作為目標(biāo)代碼生成階段編譯程序分配地址空間的依據(jù) 132 6.2 符號(hào)表的主要內(nèi)容 132 6.2.1 符號(hào)名 132 6.2.2 符號(hào)的類型 133 6.2.3 符號(hào)的存儲(chǔ)類型 133 6.2.4 符號(hào)的作用域及可視性 133 6.2.5 符號(hào)變量的存儲(chǔ)分配信息 134 6.2.6 符號(hào)的其他屬性 136 6.3 符號(hào)表的組織 136 6.3.1 符號(hào)表的總體組織 136 6.3.2 符號(hào)表項(xiàng)的組織 138 6.4 符號(hào)表的管理 142 6.4.1 符號(hào)表的初始化 142 6.4.2 符號(hào)的插入 143 6.4.3 符號(hào)的查找 145 6.5 小結(jié) 146 復(fù)習(xí)思考題 146 第7章 運(yùn)行時(shí)的存儲(chǔ)組織與分配 147 7.1 存儲(chǔ)組織概述 147 7.1.1 運(yùn)行時(shí)內(nèi)存的劃分 147 7.1.2 過程活動(dòng)記錄 149 7.2 靜態(tài)存儲(chǔ)分配 150 7.3 棧式動(dòng)態(tài)存儲(chǔ)分配 151 7.3.1 棧的結(jié)構(gòu) 151 7.3.2 活動(dòng)樹和簡(jiǎn)單的棧式存儲(chǔ)分配 151 7.3.3 嵌套過程語(yǔ)言的棧式實(shí)現(xiàn) 153 7.4 堆式動(dòng)態(tài)存儲(chǔ)分配 154 7.5 小結(jié) 156 復(fù)習(xí)思考題 156 第8章 代碼優(yōu)化 158 8.1 局部?jī)?yōu)化 159 8.1.1 基本塊的劃分 159 8.1.2 利用基本塊DAG進(jìn)行優(yōu)化 162 8.2 循環(huán)優(yōu)化 166 8.2.1 程序流圖 166 8.2.2 循環(huán)的查找 167 8.2.3 循環(huán)優(yōu)化 169 8.3 小結(jié) 171 復(fù)習(xí)思考題 171 第9章 目標(biāo)代碼生成 173 9.1 目標(biāo)代碼的形式 173 9.2 假想的計(jì)算機(jī)模型 174 9.3 一個(gè)簡(jiǎn)單的代碼生成程序 175 9.3.1 待用信息和活躍信息 175 9.3.2 寄存器描述和地址描述 175 9.3.3 代碼生成算法 176 9.3.4 寄存器選擇函數(shù) 177 9.3.5 為變址和指針語(yǔ)句產(chǎn)生代碼 178 9.3.6 條件語(yǔ)句 178 9.4 小結(jié) 180 復(fù)習(xí)思考題 180 附錄A C語(yǔ)言實(shí)現(xiàn)的實(shí)例語(yǔ)言編譯程序 181 附錄B YACC語(yǔ)言實(shí)現(xiàn)的實(shí)例語(yǔ)言編譯程序 184 參考文獻(xiàn) 185