本書系統(tǒng)全面地介紹經(jīng)典、廣泛應(yīng)用的高級程序設(shè)計語言編譯程序的構(gòu)造原理、實現(xiàn)技術(shù)、方法和工具。本書包含了現(xiàn)代編譯程序設(shè)計的基礎(chǔ)理論和技術(shù)，并在語義分析、代碼優(yōu)化,面向?qū)ο笳Z言的編譯及高級優(yōu)化技術(shù)等方面反映了20世紀(jì)90年代后的一些重要研究成果,特別兼顧近年來編譯原理及技術(shù)的發(fā)展和發(fā)生的一些重要變化,專辟“編譯技術(shù)高級專題”予以介紹。本書的組織注重提煉精華、循序漸進(jìn)、深入淺出,每章開頭提煉了該章涉及的主要內(nèi)容、要點和關(guān)鍵概念,全書精編、精選了近300道各種類型的習(xí)題和思考題,還提供了編譯程序?qū)崿F(xiàn)的具體實例,能夠輔助讀者更好地學(xué)習(xí)和掌握編譯原理。
本書可以作為計算機(jī)學(xué)科類專業(yè)及相關(guān)專業(yè)本科和研究生編譯原理的教科書,也可以作為軟件技術(shù)人員的參考用書。
編譯原理作為計算機(jī)學(xué)科的一門重要專業(yè)基礎(chǔ)課,列入國際ACM教程和IEEE計算機(jī)學(xué)科的正式主干課程,并提高該課程內(nèi)容的課時比重,這充分體現(xiàn)了其在計算機(jī)科學(xué)中的地位和作用。
編譯程序是計算機(jī)系統(tǒng)軟件的主要組成部分,是計算機(jī)科學(xué)中發(fā)展迅速、系統(tǒng)、成熟的一個分支,其基本原理和技術(shù)也適用于一般軟件的設(shè)計和實現(xiàn),而且在語言處理、軟件工程、軟件自動化、逆向軟件工程、再造軟件工程等諸多領(lǐng)域有著廣泛的應(yīng)用。
本書旨在介紹編譯程序設(shè)計的基本原理、實現(xiàn)技術(shù)、方法和工具。本書的前驅(qū)版本系陳英教授主編,獲得北京市2008年高校精品教材。在此基礎(chǔ)上,規(guī)劃、整合為“編譯原理”課程的系列叢書,包括作為教材的本書及后續(xù)即將推出的《編譯原理學(xué)習(xí)指導(dǎo)與習(xí)題解析》和《編譯原理課程設(shè)計》。全書分為11章,第1章作為全書的開場白,介紹了編譯程序有關(guān)的概念,編譯過程、編譯程序的結(jié)構(gòu)與組織等要點。第2章作為后續(xù)各章的基礎(chǔ)知識,也是學(xué)習(xí)編譯原理應(yīng)起碼具備的理論基礎(chǔ),對形式語言與自動機(jī)理論作了基本的介紹。第3章以正則文法、正規(guī)式、有限自動機(jī)為工具,討論了詞法分析器的設(shè)計與實現(xiàn)。第4章和第5章對常規(guī)的語法分析方法,即自上而下和自下而上分析中的幾種經(jīng)典方法展開了較深入的討論,并結(jié)合流行、實用、高效的LR分析方法,介紹了二義文法的分析應(yīng)用,編譯程序的出錯處理。第3章和第5章還討論了流行的詞法分析和語法分析自動生成工具Lex及Flex,YACC及Bison的構(gòu)造原理與應(yīng)用,并以ANSI_C語言為例,給出了其Lex和YACC的描述。第6章涉及語義分析方法和屬性翻譯文法,中間語言,符號表及類型檢查技術(shù),流行的高級程序設(shè)計語言中典型語句的翻譯。第7章介紹編譯程序運行時環(huán)境的有關(guān)概念和存儲組織與分配技術(shù)。第8章介紹中間代碼級上的優(yōu)化,展開討論了優(yōu)化的基本概念,優(yōu)化涉及的控制流分析和數(shù)據(jù)流分析技術(shù),以及中間代碼上的局部優(yōu)化和循環(huán)優(yōu)化技術(shù)及實現(xiàn)。第9章簡單介紹了代碼生成的有關(guān)知識點及目標(biāo)代碼級可實施的窺孔優(yōu)化技術(shù)。第10章以PL/0語言為源語言,提供了一個短小、精悍的編譯程序?qū)崿F(xiàn)的范例,以彌補(bǔ)編譯程序從原理到工程實現(xiàn)的鴻溝。第11章反映了20世紀(jì)90年代后本領(lǐng)域的一些重要研究成果,如面向?qū)ο笳Z言的翻譯、GLR分析。另外,高性能體系結(jié)構(gòu)的發(fā)展與技術(shù)對編譯技術(shù)提出新的挑戰(zhàn)。本章針對主流并行處理器體系結(jié)構(gòu)及與之相關(guān)的編譯優(yōu)化技術(shù)進(jìn)行簡要介紹,如并行優(yōu)化技術(shù)、存儲層次及其優(yōu)化技術(shù)等。
縱觀本書的組織,注重循序漸進(jìn),深入淺出,每章開頭提煉了該章涉及的主要內(nèi)容提要和關(guān)鍵概念,全書精編、精選了近300道各種類型的習(xí)題和思考題,還提供了編譯程序?qū)崿F(xiàn)的具體實例,輔助讀者更好地學(xué)習(xí)和掌握編譯原理。
本書是作者多年教學(xué)實踐和科研工作的匯集、提煉和整理,特別是北京理工大學(xué)“編譯原理”課程組老師們奉獻(xiàn)了他們教學(xué)實踐的匯集和積累。本書完成的責(zé)任編著和輔助編著的直接承擔(dān)者是: 陳英第1, 3, 4, 5, 6, 9和11章;王貴珍第2, 10, 4和11章;李侃第6, 7, 11和2章;計衛(wèi)星第8, 9, 11, 1和5章;陳朔鷹第3, 7和8章。本書參考了國內(nèi)外一些專著、論文和資料,參考、借鑒了一些專家學(xué)者的研究成果,對所有這些前輩和同行的引導(dǎo)和幫助表示衷心的感謝。另外,本書過去多個不同版本通過數(shù)屆學(xué)生和讀者的使用,亦得到了他們許多寶貴的反饋意見和建議。 本書完成過程中,得到了清華大學(xué)出版社的鼎力協(xié)助,尤其是編審謝琛高效的工作和非常專業(yè)的指導(dǎo),作者在此一并深為致謝。
鑒于作者水平有限,本書稿雖經(jīng)審慎校閱,仍難免存在疏誤,敬請讀者不吝賜教。
編 者2009年1月于北京
第1章 編譯引論 /1
1.1 程序設(shè)計語言與編譯程序 /1
1.1.1 編譯程序鳥瞰 /1
1.1.2 源程序的執(zhí)行 /2
1.2 編譯程序的表示與分類 /2
1.2.1 T型圖 /2
1.2.2 編譯程序的分類 /3
1.3 編譯程序的結(jié)構(gòu)與編譯過程 /4
1.3.1 編譯程序的結(jié)構(gòu)與編譯過程 /4
1.3.2 編譯程序結(jié)構(gòu)的公共功能與編譯程序的
組織 /9
1.4 語言開發(fā)環(huán)境中的伙伴程序 /10
1.5 編譯程序結(jié)構(gòu)的實例模型 /11
1.5.1 一遍編譯程序結(jié)構(gòu) /11
1.5.2 PRIME機(jī)上AHPL語言的兩遍編譯
程序 /11
1.5.3 PDP-11計算機(jī)上C語言的三遍編譯
程序 /11
1.5.4 Tiger編譯程序結(jié)構(gòu) /12
1.5.5 GCC編譯程序結(jié)構(gòu)框架 /13
1.6 編譯程序的構(gòu)造與實現(xiàn) /14
1.6.1 如何構(gòu)造一個編譯程序 /14
1.6.2 編譯程序的生成方式 /15
1.6.3 編譯程序的構(gòu)造工具 /15
習(xí)題1 /16第2章 形式語言與自動機(jī)理論基礎(chǔ) /18
2.1 文法和語言 /18
2.1.1 語言的語法和語義 /18
2.1.2 文法和語言的定義 /19
2.1.3 文法的表示方法 /25
2.1.4 語法分析樹與二義性 /26
2.1.5 文法和語言的類型 /29
2.2 有限自動機(jī) /30
2.2.1 確定的有限自動機(jī) /31
2.2.2 非確定的有限自動機(jī) /33
2.2.3 確定的有限自動機(jī)與非確定的有限自動機(jī)的等價 /35
2.2.4 確定的有限自動機(jī)的化簡 /38
2.3 正規(guī)式與有限自動機(jī) /42
2.3.1 有限自動機(jī)與正則文法 /42
2.3.2 正規(guī)式與正規(guī)集 /43
2.3.3 正規(guī)式與有限自動機(jī) /44
習(xí)題2 /52第3章 詞法分析 /58
3.1 詞法分析與詞法分析程序 /58
3.2 詞法分析程序設(shè)計與實現(xiàn) /59
3.2.1 詞法分析程序的輸入與輸出 /59
3.2.2 源程序的輸入與預(yù)處理 /60
3.2.3 單詞的識別 /61
3.2.4 詞法分析程序與語法分析程序
的接口 /62
3.2.5 詞法分析器的設(shè)計與實現(xiàn) /62
3.3 詞法分析程序的自動生成 /68
3.3.1 詞法分析自動實現(xiàn)思想與自動生成
器--Lex/Flex /68
3.3.2 Lex運行與應(yīng)用過程 /68
3.3.3 Lex語言 /69
3.3.4 詞法分析器產(chǎn)生器的實現(xiàn) /73
3.3.5 Lex應(yīng)用 /74
習(xí)題3 /78第4章 語法分析--自上而下分析 /79
4.1 語法分析綜述 /79
4.1.1 語法分析程序的功能 /79
4.1.2 語法分析方法 /80
4.2 不確定的自上而下語法分析 /81
4.2.1 一般自上而下分析 /81
4.2.2 不確定性的原因與解決方法 /82
4.2.3 消除回溯 /85
4.3 遞歸下降分析法與遞歸下降分析器 /86
4.3.1 遞歸下降分析器的實現(xiàn) /86
4.3.2 遞歸下降分析器設(shè)計工具--狀態(tài)轉(zhuǎn)
換圖 /87
4.4 LL(1)分析法與LL(1)分析器 /89
4.4.1 LL(1)分析器的邏輯結(jié)構(gòu)與動態(tài)
實現(xiàn) /89
4.4.2 LL(1)分析表的構(gòu)造 /91
4.4.3 關(guān)于LL(1)文法 /94
習(xí)題4 /95第5章 語法分析--自下而上分析 /99
5.1 基于“移進(jìn)-歸約”的自下而上分析 /99
5.1.1 “移進(jìn)-歸約”分析 /99
5.1.2 規(guī)范歸約與句柄 /101
5.2 算符優(yōu)先分析法與算符優(yōu)先分析器 /103
5.2.1 直觀的算符優(yōu)先分析法 /103
5.2.2 算符優(yōu)先文法和算符優(yōu)先分析表的
構(gòu)造 /106
5.2.3 算符優(yōu)先分析法實現(xiàn)的理論探討 /109
5.2.4 優(yōu)先函數(shù)表的構(gòu)造 /112
5.3 LR分析 /114
5.3.1 LR分析法與LR文法 /114
5.3.2 LR(0)分析及LR(0)分析表的
構(gòu)造 /119
5.3.3 SLR(1)分析及SLR(1)分析表的
構(gòu)造 /128
5.3.4 LR(1)分析及LR(1)分析表的
構(gòu)造 /130
5.3.5 LALR(1)分析及LALR(1)分析表的
構(gòu)造 /135
5.4 LR分析對二義文法的應(yīng)用 /138
5.5 LR分析的錯誤處理與恢復(fù) /140
5.6 語法分析程序自動生成器 /142
5.6.1 YACC綜述與應(yīng)用 /143
5.6.2 YACC語言 /144
5.6.3 YACC處理二義文法 /145
5.6.4 YACC的錯誤恢復(fù) /147
5.6.5 YACC應(yīng)用 /148
習(xí)題5 /158第6章 語義分析與中間代碼生成 /163
6.1 語法制導(dǎo)翻譯 /163
6.1.1 語法制導(dǎo)定義 /164
6.1.2 綜合屬性 /165
6.1.3 繼承屬性 /166
6.1.4 依賴圖 /166
6.1.5 語法樹的構(gòu)造 /168
6.1.6 S_屬性定義與自下而上計算 /168
6.1.7 L_屬性定義與翻譯模式 /169
6.2 符號表 /172
6.2.1 符號表的組織 /173
6.2.2 分程序結(jié)構(gòu)的符號表 /174
6.3 類型檢查 /177
6.3.1 類型體制 /177
6.3.2 一個簡單的類型檢查程序 /179
6.4 中間語言 /183
6.4.1 逆波蘭表示法 /183
6.4.2 N-元式表示法 /184
6.4.3 圖表示法 /186
6.5 中間代碼生成 /186
6.5.1 說明類語句的翻譯 /186
6.5.2 賦值語句與表達(dá)式的翻譯 /189
6.5.3 控制流語句的翻譯 /190
6.5.4 數(shù)組說明和數(shù)組元素引用的翻譯 /196
6.5.5 過程、函數(shù)說明和調(diào)用的翻譯 /198
習(xí)題6 /199第7章 運行環(huán)境 /203
7.1 程序運行時的存儲組織與分配 /203
7.1.1 關(guān)于存儲組織 /203
7.1.2 過程的活動記錄 /204
7.1.3 存儲分配策略 /205
7.2 靜態(tài)運行時環(huán)境與存儲分配 /206
7.3 基于棧的運行時環(huán)境的動態(tài)存儲分配 /208
7.3.1 簡單的棧式存儲分配的實現(xiàn) /208
7.3.2 嵌套過程語言的棧式存儲分配的
實現(xiàn) /210
7.4 基于堆的運行時環(huán)境的動態(tài)存儲分配 /212
7.4.1 基于堆的運行時環(huán)境的動態(tài)存儲分配的
實現(xiàn) /212
7.4.2 關(guān)于懸空引用 /214
習(xí)題7 /216第8章 代碼優(yōu)化 /221
8.1 代碼優(yōu)化概述 /221
8.1.1 代碼優(yōu)化的概念 /221
8.1.2 優(yōu)化技術(shù)分類 /222
8.1.3 優(yōu)化編譯程序的組織 /227
8.2 局部優(yōu)化 /227
8.2.1 基本塊的定義與劃分 /227
8.2.2 程序的控制流圖 /228
8.2.3 基本塊的DAG表示及應(yīng)用 /229
8.3 控制流分析與循環(huán)查找 /236
8.4 數(shù)據(jù)流分析 /239
8.4.1 程序中的點與通路 /239
8.4.2 到達(dá)-定值數(shù)據(jù)流方程及其方程
求解 /239
8.4.3 引用-定值鏈(ud鏈) /242
8.4.4 活躍變量與數(shù)據(jù)流方程 /242
8.4.5 定值-引用鏈(du鏈)與du鏈數(shù)據(jù)流
方程 /243
8.4.6 可用表達(dá)式數(shù)據(jù)流方程 /244
8.5 循環(huán)優(yōu)化 /244
8.5.1 代碼外提 /245
8.5.2 強(qiáng)度削弱 /247
8.5.3 變換循環(huán)控制變量（刪除歸納
變量） /247
習(xí)題8 /249第9章 代碼生成 /253
9.1 代碼生成器設(shè)計中的要點 /253
9.1.1 代碼生成器的輸入與輸出 /253
9.1.2 指令的選擇 /254
9.1.3 寄存器分配 /255
9.1.4 存儲管理 /256
9.2 簡單代碼生成器的構(gòu)造 /256
9.3 目標(biāo)代碼的窺孔優(yōu)化 /258
9.3.1 冗余指令序列 /259
9.3.2 控制流優(yōu)化 /260
9.3.3 代數(shù)化簡 /261
9.3.4 窺孔優(yōu)化實例 /261
習(xí)題9 /264第10章 編譯程序?qū)崿F(xiàn)范例 /265
10.1 PL/0語言描述 /265
10.2 PL/0編譯程序的結(jié)構(gòu) /266
10.3 PL/0編譯程序的詞法分析 /268
10.4 PL/0編譯程序的語法分析 /270
10.5 PL/0編譯程序的目標(biāo)代碼結(jié)構(gòu)和代碼
生成 /274
10.6 PL/0編譯程序的語法錯誤處理 /276
10.7 PL/0編譯程序的目標(biāo)代碼解釋執(zhí)行時的
存儲分配 /279
10.8 PL/0編譯程序文本 /281
習(xí)題10 /301第11章 編譯技術(shù)高級專題 /303
11.1 面向?qū)ο笳Z言的翻譯 /303
11.1.1 面向?qū)ο蟪绦蛟O(shè)計語言的概念 /303
11.1.2 面向?qū)ο笳Z言的翻譯 /305
11.1.3 面向?qū)ο笳Z言中的動態(tài)存儲 /308
11.2 高性能計算機(jī)體系結(jié)構(gòu)及發(fā)展趨勢 /309
11.2.1 支持指令級并行的處理器簡介 /310
11.2.2 支持線程級并行的處理器簡介 /313
11.2.3 高性能體系結(jié)構(gòu)對編譯器的
挑戰(zhàn) /316
11.3 關(guān)于并行優(yōu)化技術(shù) /316
11.3.1 指令相關(guān)與指令并行化 /316
11.3.2 循環(huán)展開與優(yōu)化 /319
11.3.3 VLIW指令調(diào)度 /322
11.4 存儲層次及其優(yōu)化技術(shù) /323
11.4.1 存儲層次與Cache組織結(jié)構(gòu) /323
11.4.2 Cache預(yù)取 /324
11.4.3 循環(huán)交換 /325
11.4.4 循環(huán)分塊 /327
11.5 關(guān)于GLR分析法 /329
習(xí)題11 /335
參考文獻(xiàn) /337
書單推薦
