自己動手寫編譯器、連結器

自己動手寫編譯器、連結器

本書講述了一個真實編譯器的開發過程,源語言是以C語言為藍本,進行適當簡化定義的一門新語言,稱之為SC語言(簡化的C語言),目標語言是大家熟悉的Intel x86機器語言。在本書中,讀者將看到從SC語言定義,到SCC編譯器開發的完整過程。本書介紹的SCC編譯器,沒有藉助Lex與Yacc這些編譯器自動生成工具,純手工編寫而成,更便於學習和理解。為了生成可以直接運行EXE檔案,本書還實現了一個連結器。讀完本書讀者將知道一門全新的語言如何定義,一個真實的編譯器、連結器如何編寫。 本書適合各類程式設計師、程式開發愛好者閱讀,也可作為高等院校編譯原理課程的實踐教材。

前言

紙上得來終覺淺,絕知此事要躬行。

——陸游編譯原理與技術的一整套理論在整個計算機科學領域占有相當重要的地位,學習它對程式設計人員有很大的幫助。我們考究歷史會發現那些人人稱頌的程式設計大師都是編譯領域的高手,像寫出Sun公司的Java之父等,在編譯領域都有很深的造詣。曾經在世界首富寶座上穩坐多年的比爾·蓋茨也是從給微機編寫BASIC語言編譯器起家的,也正是這個BASIC編譯器為比爾·蓋茨和保羅·艾倫的微軟帝國奠定了基礎。這個編寫BASIC語言編譯器的經歷,開啟了比爾·蓋茨的輝煌職業生涯。

編譯器是一種相當複雜的程式,編寫甚至讀懂這樣的一個程式都非易事,大多數的計算機科學家和專業人員也從來沒有編寫過一個完整的編譯器。但是,幾乎所有形式的計算都要用到編譯器,而且任何一個與計算機打交道的專業人員都應掌握編譯器的基本結構和操作。除此之外,計算機應用程式中經常遇到的一個任務就是命令解釋程式和界面程式的開發,這比編譯器要小,但使用的卻是相同的技術。因此,掌握這一技術具有非常大的實際意義。

李國傑院士說: “隨著微處理器技術的飛速發展,處理器性能在很大程度上取決於編譯器的質量,編譯技術成為計算機的核心技術,地位變得越來越重要。我國要發展自己的微處理器事業,必然要有自己的編譯技術作為後盾。”

回過頭來說一說是什麼樣的原因使我萌生了寫這樣一本書的想法。作者學習其他計算機課程感覺沒有特別難懂的,唯獨看編譯原理的教材,看完了雲裡霧裡的,感覺一知半解,我感覺可能是學的教材過於理論化,於是到書店把所有跟編譯原理有關的書籍統統買回家,當然這也包括大家公認的編譯原理三大經典書籍(龍書、虎書、鯨書)在內,每一本我都從頭到尾翻一遍,好像什麼都懂了,又感覺要真的自己動手寫個編譯器仍然是只有大師才能完成,對自己還是可望而不可即的事情。並且作者也了解到許多關於編譯原理實踐的悲觀論調: “現有的編譯器都是用Lex和Yacc構造的,從頭開始手工編寫一個完整的編譯器幾乎是不可能的。”可作者偏偏是那種“明知山有虎,偏向虎山行”的人,要知道早期的編譯器可都是純手工構造的,苦辣酸甜的征程就此開始,可是寫個什麼語言的編譯器?這個編譯器怎么定位?這一切都很茫然。

我開始研究編譯原理書上的樣例,希望能從中找到靈感,給上述問題找到答案。世界著名計算機科學家N.Worth編寫的PL/0語言的編譯程式是作者最先研究的編譯器,它功能簡單、結構清晰、可讀性強,被認為是一個非常合適的小型編譯程式的學習模型,可這個編譯程式不支持數組、結構體、字元串,並且是以假想的棧式機器為例來編寫的,而不是直接生成在某種CPU,某種作業系統環境下直接可以運行的目標語言程式。“PL/0語言的編譯程式”作為編譯器的學習模型,也只能算“矬子裡面拔將軍”,因為沒有更好的,也只好將就著用了。至此,編譯器定位問題算有了些眉目,作者希望構造一個更適合學習的編譯器。可是,另一個問題接踵而至,為什麼那么多開源編譯器不能直接用作編譯器學習模型呢?我開始研究各個開源編譯器的原始碼,其中包括GCC的原始碼,由於GCC支持多個前端語言和各種後端機器平台、AST(Abstract Syntax Tree)和RTL(Register Transfer Language)又成了繞不過去的坎,還沒學會怎么編寫針對一種源語言、一種目標機器的編譯器,就要去學習支持多種源語言多個機器平台的編譯器,就好比一個嬰兒還沒學會走路就要學跑,這注定是要跌跟頭的。

