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

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

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

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

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

1.1.1 集合與序列/1

1.1.2 語(yǔ)言/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 重寫(xiě)系統(tǒng)/13

1.3.1 語(yǔ)言模型/14

本書(shū)要點(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 簡(jiǎn)化/23

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

2.2 方法/29

2.2.1 單詞與單詞記號(hào)/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ī)的化簡(jiǎn)/44

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

2.3.4 判定問(wèn)題/60

習(xí)題/62

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

第3章 語(yǔ)法分析/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)證文法形式的語(yǔ)法描述/97

3.3.3 文法的簡(jiǎn)化/99

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

3.3.5 文法不能描述的語(yǔ)法/114

3.3.6 判定問(wèn)題/120

習(xí)題/122

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

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

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

4.2 預(yù)測(cè)分析/136

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

4.2.2 表驅(qū)動(dòng)的預(yù)測(cè)分析/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語(yǔ)法分析/160

5.2.1 LR分析算法/160

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

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

習(xí)題/172

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

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

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

6.1.1 語(yǔ)法樹(shù)/180

6.1.2 三地址碼/185

6.1.3 波蘭式/188

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

6.3 語(yǔ)義分析/191

6.4 符號(hào)表/192

6.4.1 組織/192

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

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

6.5 語(yǔ)法制導(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é)束語(yǔ)/226

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

研究生層次的話題/227

當(dāng)前趨勢(shì)/230

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

A.1 概念/233

類(lèi)接口/234

A.2 代碼/236

參考文獻(xiàn)/256

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

外文書(shū)名: Elements Of Compiler Design

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

平裝: 277頁(yè)

正文語(yǔ)種: 簡(jiǎn)體中文

開(kāi)本: 16

ISBN: 9787302193340

條形碼: 9787302193340

尺寸: 25.6 x 18.4 x 1.4 cm

重量: 762 g

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

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

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

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

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

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

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

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

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