編譯器設(shè)計(jì)基礎(chǔ)

作者:(美國)梅杜納 (Alexander Meduna) 譯者:楊萍 王生原

Alexander Meduna，PhD，布爾諾理工大學(xué)計(jì)算機(jī)科學(xué)系教授，于1988年在那里獲得博士學(xué)位。從1988至1997年，他在美國密蘇里哥倫比亞大學(xué)講授計(jì)算機(jī)科學(xué)。從2000年起，他在布爾諾理工大學(xué)任教，更加專注于講授計(jì)算機(jī)科學(xué)和數(shù)學(xué)。除了這兩所大學(xué)，他還在美洲、歐洲和日本的幾所大學(xué)短期講授計(jì)算機(jī)科學(xué)。他的課程主要集中于編譯器的編寫。他所教授的內(nèi)容也涵蓋了多種主題，包括自動(dòng)機(jī)、離散數(shù)學(xué)、形式語言、操作系統(tǒng)、程序設(shè)計(jì)語言原理以及計(jì)算理論。

第1章 導(dǎo)引/1

1.1 數(shù)學(xué)基礎(chǔ)/1

1.1.1 集合與序列/1

1.1.2 語言/2

1.1.3 關(guān)系與翻譯/3

1.1.4 圖/4

1.1.5 證明/6

1.2 編譯/8

1.2.1 編譯階段/8

1.2.2 編譯器構(gòu)造/12

1.3 重寫系統(tǒng)/13

1.3.1 語言模型/14

本書要點(diǎn)/15

習(xí)題/15

部分習(xí)題解答/17

第2章 詞法分析/19

2.1 模型/19

2.1.1 正規(guī)表達(dá)式/19

2.1.2 有窮自動(dòng)機(jī)/20

2.1.3 有窮自動(dòng)機(jī)的表示/22

2.1.4 簡化/23

2.1.5 有窮變換機(jī)/28

2.2 方法/29

2.2.1 單詞與單詞記號/29

2.2.2 詞法分析器/33

2.2.3 額外的任務(wù)/39

2.3 理論/39

2.3.1 正規(guī)表達(dá)式到有窮自動(dòng)機(jī)的變換/39

2.3.2 有窮自動(dòng)機(jī)的化簡/44

2.3.3 非正規(guī)詞法構(gòu)造/51

2.3.4 判定問題/60

習(xí)題/62

部分習(xí)題解答/67

第3章 語法分析/69

3.1 模型/69

3.1.1 文法/69

3.1.2 下推自動(dòng)機(jī)/80

3.2 方法/83

3.2.1 自上而下分析/83

3.2.2 遞歸下降分析程序/86

3.2.3 消除左遞歸/89

3.2.4 自下而上分析/91

3.3 理論/96

3.3.1 分析模型的能力/97

3.3.2 驗(yàn)證文法形式的語法描述/97

3.3.3 文法的簡化/99

3.3.4 文法的范式和基于它們的分析/108

3.3.5 文法不能描述的語法/114

3.3.6 判定問題/120

習(xí)題/122

部分習(xí)題解答/127

第4章 確定的自上而下分析/130

4.1 預(yù)測集合和LL文法/130

4.2 預(yù)測分析/136

4.2.1 遞歸下降預(yù)測分析/136

4.2.2 表驅(qū)動(dòng)的預(yù)測分析/139

4.2.3 處理錯(cuò)誤/144

習(xí)題/145

部分習(xí)題解答/149

第5章 確定的自下而上分析/151

5.1 優(yōu)先分析/151

5.1.1 算符優(yōu)先分析算法/151

5.1.2 算符優(yōu)先表的構(gòu)造/154

5.1.3 處理錯(cuò)誤/155

5.1.4 擴(kuò)展/158

5.1.5 限制/160

5.2 LR語法分析/160

5.2.1 LR分析算法/160

5.2.2 構(gòu)造LR表/163

5.2.3 LR分析中的錯(cuò)誤處理/170

習(xí)題/172

部分習(xí)題解答/175

第6章 語法制導(dǎo)翻譯和中間代碼生成/178

6.1 自下而上語法制導(dǎo)翻譯和中間代碼生成/179

6.1.1 語法樹/180

6.1.2 三地址碼/185

6.1.3 波蘭式/188

6.2 自上而下的語法制導(dǎo)翻譯/189

6.3 語義分析/191

6.4 符號表/192

6.4.1 組織/192

6.4.2 存儲(chǔ)標(biāo)識符名字/193

6.4.3 塊結(jié)構(gòu)的符號表/194

6.5 語法制導(dǎo)翻譯的軟件工具/195

6.5.1 Lex/196

6.5.2 Yacc/197

習(xí)題/201

部分習(xí)題解答/203

第7章 優(yōu)化和目標(biāo)代碼生成/205

7.1 跟蹤變量的使用/205

7.1.1 基本塊/206

7.1.2 基本塊內(nèi)變量的使用/208

7.1.3 基本塊之間變量的使用/211

7.2 中間代碼優(yōu)化/214

7.3 目標(biāo)代碼的優(yōu)化和生成/218

習(xí)題/222

部分習(xí)題解答/225

結(jié)束語/226

文獻(xiàn)紀(jì)要/226

研究生層次的話題/227

當(dāng)前趨勢/230

附錄A實(shí)現(xiàn)/233

A.1 概念/233

類接口/234

A.2 代碼/236

參考文獻(xiàn)/256

出版社: 清華大學(xué)出版社; 第1版 (2009年4月1日)

外文書名: Elements Of Compiler Design

叢書名: 世界著名計(jì)算機(jī)教材精選

平裝: 277頁

正文語種: 簡體中文

開本: 16

