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