自序自己動手寫編譯器、連結器一面是過於簡化的編譯器學習模型,另一面是過於複雜的開源編譯器,作為學習模型都不太合適。到這裡,編譯器定位問題算是徹底想清楚了,作者要構造一個教大家如何自己動手寫編譯器的學習模型。這個模型包括兩大部分,第一部分是語言定義,第二部分是這個語言編譯器的實現,這個編譯器只支持一種源語言,目標語言也只支持一種。這個語言應該具備目前流行的高級語言的最主要特徵。這個編譯器要結構清晰,代碼量要儘可能少,要能體現編寫一個實用的編譯器的完整過程與技術。這個編譯器可以生成在作業系統中直接運行的exe檔案,只要雙擊或在命令行執行就能看到結果的那種。

接下來作者開始思考另一個問題,編寫個什麼語言的編譯器?作者研究了目前最流行的幾種程式語言C、C++、C#、ObjectiveC、Java,其中C語言是最簡單的了,只有32個關鍵字,但是作者研究發現,C語言還是有許多冗餘的成分,作為學習模型還可以更簡單一些。作者最終以C語言為藍本,進行適當簡化定義了一門新的語言,僅有15個關鍵字,稱為SC語言。目標語言選擇大家熟悉的Intel x86機器語言,編譯器命名為SCC編譯器。

在本書中,讀者將看到從SC語言定義,到SCC編譯器開發的完整過程。讀完本書你將知道一門全新的語言如何定義,一個真實的編譯器如何編寫,這些對你來說將不再神秘,編譯原理講的理論與本書中講述的SC語言定義及SCC編譯器開發過程,是理論聯繫實際在編譯領域的最好闡釋。

如本書作為編譯原理實踐教材,作者建議安排10學時講授。

目錄

第1章引言

1.1HelloWorld編譯過程分析1

1.1.1HelloWorld程式源檔案1

1.1.2詞法分析2

1.1.3語法分析3

1.1.4語義分析3

1.1.5連結器4

1.2SCC編譯器簡介7

1.2.1SCC編譯器架構7

1.2.2SCC編譯器開發環境7

1.2.3SCC編譯器運行環境8

第2章文法知識

2.1語言概述10

2.2形式語言11

2.2.1字母表和符號串11

2.2.2文法與語言的形式定義12

2.2.3文法與語言的類型13

2.2.4程式設計語言描述工具15

2.3詞法分析方法16

2.3.1詞法定義例舉17

2.3.2狀態轉換圖17

2.3.3詞法分析程式流程圖17

2.4語法分析方法18

2.4.1LL分析器18

2.4.2LL(k)文法19

2.4.3LL(1)文法19

2.4.4遞歸子程式法21

2.4.5文法的等價變換24

第3章SC語言定義

3.1SC語言的藍本選擇26

3.1.1K&R C26

3.1.2C8926

3.1.3C9927

3.2SC語言對C89簡化原則27

3.3SC語言的字元集27

3.3.1基本字元集28

3.3.2擴展字元集28

3.4SC語言詞法定義29

3.4.1關鍵字29

3.4.2標識符30

3.4.3整數常量31

3.4.4字元常量31

3.4.5字元串常量32

3.4.6運算符及分隔設定32

3.4.7注釋33

3.5SC語言語法定義33

3.5.1外部定義33

3.5.2語句35

3.5.3表達式39

3.6SC語言與C語言功能對比46

3.6.1關鍵字46

3.6.2數據類型46

3.6.3存儲類型47

3.6.4常量47

3.6.5變數47

3.6.6函式48

3.6.7語句48

3.6.8表達式50

第4章SC語言詞法分析

4.1詞法分析任務的官方說法52

4.2單詞編碼53

4.3詞法分析用到的數據結構55

4.3.1動態字元串56

4.3.2動態數組58

4.3.3哈希表61

4.3.4單詞表62

4.4錯誤處理,未雨綢繆67

4.5詞法分析過程72

4.5.1詞法分析主程式72

4.5.2預處理76

4.5.3解析標識符79

4.5.4解析整數80

4.5.5解析字元串80

4.5.6詞法分析流程圖82

4.6詞法著色84

4.7控制程式85

4.8詞法分析成果展示86

第5章SC語言語法分析

5.1外部定義87

5.1.1翻譯單元87

5.1.2外部聲明88

5.1.3類型區分符90

5.1.4結構區分符92

5.1.5函式調用約定95

5.1.6結構成員對齊95

5.1.7聲明符96

5.1.8初值符100

5.2語句101

5.2.1複合語句102

5.2.2表達式語句103

5.2.3選擇語句104

5.2.4循環語句104

