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