ISBN: 9787302193340

條形碼: 9787302193340

尺寸: 25.6 x 18.4 x 1.4 cm

重量: 762 g

《編譯器設(shè)計(jì)基礎(chǔ)》是編譯器編寫方面的入門教材，適用于一個(gè)學(xué)期的高年級本科課程?！毒幾g器設(shè)計(jì)基礎(chǔ)》堅(jiān)持在這一主題的理論和實(shí)踐方法之間維持一種平衡。從理論角度來看，《編譯器設(shè)計(jì)基礎(chǔ)》介紹了編譯及其核心階段的基本模型?；谶@些模型，它講解了編譯器中用到的概念、方法和技術(shù)?！毒幾g器設(shè)計(jì)基礎(chǔ)》還簡述了編譯以及相關(guān)話題的數(shù)學(xué)基礎(chǔ)，這些話題包括形式語言理論、自動(dòng)機(jī)和變換機(jī)。同時(shí)，從實(shí)踐的視角來看，《編譯器設(shè)計(jì)基礎(chǔ)》描述了編譯器技術(shù)是如何實(shí)現(xiàn)的。一個(gè)案例學(xué)習(xí)貫穿全書，《編譯器設(shè)計(jì)基礎(chǔ)》設(shè)計(jì)一種新的類Pascal程序設(shè)計(jì)語言，并構(gòu)造其編譯器;在討論編譯器各種方法的同時(shí)，這個(gè)案例學(xué)習(xí)用作其實(shí)現(xiàn)的實(shí)例說明。此外，《編譯器設(shè)計(jì)基礎(chǔ)》提供了許多詳細(xì)的例子和計(jì)算機(jī)程序，以強(qiáng)調(diào)編譯算法的實(shí)際應(yīng)用?！毒幾g器設(shè)計(jì)基礎(chǔ)》中也涵蓋了核心軟件工具。學(xué)完《編譯器設(shè)計(jì)基礎(chǔ)》之后，學(xué)生應(yīng)該能夠掌握編譯過程，編寫簡單的真實(shí)編譯器，并可以繼續(xù)學(xué)習(xí)關(guān)于該主題的更深入的書籍。

編譯 器可以生成用來在與編譯器本身所在的計(jì)算機(jī)和操作系統(tǒng)(平臺(tái))相同的環(huán)境下運(yùn)行的目標(biāo)代碼，這種編譯器又叫做"本地"編譯器。另外，編譯器也可以生成用來在其它平臺(tái)上運(yùn)行的目標(biāo)代碼，這種編譯器又叫做交叉編譯器。交叉編譯器在生成新的硬件平臺(tái)時(shí)非常有用。"源碼到源碼編譯器"是指用一種高級語言作為輸入，輸出也是高級語言的編譯器。例如: 自動(dòng)并行化編譯器經(jīng)常采用一種高級語言作為輸入，轉(zhuǎn)換其中的代碼，并用并行代碼注釋對它進(jìn)行注釋(如OpenMP)或者用語言構(gòu)造進(jìn)行注釋(如FORTRAN的DOALL指令)。

作用是通過代入預(yù)定義等程序段將源程序補(bǔ)充完整。

前端主要負(fù)責(zé)解析(parse)輸入的源代碼，由語法分析器和語意分析器協(xié)同工作。語法分析器負(fù)責(zé)把源代碼中的'單詞'(Token)找出來，語意分析器把這些分散的單詞按預(yù)先定義好的語法組裝成有意義的表達(dá)式，語句 ，函數(shù)等等。 例如"a = b + c;"前端語法分析器看到的是"a， =， b ， +， c;"，語意分析器按定義的語法，先把他們組裝成表達(dá)式"b + c"，再組裝成"a = b + c"的語句。 前端還負(fù)責(zé)語義(semantic checking)的檢查，例如檢測參與運(yùn)算的變量是否是同一類型的，簡單的錯(cuò)誤處理。最終的結(jié)果常常是一個(gè)抽象的語法樹(abstract syntax tree，或 AST)，這樣后端可以在此基礎(chǔ)上進(jìn)一步優(yōu)化，處理。

編譯器后端主要負(fù)責(zé)分析，優(yōu)化中間代碼(Intermediate representation)以及生成機(jī)器代碼(Code Generation)。

一般說來所有的編譯器分析，優(yōu)化，變型都可以分成兩大類: 函數(shù)內(nèi)(intraprocedural)還是函數(shù)之間(interprocedural)進(jìn)行。很明顯，函數(shù)間的分析，優(yōu)化更準(zhǔn)確，但需要更長的時(shí)間來完成。

編譯是從源代碼(通常為高級語言)到能直接被計(jì)算機(jī)或虛擬機(jī)執(zhí)行的目標(biāo)代碼(通常為低級語言或機(jī)器語言)的翻譯過程。然而，也存在從低級語言到高級語言的編譯器，這類編譯器中用來從由高級語言生成的低級語言代碼重新生成高級語言代碼的又被叫做反編譯器。也有從一種高級語言生成另一種高級語言的編譯器，或者生成一種需要進(jìn)一步處理的的中間代碼的編譯器(又叫級聯(lián))。

典型的編譯器輸出是由包含入口點(diǎn)的名字和地址， 以及外部調(diào)用(到不在這個(gè)目標(biāo)文件中的函數(shù)調(diào)用)的機(jī)器代碼所組成的目標(biāo)文件。一組目標(biāo)文件，不必是同一編譯器產(chǎn)生，但使用的編譯器必需采用同樣的輸出格式，可以鏈接在一起并生成可以由用戶直接執(zhí)行的EXE,

所以我們電腦上的文件都是經(jīng)過編譯后的文件。