5.2.5跳轉語句105

5.3表達式107

5.3.1賦值表達式108

5.3.2相等類表達式109

5.3.3關係表達式109

5.3.4加減類表達式110

5.3.5乘除類表達式111

5.3.6一元表達式112

5.3.7後綴表達式113

5.3.8初值表達式114

5.4語法縮進116

5.4.1用到的全局變數及枚舉116

5.4.2語法縮進程式117

5.5總控程式118

5.6成果展示119

第6章符號表

6.1符號表簡介121

6.1.1收集符號屬性121

6.1.2語義的合法性檢查122

6.2符號表用到的主要數據結構123

6.2.1棧結構123

6.2.2符號表結構127

6.2.3數據類型結構132

6.2.4存儲類型133

6.3符號表的構造過程134

6.3.1外部聲明134

6.3.2類型區分符137

6.3.3結構區分符138

6.3.4聲明符144

6.3.5變數初始化149

6.3.6複合語句150

6.3.7sizeof表達式150

6.3.8初等表達式152

6.4控制程式153

6.5成果展示155

第7章生成COFF目標檔案

7.1COFF檔案結構157

7.1.1基本概念157

7.1.2總體結構158

7.1.3COFF檔案頭158

7.1.4節頭表161

7.1.5代碼節內容168

7.1.6數據節與導入節內容168

7.1.7COFF符號表169

7.1.8COFF字元串表173

7.1.9COFF重定位信息173

7.2生成COFF目標檔案175

7.2.1生成節表176

7.2.2生成符號表178

7.2.3生成重定位信息182

7.2.4生成目標檔案183

7.3成果展示185

第8章x86機器語言

8.1x86機器語言簡介187

8.2通用指令格式188

8.2.1指令前綴188

8.2.2操作碼190

8.2.3ModR/M位元組190

8.2.4SIB位元組191

8.2.5偏移量與立即數193

8.3x86暫存器193

8.3.1數據暫存器193

8.3.2變址暫存器193

8.3.3指針暫存器194

8.3.4段暫存器194

8.3.5指令指針暫存器194

8.3.6標誌暫存器195

8.4指令參考196

8.4.1符號說明196

8.4.2數據傳送指令198

8.4.3算術運算指令200

8.4.4邏輯運算指令203

8.4.5控制轉移指令205

8.4.6串操作指令208

8.4.7處理器控制指令208

8.5生成x86機器語言208

8.5.1運算元棧209

8.5.2生成通用指令210

8.5.3生成數據傳送指令213

8.5.4生成算術與邏輯運算指令217

8.5.5生成控制轉移指令221

8.5.6暫存器使用224

8.5.7本章用到的全局變數227

8.6成果展示227

第9章SCC語義分析

9.1外部定義229

9.1.1聲明與函式定義229

9.1.2初值符232

9.1.3函式體234

9.2語句237

9.2.1表達式語句237

9.2.2選擇語句 238

9.2.3循環語句 239

9.2.4跳轉語句241

9.3表達式 244

9.3.1賦值表達式244

9.3.2相等類表達式245

9.3.3關係表達式246

9.3.4加減類表達248

9.3.5乘除類表達式249

9.3.6一元表達式250

9.3.7後綴表達式253

9.3.8初值表達式257

9.4成果展示259

第10章連結器

10.1連結方式與庫檔案261

10.2PE檔案格式263

10.2.1總體結構263

10.2.2DOS部分264

10.2.3NT頭265

10.2.4節頭表272

10.2.5代碼節272

10.2.6數據節274

10.2.7導入節274

10.3連結器代碼實現278

10.3.1生成PE檔案頭278

10.3.2載入目標檔案281

10.3.3載入引入庫檔案282

10.3.4解析外部符號285

10.3.5計算節區的RVA地址288

10.3.6重定位符號地址291

10.3.7修正需要重定位的地址292

10.3.8寫PE檔案293

10.3.9生成EXE檔案295

10.4SCC編譯器、連結器總控程式297

10.5成果展示301

10.6全書代碼架構302

第11章SC語言程式開發

11.1SC語言程式開發流程304

11.2SCC編譯器測試程式304

11.2.1表達式測試304

11.2.2語句測試308

11.2.3結構體測試310

11.2.4函式參數傳遞測試312

11.2.5字元串測試314

11.2.6全局變數測試315

11.3語言舉例316

11.3.1可接收命令行參數的控制台程式316

11.3.2可接收命令行參數的Win32應用程式317

11.3.3HelloWindows視窗程式318

11.3.4檔案複製程式323

11.3.5九九乘法表325

11.3.6列印菱形326

11.3.7螢幕捕捉程式328

參考文獻

附錄ASC語言文法定義中英文對照表

相關詞條

熱門詞條

聯絡我們