自己動手構造編譯系統：編譯、彙編與連結

“自己動手系列”

自己動手構造編譯系統

編譯、彙編與連結

範志東  張瓊聲  著

圖書在版編目（cip）資料

自己動手構造編譯系統：編譯、彙編與連結 / 範志東，張瓊聲著. —北京：機械工業出版社，2016.7

（自己動手系列）

isbn 978-7-111-54355-8

i. 自…　ii. ①範… ②張…　iii. 編譯器　iv. tp314

中國版本圖書館cip資料核字（2016）第163077号

自己動手構造編譯系統：編譯、彙編與連結

出版發行：機械工業出版社（北京市西城區百萬莊大街22号　郵政編碼：100037）

責任編輯： 佘　潔 責任校對：董紀麗

印　　刷： 版　　次：2016年8月第1版第1次印刷

開　　本：186mm×240mm　1/16 印　　張：19

書　　号：isbn 978-7-111-54355-8 定　　價：69.00元

凡購本書，如有缺頁、倒頁、脫頁，由本社發行部調換

客服熱線：[phone]　88361066 投稿熱線：[phone]

購書熱線：[phone]　88379649　68995259 讀者信箱：[email protected]

版權所有  " 侵權必究

封底無防僞标均為盜版

本書法律顧問：北京大成律師事務所　韓光/鄒曉東

foreword序

小範從大學畢業設計開始寫編譯器的實作代碼，為他選擇這個題目的初衷是希望把編譯系統與作業系統、計算機體系結構相關的結合點找出來、弄清楚，為教學提供可用的執行個體。大學畢業設計結束時小範完成了一個最簡單的c語言子集的編譯器，生成的彙程式設計式經過彙編和連結後可以正确執行。研究所學生期間我們決定繼續編譯系統實作技術方向的研究工作，主要完成彙編器和連結器這兩大子產品。小範用一顆好奇、求知的心指引自己，利用一切可以搜集到的資料，用“日拱一卒”的勁頭一步一步接近目标。每天的日子都可能有不同的“幹擾”——名企的實習、發論文、做項目、參加競賽、考認證，身邊的同學在快速積攢各種經曆和成果的時候，小範要保持内心的平靜，專注于工作量巨大而是否有回報還未曾可知的事情。三年的時間裡，沒有獎學金，沒有項目經費，有的是沒完沒了的各種問題，各種要看的書、資料和要完成的代碼，同時還要關注大資料平台、程式設計語言等新技術的發展。

“彙編器完成了”“連結器完成了”，好消息接踵而至。小範說，“把編譯器的代碼重寫一下，加上代碼優化吧？”我說“好”，其實，這個“好”說起來容易，而小範那裡增加的工作量可想而知，這絕不是那麼輕松的事情。優化的基本原理有了，怎麼設計算法來實作呢？整個編譯器的文法比大學畢業設計時擴充了很多。編譯器重寫、增加代碼優化子產品、完成彙編器和連結器，難度和工作量可想而知。每當小範解決一個問題，完成一個功能，就會非常開心地與我分享。看小範完成的一行行規範、漂亮的代碼，聽他興奮地講解，很難說與聽郎朗的鋼琴協奏曲《黃河之子》、德沃夏克的《自新大陸》比哪一個更令人陶醉，與聽交響曲《嘎達梅林》比哪一個更令人震撼。當小範完成連結器後，我說：“小範，寫書吧，不寫下來太可惜了。”就這樣，小範再次如一輛嶄新的裝甲車，轟隆前行，踏上了筆耕不辍的征程。2015年暑假，細讀和修改這部30多萬字的書稿，感慨萬千，完成編譯系統的工作量、四年的甘苦與共、超然物外的孤獨都在這字裡行間跳躍。寫完這部原創書對一個年輕學生來說是極富挑戰的，但是他完成了，而且完成得如此精緻、用心。

小範來自安徽的農村，面對生活中的各種困惑、困難，他很少有沮喪、悲觀的情緒，永遠有天然的好奇心，保留着頑童的天真、快樂與坦率。他開始寫本書時23歲，完成全書的初稿時25歲。寫編譯系統和作業系統核心并非難以企及，隻是需要一份淡然、專注和堅持。

如果你想了解計算機是如何工作的，為什麼程式會出現不可思議的錯誤？進階語言程式是如何被翻譯成機器語言代碼的？編譯器在程式的優化方面能做哪些工作？軟體和硬體是怎麼結合工作的？各種複雜的資料結構和算法，包括圖論在實作編譯系統時如何應用？有限自動機在詞法分析中的作用是什麼？其程式又如何實作？那麼本書可以滿足你的好奇心和求知欲。如何實作編譯系統？如何實作編譯器？如何實作彙編器？如何使用符号表？如何結合作業系統加載器的需要實作連結器？intel的指令是如何構成的？如何實作不同的編譯優化算法？對這些問題，本書結合作者實作的代碼執行個體進行了詳盡的闡述，對提高程式員的專業素質有實際的助益，同時本書也可以作為計算機科學相關專業教師的參考書和編譯原理實習類課程的教材。

2013年在新疆參加全國作業系統群組成原理教學研讨會時，我帶着列印出來的兩章書稿給了機械工業出版社的溫莉芳老師，與她探讨這本書出版的意義和可行性，她給了我們很大的鼓勵和支援，促成了本書的完成。在此，特别感謝溫莉芳老師。

本書的責任編輯佘潔老師與作者反複溝通，對本書進行了認真、耐心的編輯，感謝她的辛勤付出。

中國石油大學（華東）的李村合老師在編譯器設計的初期給予了我們指導和建議。馬力老師在繁忙的工作之餘，認真審閱書稿，給出了詳細的修改意見。王小雲、程堅、梁紅衛、葛永文老師對本書提出了他們的意見，并給出了認真的評價。趙國梁同學對書中的代碼和文字做了細心的校對。在此，對他們表示衷心的感謝。最後要感謝小範勤勞、堅韌的爸爸媽媽，是他們一直給予他無私的支援和持續的鼓勵。

感恩所有給予我們幫助和鼓勵的老師、同學和朋友！

張瓊聲

2016年春于北京

preface前　　言

本書适合誰讀

本書是一本描述編譯系統實作的書籍。這裡使用“編譯系統”一詞，主要是為了與市面上描述編譯器實作的書籍進行區分。本書描述的編譯系統不僅包含編譯器的實作，還包括彙編器、連結器的實作，以及機器指令與可執行檔案格式的知識。是以，本書使用“編譯系統”一詞作為編譯器、彙編器和連結器的統稱。

本書的目的是希望讀者能通過閱讀本書清晰地認識編譯系統的工作流程，并能自己嘗試構造一個完整的編譯系統。為了使讀者更容易了解和學習編譯系統的構造方法，本書将描述的重點放在編譯系統的關鍵流程上，并對工業化編譯系統的實作做了适當的簡化。如果讀者對編譯系統實作的内幕感興趣，或者想自己動手實作一個編譯系統的話，本書将非常适合你閱讀。

閱讀本書，你會發現書中的内容與傳統的編譯原理教材以及描述編譯器實作的書籍有所不同。本書除了描述一個編譯器的具體實作外，還描述了一般書籍較少涉及的彙編器和連結器的具體實作。而且本書并非“紙上談兵”，在講述每個功能子產品時，書中都會結合具體實作代碼來闡述子產品功能的實作。通過本書讀者将會學習如何使用有限自動機構造詞法分析器，如何将文法分析算法應用到文法分析過程，如何使用資料流分析進行中間代碼的優化，如何生成合法的彙編代碼，如何産生二進制指令資訊，如何在連結器内進行符号解析和重定位，如何生成目标檔案和可執行檔案等。

本書的宗旨是為意欲了解或親自實作編譯系統的讀者提供指導和幫助。尤其是計算機專業的讀者，通過自己動手寫出一個編譯系統，能加強讀者對計算機系統從軟體層次到硬體層次的了解。同時，深入挖掘技術幕後的秘密也是對專業興趣的一種良好培養。gcc本身是一套非常完善的工業化編譯系統（雖然我們習慣上稱它為編譯器），然而單憑個人之力無法做到像gcc這樣完善，而且很多時候是沒有必要做出一個工程化的編譯器的。本書試圖幫助讀者深入了解編譯的過程，并能按照書中的指導實作一個能正常工作的編譯器。在自己親自動手實作一個編譯系統的過程中，讀者獲得的不僅僅是軟體開發的經曆。在開發編譯系統的過程中，讀者還會學習很多與底層相關的知識，而這些知識在一般的專業教材中很少涉及。

如果讀者想了解計算機程式底層工作的奧秘，本書能夠解答你内心的疑惑。如果讀者想自定義一種進階語言，并希望使該語言的程式在計算機上正常運作，本書能幫助你較快地達到目的。如果讀者想從實作一個編譯器的過程中，加強對編譯系統工作流程的了解，并嘗試深入研究gcc源碼，本書也能為你提供很多有價值的參考。

基礎知識儲備

本書盡可能地不要求讀者有太多的基礎知識準備，但是編譯理論屬于計算機學科比較深層次的知識領域，難免對讀者的知識儲備有所要求。本書的編譯系統是基于linux x86平台實作的，是以要求讀者對linux環境的c/c++程式設計有所了解。另外，了解彙編器的實作内容需要讀者對x86的彙編指令程式設計比較熟悉。本書不會描述過多編譯原理教材中涉及的内容，是以要求讀者具備編譯原理的基礎知識。不過讀者不必過于擔心，本書會按照循序漸進的方式描述編譯系統的實作，在具體的章節中會将編譯系統實作的每個細節以及所需的知識闡述清楚。

本書内容組織

本書共7章，各章的主要内容分别如下。

第1章代碼背後

從程式設計開始，追溯代碼背後的細節，引出編譯系統的概念。

第2章編譯系統設計

按照編譯系統的工作流程，介紹本書編譯系統的設計結構。

第3章編譯器構造

描述如何使用有限自動機識别自定義進階語言的詞法記号，如何使用文法分析算法識别程式的文法子產品，如何對進階語言上下文相關資訊進行語義合法性檢查，如何使用文法制導翻譯進行代碼生成，以及編譯器工作時符号資訊的管理等。

第4章編譯優化

介紹中間代碼的設計和生成，如何利用資料流分析實作中間代碼優化，如何對變量進行寄存器配置設定，目标代碼生成階段如何使用窺孔優化器對目标代碼進行優化。

第5章二進制表示

描述intel x86指令的基本格式，并将at&t彙編與intel彙編進行對比。描述elf檔案的基本格式，介紹elf檔案的組織和操作方法。

第6章彙編器構造

描述彙編器詞法分析和文法分析的實作，介紹彙編器如何提取目标檔案的主要表資訊，并描述x86二進制指令的輸出方法。

第7章連結器構造

介紹如何為可重定位目标檔案的段進行位址空間配置設定，描述連結器符号解析的流程，以及符号位址的計算方法，并介紹重定位在連結器中的實作。

随書源碼

本書實作的編譯系統代碼已經托管到github，源碼可以使用gcc 5.2.0編譯通過。代碼的github位址是https://github.com/fanzhidongyzby/cit。代碼分支x86實作了基于intel x86體系結構的編譯器、彙編器和連結器，編譯系統生成的目标檔案和可執行檔案都是linux下标準的elf檔案格式。代碼分支arm實作了基于arm體系結構的編譯器，目前支援生成arm 7的彙編代碼。

目　　錄?contents

序

前言

第1章?代碼背後 1

1.1?從程式設計聊起 1

1.2?曆史淵源 2

1.3?gcc的工作流程 3

1.3.1?預編譯 4

1.3.2?編譯 5

1.3.3?彙編 6

1.3.4?連結 7

1.4?設計自己的編譯系統 8

1.5?本章小結 9

第2章?編譯系統設計 11

2.1?編譯程式的設計 11

2.1.1?詞法分析 12

2.1.2?文法分析 13

2.1.3?符号表管理 14

2.1.4?語義分析 15

2.1.5?代碼生成 16

2.1.6?編譯優化 16

2.2?x86指令格式 18

2.3?elf檔案格式 19

2.4?彙程式設計式的設計 21

2.4.1?彙編詞法、文法分析 22

2.4.2?表資訊生成 23

2.4.3?指令生成 24

2.5?連結程式的設計 25

2.5.1?位址空間配置設定 25

2.5.2?符号解析 26

2.5.3?重定位 27

2.6?本章小結 27

第3章?編譯器構造 29

3.1?詞法分析 29

3.1.1?掃描器 30

3.1.2?詞法記号 32

3.1.3?有限自動機 36

3.1.4?解析器 40

3.1.5?錯誤處理 53

3.2?文法分析 55

3.2.1?文法定義 55

3.2.2?遞歸下降子程式 65

3.2.3?錯誤處理 70

3.3?符号表管理 74

3.3.1?符号表資料結構 75

3.3.2?作用域管理 78

3.3.3?變量管理 82

3.3.4?函數管理 88

3.4?語義分析 93

3.4.1?聲明與定義語義檢查 93

3.4.2?表達式語義檢查 95

3.4.3?語句語義檢查 97

3.4.4?錯誤處理 98

3.5?代碼生成 101

3.5.1?中間代碼設計 102

3.5.2?程式運作時存儲 105

3.5.3?函數定義與return語句翻譯 108

3.5.4?表達式翻譯 110

3.5.5?複合語句與break、continue

???語句翻譯 120

3.5.6?目标代碼生成 132

3.5.7?資料段生成 141

3.6?本章小結 145

第4章?編譯優化 147

4.1?資料流分析 149

4.1.1?流圖 149

4.1.2?資料流分析架構 152

4.2?中間代碼優化 155

4.2.1?常量傳播 155

4.2.2?複寫傳播 167

4.2.3?死代碼消除 172

4.3?寄存器配置設定 177

4.3.1?圖着色算法 177

4.3.2?變量棧幀偏移計算 182

4.4?窺孔優化 187

4.5?本章小結 190

第5章?二進制表示 191

5.1?x86指令 191

5.1.1?指令字首 192

5.1.2?操作碼 194

5.1.3?modr/m字段 196

5.1.4?sib字段 198

5.1.5?偏移 201

5.1.6?立即數 201

5.1.7?at&t彙編格式 202

5.2?elf檔案 204

5.2.1?檔案頭 205

5.2.2?段表 207

5.2.3?程式頭表 209

5.2.4?符号表 213

5.2.5?重定位表 214

5.2.6?串表 215

5.3?本章小結 217

第6章?彙編器構造 219

6.1?詞法分析 220

6.1.1?詞法記号 220

6.1.2?有限自動機 222

6.2?文法分析 223

6.2.1?彙編語言程式 223

6.2.2?資料定義 225

6.2.3?指令 226

6.3?符号表管理 227

6.3.1?資料結構 228

6.3.2?符号管理 230

6.4?表資訊生成 234

6.4.1?段表資訊 235

6.4.2?符号表資訊 238

6.4.3?重定位表資訊 239

6.5?指令生成 246

6.5.1?雙操作數指令 247

6.5.2?單操作數指令 251

6.5.3?零操作數指令 254

6.6?目标檔案生成 255

6.7?本章小結 261

第7章?連結器構造 263

7.1?資訊收集 264

7.1.1?目标檔案資訊 264

7.1.2?段資料資訊 266

7.1.3?符号引用資訊 268

7.2?位址空間配置設定 269

7.3?符号解析 272

7.3.1?符号引用驗證 274

7.3.2?符号位址解析 276

7.4?重定位 277

7.5?程式入口點與運作時庫 281

7.6?可執行檔案生成 283

7.7?本章小結 290

參考文獻   291

第1章 

　　代碼背後

　

知其然，并知其是以然。

——《朱子語類》

1.1  從程式設計聊起

　　說起程式設計，如果有人問我們敲進計算機的第一段代碼是什麼，相信很多人會說出同一個答案——“hello world !”。程式設計語言的教材一般都會把這段代碼作為書中的第一個例子呈現給讀者。當我們按照課本或者老師的要求把它輸入到開發環境，然後單擊“編譯”和“運作”按鈕，映入眼簾的那行字元串定會令人欣喜不已！然而激動過後，一股強烈的好奇心可能會驅使我們去弄清一個新的概念——編譯是什麼？

　　遺憾的是，一般教授程式設計語言的老師不會介紹太多關于它的内容，最多會告訴我們：代碼隻有經過編譯，才能在計算機中正确執行。随着知識和經驗的不斷積累，我們逐漸了解到當初單擊“編譯”按鈕的時候，計算機在幕後做了一系列的工作。它先對源代碼進行編譯，生成二進制目标檔案，然後對目标檔案進行連結，最後生成一個可執行檔案。即便如此，我們對編譯的流程也隻有一個模糊的認識。

　　直到學習了編譯原理，才發現編譯器原來就是語言翻譯程式，它把進階語言程式翻譯成低級彙編語言程式。而彙編語言程式是不能被計算機直接識别的，必須靠彙編器把它翻譯為計算機硬體可識别的機器語言程式。而根據之前對目标檔案和連結器的了解，我們可能猜測到機器語言應該是按照二進制的形式存儲在目标檔案内部的。可是目标檔案到底包含什麼，連結後的可執行檔案裡又有什麼？問題貌似越來越多。

　　圖1-1展示了編譯的大緻工作流程，相信擁有一定程式設計經驗的人，對該圖所表達的含義并不陌生。為了讓源代碼能正常地運作在計算機上，計算機對代碼進行了“繁複”的處理。可是，編譯器既然是語言翻譯程式，為什麼不把源代碼直接翻譯成機器語言，卻還要經過彙編和連結的過程呢？

圖1-1  編譯的流程

　　似乎我們解決了一些疑惑後，總是會有更多的疑惑接踵而來。但也正是這些層出不窮的疑惑，促使我們不斷地探究簡單問題背後的複雜機制。當挖掘出這些表象下覆寫的問題本質時，可能比首次敲出“hello world!”程式時還要喜悅。在後面的章節中，将會逐漸探讨編譯背後的本質，将謎團一一揭開，最終讀者自己可動手構造出本書所實作的編譯系統——編譯器、彙編器與連結器，真正做到“知其然，并知其是以然”。

1.2  曆史淵源

　　曆史上很多新鮮事物的出現都不是偶然的，計算機學科的技術和知識如此，編譯系統也不例外，它的産生來源于程式設計工作的需求。程式設計本質上是人與計算機交流，人們使用計算機解決問題，必須把問題轉化為計算機所能了解的方式。當問題規模逐漸增大時，程式設計的勞動量自然會變得繁重。編譯系統的出現在一定程度上降低了程式設計的難度和複雜度。

　　在計算機剛剛誕生的年代，人們隻能通過二進制機器指令指揮計算機工作，計算機程式是依靠人工撥動計算機控制台上的開關被輸入到計算機内部的。後來人們想到使用穿孔卡片來代替原始的開關輸入，用卡片上穿孔的有無表示計算機世界的“0”和“1”，讓計算機自動讀取穿孔卡片實作程式的錄入，這裡錄入的指令就是常說的二進制代碼。然而這種程式設計工作在現在看起來簡直就是一個“噩夢”，因為一旦穿孔卡片的制作出現錯誤，所有的工作都要重新來過。

　　人們很快就發現了使用二進制代碼控制計算機的不足，因為人工輸入二進制指令的錯誤率實在太高了。為了解決這個問題，人們用一系列簡單明了的助記符代替計算機的二進制指令，即我們熟知的彙編語言。可是計算機隻能識别二進制指令，是以需要一個已有的程式自動完成彙編語言到二進制指令的翻譯工作，于是彙編器就産生了。程式員隻需要寫出彙編代碼，然後交給彙編器進行翻譯，生成二進制代碼。是以，彙編器将程式員從煩瑣的二進制代碼中解脫出來。

　　使用彙編器提高了程式設計的效率，使得人們有能力處理更複雜的計算問題。随着計算問題複雜度的提高，程式設計中出現了大量的重複代碼。人們不願意進行重複的勞動，于是就想辦法将公共的代碼提取出來，彙編成獨立的子產品存儲在目标檔案中，甚至将同一類的目标檔案打包成庫。由于原本寫在同一個檔案内的代碼被分割到多個檔案中，那麼最終還需要将這些分離的檔案拼裝起來形成完整的可執行代碼。但是事情并沒有那麼簡單，由于檔案的子產品化分割，檔案間的符号可能會互相引用。人們需要處理這些引用關系，重新計算符号的引用位址，這就是連結器的基本功能。連結器使得計算機能自動把不同的檔案子產品準确無誤地拼接起來，使得代碼的複用成為可能。

　　圖1-2描述的連結方式稱為靜态連結，但這種方式也有不足之處。靜态連結器把公用庫内的目标檔案合并到可執行檔案内部，使得可執行檔案的體積變得龐大。這樣做會導緻可執行檔案版本難以更新，也導緻了多個程式加載後相同的公用庫代碼占用了多份記憶體空間。為了解決上述的問題，現代編譯系統都引入了動态連結方式（見圖1-3）。動态連結器不會把公用庫内的目标檔案合并到可執行檔案内，而僅僅記錄動态連結庫的路徑資訊。它允許程式運作前才加載所需的動态連結庫，如果該動态連結庫已加載到記憶體，則不需要重複加載。另外，動态連結器也允許将動态連結庫的加載延遲到程式執行庫函數調用的那一刻。這樣做，不僅節約了磁盤和記憶體空間，還友善了可執行檔案版本的更新。如果應用程式子產品設計合理的話，程式更新時隻需要更新子產品對應的動态連結庫即可。當然，動态連結的方式也有缺點。運作時連結的方式會增加程式執行的時間開銷。另外，動态連結庫的版本錯誤可能會導緻程式無法執行。由于靜态連結和動态連結的基本原理類似，且動态連結器的實作相對複雜，是以本書編譯系統所實作的連結器采用靜态連結的方式。

               圖1-2  靜态連結 圖1-3  動态連結

　　彙編器和連結器的出現大大提高了程式設計效率，降低了程式設計和維護的難度。但是人們對彙編語言的能力并不滿足，有人設想要是能像寫數學公式那樣對計算機程式設計就太友善了，于是就出現了如今形形色色的進階程式設計語言。這樣就面臨與當初彙編器産生時同樣的問題——如何将進階語言翻譯為彙編語言，這正是編譯器所做的工作。編譯器比彙編器複雜得多。彙編語言的文法比較單一，它與機器語言有基本的對應關系。而進階語言形式比較自由，計算機識别進階語言的含義比較困難，而且它的語句翻譯為彙編語言序列時有多種選擇，如何選擇更好的序列作為翻譯結果也是比較困難的，不過最終這些問題都得以解決。進階語言編譯器的出現，實作了人們使用簡潔易懂的程式設計語言與計算機交流的目的。

1.3  gcc的工作流程

　　在着手構造編譯系統之前，需要先介紹編譯系統應該做的事情，而最具參考價值的資料就是主流編譯器的實作。gnu的gcc編譯器是工業化編譯器的代表，是以我們先了解gcc都在做什麼。

　　我們寫一個最簡單的“helloworld”程式，代碼存儲在源檔案hello.c中，源檔案内容如下：

#include<stdio.h>

int main()

{

     printf("hello world!");

     return 0;

}

　　如果将hello.c編譯并靜态連結為可執行檔案，使用如下gcc指令直接編譯即可：

$gcc hello.c –o hello -static

　　hello即編譯後的可執行檔案。

　　如果檢視gcc背後的工作流程，可以使用--verbose選項。

$gcc hello.c –o hello –static --verbose

　　輸出的資訊如下：

$cc1 -quiet hello.c -o hello.s

$as -o hello.o hello.s

$collect2 -static -o hello \

     crt1.o crti.o crtbegint.o hello.o \

     --start-group libgcc.a libgcc_eh.a libc.a --end-group \

     crtend.o crtn.o

　　為了保持輸出資訊的簡潔，這裡對輸出資訊進行了整理。可以看出，gcc編譯背後使用了cc1、as、collect2三個指令。其中cc1是gcc的編譯器，它将源檔案hello.c編譯為hello.s。as是彙編器指令，它将hello.s彙編為hello.o目标檔案。collect2是連結器指令，它是對指令ld的封裝。靜态連結時，gcc将c語言運作時庫（crt）内的5個重要的目标檔案crt1.o、crti.o、crtbegint.o、crtend.o、crtn.o以及3個靜态庫libgcc.a、libgcc_eh.a、libc.a連結到可執行檔案hello。此外，cc1在對源檔案編譯之前，還有預編譯的過程。

　　是以，我們從預編譯、編譯、彙編和連結四個階段檢視gcc的工作細節。

1.3.1  預編譯

　　gcc對源檔案的第一階段的處理是預編譯，主要是處理宏定義和檔案包含等資訊。指令格式如下： 

$gcc –e hello.c –o hello.i

　　預編譯器将hello.c處理後輸出到檔案hello.i，hello.i檔案内容如下：

# 1 "hello.c"

# 1 "<built-in>"

# 1 "<command-line>"

……

extern int printf (const char *__restrict __format, ...);

…… 

　　比如檔案包含語句#include<stdio.h>，預編譯器會将stdio.h的檔案内容拷貝到#include語句聲明的位置。如果源檔案内使用#define語句定義了宏，預編譯器則将該宏的内容替換到其被引用的位置。如果宏定義本身使用了其他宏，則預編譯器需要将宏遞歸地展開。

　　我們可以将預編譯的工作簡單地了解為源碼的文本替換，即将宏定義的内容替換到宏的引用位置。當然，這樣了解有一定的片面性，因為要考慮宏定義中使用其他宏的情況。事實上預編譯器的實作機制和編譯器有着很大的相似性，是以本書描述的編譯系統将重點放在源代碼的編譯上，不再獨立實作預編譯器。然而，我們需要清楚的事實是：一個完善的編譯器是需要預編譯器的。

1.3.2  編譯

　　接下來gcc對hello.i進行編譯，指令如下：

$gcc –s hello.i –o hello.s

　　編譯後産生的彙編檔案hello.s内容如下：

     .file "hello.c"

     .section .rodata

.lc0:

     .string "hello world!"

     .text

.globl main

     .type main, @function

main:

     pushl %ebp

     movl %esp, %ebp

     andl $-16, %esp

     subl $16, %esp

     movl $.lc0, %eax

     movl %eax, (%esp)

     call printf

     movl $0, %eax

     leave

     ret

     .size main, .-main

     .ident "gcc: (ubuntu/linaro 4.4.4-14ubuntu5) 4.4.5"

     .section .note.gnu-stack,"",@progbits

　　gcc生成的彙編代碼的文法是at&t格式，與intel格式的彙編有所不同（若要生成intel格式的彙編代碼，使用編譯選項“-masm=intel”即可）。比如立即數用“$”字首，寄存器用“%”字首，記憶體尋址使用小括号等。差別最大的是，at&t彙編指令的源操作數在前，目标操作數在後，這與intel彙編文法正好相反。本書會在後續章節中較長的描述這兩種彙編文法格式的差別。

　　不過我們仍能從中發現進階語言代碼中傳遞過來的資訊，比如字元串“hello world!”、主函數名稱main、函數調用call printf等。

1.3.3  彙編

　　接着，gcc使用彙編器對hello.s進行彙編，指令如下：

$gcc –c hello.s –o hello.o

　　生成的目标檔案hello.o，linux下稱之為可重定位目标檔案。目标檔案無法使用文本編輯器直接檢視，但是我們可以使用gcc自帶的工具objdump指令分析它的内容，指令格式如下：

$objdump –sd hello.o 

　　輸出目标檔案的主要段的内容與反彙編代碼如下：

　　

hello.o:     file format elf32-i386

contents of section .text:

 0000  5589e583  e4f083ec  10b80000  00008904  u...............

 0010  24e8fcff  ffffb800  000000c9  c3         $............   

contents of section .rodata:

 0000  48656c6c  6f20576f  726c6421  00         hello world!.   

contents of section .comment:

 0000  00474343  3a202855  62756e74  752f4c69  .gcc: (ubuntu/li

 0010  6e61726f  20342e34  2e342d31  34756275  naro 4.4.4-14ubu

 0020  6e747535  2920342e  342e3500              ntu5) 4.4.5.    

disassembly of section .text:

00000000 <main>:

    0: 55                   push %ebp

    1: 89 e5                 mov %esp,%ebp

    3: 83 e4 f0             and $0xfffffff0,%esp

    6: 83 ec 10             sub $0x10,%esp

    9: b8 00 00 00 00       mov $0x0,%eax

    e: 89 04 24             mov %eax,(%esp)

   11: e8 fc ff ff ff       call 12 <main+0x12>

   16: b8 00 00 00 00         mov $0x0,%eax

   1b: c9                     leave  

   1c: c3                   ret    

　　從資料段二進制資訊的ascii形式的顯示中，我們看到了彙編語言内定義的字元串資料“hello world !”。代碼段的資訊和彙編檔案代碼資訊基本吻合，但是我們發現了很多不同之處。比如彙編檔案内的指令“movl $.lc0, %eax”中的符号.lc0的位址（字元串“hello world !”的位址）被換成了0。指令“call printf ”内符号printf的相對位址被換成了0xfffffffc，即call指令操作數部分的起始位址。

　　這些差別本質來源于彙編語言符号的引用問題。由于彙編器在處理目前檔案的過程中無法獲悉符号的虛拟位址，是以臨時将這些符号位址設定為預設值0，真正的符号位址隻有在連結的時候才能确定。

1.3.4  連結

　　使用gcc指令進行目标檔案連結很簡單：

gcc hello.o –o hello

　　gcc預設使用動态連結，如果要進行靜态連結，需加上-static選項：

gcc hello.o –o hello –static

　　這樣生成的可執行檔案hello便能正常執行了。

　　我們使用objdump指令檢視一下靜态連結後的可執行檔案内的資訊。由于可執行檔案中包含了大量的c語言庫檔案，是以這裡不便将檔案的所有資訊展示出來，僅顯示最終main函數的可執行代碼。

080482c0 <main>:

 80482c0: 55                   push %ebp

 80482c1: 89 e5                 mov %esp,%ebp

 80482c3: 83 e4 f0             and $0xfffffff0,%esp

 80482c6: 83 ec 10             sub $0x10,%esp

 80482c9: b8 28 e8 0a 08       mov $0x80ae828,%eax

 80482ce: 89 04 24             mov %eax,(%esp)

 80482d1: e8 fa 0a 00 00     call 8048dd0 <_io_printf>

 80482d6: b8 00 00 00 00     mov $0x0,%eax

 80482db: c9                   leave  

 80482dc: c3                   ret

　　從main函數的可執行代碼中，我們發現彙編過程中描述的無法确定的符号位址資訊在這裡都被修正為實際的符号位址。如“hello world !”字元串的位址為0x080ae828，printf函數的位址為0x08048dd0。這裡符号_io_printf與printf完全等價，call指令内部相對位址為0x000afa，正好是printf位址相對于call指令下條指令起始位址0x080482d6的偏移。

1.4  設計自己的編譯系統

　　根據以上描述，我們意欲構造一個能将進階語言轉化為可執行檔案的編譯系統。進階語言文法由我們自己定義，它可以是c語言文法，也可以是它的一個子集，但是無論如何，該進階語言由我們根據程式設計需要自行設計。另外，我們要求生成的可執行檔案能正常執行，無論它是linux系統的elf可執行檔案，還是windows系統的pe檔案，而本書選擇生成linux系統的elf可執行檔案。正如本章開始所描述的，我們要做的就是：自己動手完成當初單擊“編譯”按鈕時計算機在背後做的事情。

　　然而在真正開工之前，我們需要承認一個事實——我們是無法實作一個像gcc那樣完善的工業化編譯器的。是以必須降低編譯系統實作的複雜度，確定實際的工作在可控的範圍内。本書對編譯系統的實作做了如下修改和限制： 

　　1）預編譯的處理。如前所述，預編譯作為編譯前期的工作，其主要的内容在于宏指令的展開和文本替換。本質上，預編譯器也需要識别源代碼語義，它與編譯器實作的内容十分相似。通過後面章節對編譯器實作原理的介紹，我們也能學會如何構造一個簡單的預編譯器。是以，在進階語言的文法設計中，本書未提供與預編譯處理相關的文法，而是直接對源代碼進行編譯，這樣使得我們的精力更關注于編譯器的實作細節上。

　　2）一遍編譯的方式。編譯器的設計中可以對編譯器的每個子產品獨立設計，比如詞法分析器、文法分析器、中間代碼優化器等。這樣做可能需要對源代碼進行多遍的掃描，雖然編譯效率相對較低，但是獲得的源碼語義資訊更完善。我們設計的編譯系統目标非常直接——保證編譯系統輸出正确的可執行檔案即可，是以采用一遍編譯的方式會更高效。

　　3）進階語言文法。為了友善大多數讀者對文法分析的了解，我們參考c語言的文法格式設計自己的進階語言。不完全實作c語言的所有文法，不僅可以減少重複的工作量，還能将精力重點放在編譯算法的實作上，而不是複雜的語言文法上。是以在c語言的基礎上，我們删除了浮點類型和struct類型，并将數組和指針的維數簡化到一維。

　　4）編譯優化算法。編譯器内引入了編譯優化相關的内容，考慮到編譯優化算法的多樣性，我們挑選了若幹經典的編譯優化算法作為優化器的實作。通過對資料流問題優化算法的實作，可以幫助了解優化器的工作原理，對以後深入學習編譯優化算法具有引導意義。

　　5）彙編語言的處理。本書的編譯器産生的彙編指令屬于intel x86處理器指令集的子集，雖然這間接降低了彙編器實作的複雜度，但是不會影響彙編器關鍵流程的實作。另外，編譯器在産生彙編代碼之前已經分析了源程式的正确性，生成的彙編代碼都是合法的彙編指令，是以在彙編器的實作過程中不需要考慮彙編語言的詞法、文法和語義錯誤的情況。

　　6）靜态連結方式。本書的編譯系統實作的連結器采用靜态連結的方式。這是因為動态連結器的實作相對複雜，而且其與靜态連結器處理的核心問題基本相同。讀者在了解了靜态連結器的構造的基礎上，通過進一步的學習也可以實作一個動态連結器。

　　7）elf檔案資訊。除了elf檔案必需的段和資料，我們把代碼全部存放在“.text”段，資料存儲在“.data”段。按照這樣的檔案結構組織方式，不僅能保證二進制代碼正常執行，也有助于我們更好地了解elf檔案的結構群組織。

　　綜上所述，我們所做的限制并沒有删除編譯系統關鍵的流程。按照這樣的設計，是可以允許一個人獨立完成一個較為完善的編譯系統的。

1.5  本章小結

　　本章從程式設計最基本的話題聊起，描述了初學者接觸程式時可能遇到的疑惑，并從程式設計實踐經驗中探索代碼背後的處理機制。然後，使用最簡單的“hello world !”程式展現主流編譯器gcc對代碼的處理流程。最後，我們在工業化編譯系統的基礎上做了一定的限制，提出了本書編譯系統需要實作的功能。在接下來的章節中，會對本書中編譯系統的設計和實作細節詳細闡述。

第2章

　　編譯系統設計

麻雀雖小，五髒俱全。

——《圍城》

　　一個完善的工業化編譯系統是非常複雜的，為了清晰地描述它的結構，了解編譯系統的基本流程，不得不對它進行“大刀闊斧”地删減。這為自己動手實作一個簡單但基本功能完整的編譯系統提供了可能。雖然本書設計的是簡化後的編譯系統，但保留了編譯系統的關鍵流程。正所謂“麻雀雖小，五髒俱全”，本章從全局的角度描述了編譯系統的基本結構，并按照編譯、彙編和連結的流程來介紹其設計。

2.1  編譯程式的設計

　　編譯器是編譯系統的核心，主要負責解析源程式的語義，生成目标機器代碼。一般情況下，編譯流程包含詞法分析、文法分析、語義分析和代碼生成四個階段。符号表管理和錯誤處理貫穿于整個編譯流程。如果編譯器支援代碼優化，那麼還需要優化器子產品。

　　圖2-1展示了本書設計的優化編譯器的結構，下面分别對上述子產品的實作方案做簡單介紹。

圖2-1  編譯器結構

2.1.1  詞法分析

　　編譯器工作之前，需要将用進階語言書寫的源程式作為輸入。為了便于了解，我們使用c語言的一個子集定義進階語言，本書後續章節的例子都會使用c語言的一些基本文法作為示例。現在假定我們擁有一段使用c語言書寫的源程式，詞法分析器通過對源檔案的掃描獲得進階語言定義的詞法記号。所謂詞法記号（也稱為終結符），反映在進階語言文法中就是對應的辨別符、關鍵字、常量，以及運算符、逗号、分号等界符。見圖2-2。

　　例如語句：

var2=var1+100;

   該語句包含了6個詞法記号，它們分别是：“var2”“=”“var1”“+”“100”和分号。

　　對詞法分析器的要求是能正常識别出這些不同形式的詞法記号。詞法分析器的輸入是源代碼文本檔案内一長串的文本内容，那麼如何從文本串中分析出每個詞法記号呢？為了解決這個問題，需要引入有限自動機的概念。

　　有限自動機能解析并識别詞法記号，比如識别辨別符的有限自動機、識别常量的有限自動機等。有限自動機從開始狀态啟動，讀入一個字元作為輸入，并根據該字元選擇進入下一個狀态。繼續讀入新的字元，直到遇到結束狀态為止，讀入的所有字元序列便是有限自動機識别的詞法記号。

　　圖2-3描述了識别辨別符的有限自動機。c語言辨別符的定義是：一個不以數字開始的由下劃線、數字、字母組成的非空字元串。圖中的自動機從0号狀态開始，讀入一個下劃線或者字母進入狀态1，狀态1可以接受任意數量的下劃線、字母和數字，同時狀态1也是結束狀态，一旦它讀入了其他異常字元便停止自動機的識别，這樣就可以識别任意一個合法的辨別符。如果在非結束狀态讀入了異常的字元，意味着發生了詞法錯誤，自動機停止（當然，上述辨別符的有限自動機不會出現錯誤的情況）。

圖2-3  辨別符有限自動機

　　我們以指派語句“var2=var1+100;” 中的變量var2為例來說明有限自動機識别詞法記号的工作過程。

　　識别var2的自動機狀态序列和讀入字元的對應關系如表2-1所示，結束狀态之前識别的字元序列即為合法的辨別符。

　　使用有限自動機，可以識别出自定義語言包含的所有詞法記号。把這些詞法記号記錄下來，作為下一步文法分析的輸入。如果使用一遍編譯方式，就不用記錄這些詞法記号，而是直接将識别的詞法記号送入文法分析器進行處理。

2.1.2  文法分析

　　詞法分析器的輸入是文本字元串，文法分析器的輸入則是詞法分析器識别的詞法記号序列。文法分析器的輸出不再是一串線性符号序列，而是一種樹形的資料結構，通常稱之為抽象文法樹。見圖2-4。

　　繼續前面指派語句的例子，我們可以先看看它可能對應的抽象文法樹，如圖2-5所示。

圖2-5  抽象文法樹示例

　　從圖2-5中可以看出，所有的詞法記号都出現在樹的葉子節點上，我們稱這樣的葉子節點為終結符。而所有的非葉子節點，都是對一串詞法記号的抽象概括，我們稱之為非終結符，可以将非終結符看作一個單獨的文法子產品（抽象文法子樹）。其實，整個源程式是一棵完整的抽象文法樹，它由一系列文法子產品按照樹結構組織起來。文法分析器就是要獲得源程式的抽象文法樹表示，這樣才能讓編譯器具體識别每個文法子產品的含義，分析出程式的整體含義。

　　在介紹文法分析器的工作之前，需要先獲得進階語言文法的形式化表示，即文法。文法定義了源程式代碼的書寫規則，同時也是文法分析器構造抽象文法樹的規則。如果要定義指派語句的文法，一般可以表達成如下産生式的形式：

　　<指派語句> => 辨別符 等号 <表達式> 分号

　　被“< >”括起來的内容表示非終結符，終結符直接書寫即可，上式可以讀作“指派語句推導出辨別符、等号、表達式和分号”。顯然，表達式也有相關的文法定義。根據定義好的進階語言特性，可以設計出相應的進階語言的文法，使用文法可以準确地表達進階語言的文法規則。

　　有了進階語言的文法表示，就可以構造文法分析器來生成抽象文法樹。在編譯原理教材中，描述了很多的文法分析算法，有自頂向下的ll（1）分析，也有自底向上的算符優先分析、lr分析等。其中最常使用的是ll（1）和lr分析。相比而言，lr分析器能力更強，但是分析器設計比較複雜，不适合手工構造。我們設計的進階語言文法，隻要稍加限制便能使ll（1）分析器正常工作，是以本書采用ll（1）分析器來完成文法分析的工作。遞歸下降子程式作為ll（1）算法的一種便捷的實作方式，非常适合手工實作文法分析器。

　　遞歸下降子程式的基本原則是：将産生式左側的非終結符轉化為函數定義，将産生式右側的非終結符轉化為函數調用，将終結符轉化為詞法記号比對。例如前面提到的指派語句對應的子程式的僞代碼大緻是這樣的。

void 指派語句()

     match(辨別符);

     match(等号);

     表達式();

     match(分号);

　　每次對子程式的調用，就是按照前序的方式對該抽象文法子樹的一次構造。例如在構造指派語句子樹時，會先構造“指派語句”根節點，然後依次比對辨別符、等号子節點。當遇到下一個非終結符時，會進入對應的“表達式”子程式内繼續按照前序方式構造子樹的子樹。最後比對目前子程式的最後一個子節點，完成“指派語句”子樹的構造。整個文法分析就是按照這樣的方式構造“程式”樹的一個過程，一旦在終結符比對過程中出現讀入的詞法記号與預期的詞法記号不吻合的情況，便會産生文法錯誤。

　　在實際文法分析器實作中，并不一定要顯式地構造出抽象文法樹。遞歸下降子程式實作的文法分析器，使得抽象文法樹的文法子產品都蘊含在每次子程式的執行中，即每次子程式的正确執行都表示識别了對應的文法子產品。是以，可以在文法分析子程式中直接進行後續的工作，如語義分析及代碼生成。

2.1.3  符号表管理

　　符号表是記錄符号資訊的資料結構，它使用按名存取的方式記錄與符号相關的所有編譯資訊。編譯器工作時，少不了符号資訊的記錄和更新。在本書定義的進階語言中，符号存在兩種形式：變量和函數。前者是資料的符号化形式，後者是代碼的符号化形式。語義分析需要根據符号檢測變量使用的合法性，代碼生成需要根據符号産生正确的位址，是以，符号資訊的準确和完整是進行語義分析和代碼生成的前提。見圖2-6。

　　對于變量符号，需要在符号表中記錄變量的名稱、類型、區分變量的聲明和定義的形式，如果變量是局部變量，還需要記錄變量在運作時棧幀中的相對位置。例如以下變量聲明語句：

extern int var;

　　該語句聲明了一個外部的全局變量，記錄變量符号的資料結構除了儲存變量的名稱“var”之外，還需要記錄變量的類型“int”，以及變量是外部變量的聲明形式“extern”。

　　對于函數符号，需要在符号表中記錄函數的名稱、傳回類型、參數清單，以及函數内定義的所有局部變量等。例如下面的函數定義代碼：

int sum(int a,int b)

     int c;

     c=a+b;

     return c;

　　符号表應該記錄函數的傳回類型“int”、函數名“sum”、參數清單“int,int”。函數的局部變量除了顯式定義的變量“c”之外，還暗含參數變量“a”和“b”。

　　由于局部變量的存在，符号表必須考慮代碼作用域的變化。函數内的局部變量在函數之外是不可見的，是以在代碼分析的過程中，符号表需要根據作用域的變化動态維護變量的可見性。

2.1.4  語義分析

　　編譯原理教材中，将語言的文法分為4種：0型、1型、2型、3型，并且這幾類文法對語言的描述能力依次減弱。其中，3型文法也稱為正規文法，詞法分析器中有限自動機能處理的語言文法正是3型文法。2型文法也稱為上下文無關文法，也是目前計算機程式語言所采用的文法。顧名思義，程式語言的文法是上下文無關的，即程式代碼語句之間在文法層次上是沒有關聯的。例如在分析指派語句時，ll（1）分析器無法解決“被指派的對象是已經聲明的辨別符嗎？”這樣的問題，因為文法分析隻關心程式語言文法形式的正确性，而不考慮文法子產品上下文之間聯系的合法性。

　　然而實際的情況是，程式語言的語句雖然形式上是上下文無關的，但含義上卻是上下文相關的。例如：不允許使用一個未聲明的變量，不允許函數實參清單和形參清單不一緻，不允許對無法預設轉換的類型進行指派和運算，不允許continue語句出現在循環語句之外等，這些要求是文法分析器不能完成的。

　　根據本書設計的程式語言文法，編譯器的語義分析子產品（見圖2-7）處理如下類似問題：

　　1）變量及函數使用前是否定義？

　　2）break語句是否出現在循環或switch-case語句内部？

　　3）continue語句是否出現在循環内部？

　　4）return語句傳回值的類型是否與函數傳回值類型相容？

　　5）函數調用時，實參清單和形參清單是否相容？

　　6）表達式計算及指派時，類型是否相容？

　　語義分析是編譯器處理流程中對源代碼正确性的最後一次檢查，隻要源代碼語義上沒有問題，編譯器就可以正常引導目标代碼的生成。

2.1.5  代碼生成

　　代碼生成是編譯器的最後一個處理階段，它根據識别的文法子產品翻譯出目标機器的指令，比如彙編語言，這一步稱為使用基于文法制導的方式進行代碼生成。見圖2-8。

　　為了便于了解，本書采用常見的intel格式彙編語言程式作為編譯器的輸出。繼續引用指派語句“var2=var1+100；”作為例子，若将之翻譯為彙編代碼，其内容可能是：

mov eax,[var1]

mov ebx,100

add eax,ebx

mov [tmp],eax

mov eax,[tmp]

mov [var2],eax

　　參考圖2-5中的兩個非葉子節點，它們分别對應了表達式文法子產品和指派語句文法子產品。上面彙編代碼的前4行表示将var1與100的和存儲在臨時變量tmp中，是對表達式翻譯的結果。最後兩行表示将臨時變量tmp複制到var2變量中，是對指派語句的翻譯結果。根據自定義語言的文法，需要對如下文法子產品進行翻譯：

　　1）表達式的翻譯。

　　2）複合語句的翻譯。

　　3）函數定義與調用的翻譯。

　　4）資料段資訊的翻譯。

2.1.6  編譯優化

　　現代編譯器一般都包含優化器，優化器可以提高生成代碼的品質，但會使代碼生成過程變得複雜。一般主流的工業化編譯器會按照如圖2-9所示結構進行設計。

　　現代編譯器設計被分為前端、優化器和後端三大部分，前端包含詞法分析、文法分析和語義分析。後端的指令選擇、指令排程和寄存器配置設定實際完成代碼生成的工作，而優化器則是對中間代碼進行優化操作。實作優化器，必須設計編譯器的中間代碼表示。中間代碼的設計沒有固定的标準，一般由編譯器設計者自己決定。

圖2-9  現代編譯器結構

　　由于中間代碼的存在，使得文法制導翻譯的結果不再是目标機器的代碼，而是中間代碼。按照我們自己設計的中間代碼形式，上述例子生成的中間代碼可能是如下形式：

tmp=var1+100

var2=tmp

　　即使優化器沒有對這段代碼進行處理，編譯器的後端也能正确地把這段中間代碼翻譯為目标機制指令。根據指令選擇和寄存器配置設定算法，得到的目标機器指令可能如下：

add eax,100

　　編譯器後端在指令選擇階段會選擇更“合适”的指令實作中間代碼的翻譯，比如使用“add eax,100”實作tmp=var1+100的翻譯。在寄存器配置設定階段會盡可能地将變量儲存在寄存器内，比如tmp一直儲存在eax中。

　　中間代碼的抽象程度一般介于進階語言和目标機器語言之間。良好的中間代碼形式使得中間代碼生成、目标代碼生成以及優化器的實作更加簡單。我們設計的優化器實作了常量傳播、備援消除、複寫傳播和死代碼消除等經典的編譯優化算法。先通過一個簡單的執行個體說明中間代碼優化的工作。

var1=100;

　　将上述進階語言翻譯為中間代碼的形式如下：

var1=100

　　常量傳播優化使編譯器在編譯期間可以将表達式的結果提前計算出來，是以經過常量傳播優化後的中間代碼形式如下：

tmp=200

var2=200

　　死代碼消除優化會把無效的表達式從中間代碼中删除，假如上述代碼中隻有變量var2在之後會被使用，那麼var1和tmp都是無效的計算。是以，消除死代碼後，最終的中間代碼如下：

　　再經過後端将之翻譯為彙編代碼如下：

mov [var2],200

   由于本書篇幅及作者水準所限，在不能實作所有的編譯優化算法的情況下，選擇若幹經典的優化算法來幫助讀者了解優化器的基本工作流程。

　　至此，我們簡單介紹了進階語言源檔案轉化為目标機器的彙編代碼的基本流程。本書設計的編譯器支援多檔案的編譯，是以編譯器會為每個源檔案單獨生成一份彙編檔案，然後通過彙編器将它們轉換為二進制目标檔案。彙編過程中涉及目标機器的指令格式和可執行檔案的内容，為了便于了解彙編器的工作流程，需要提前準備與作業系統和硬體相關的知識。

2.2  x86指令格式

　　編譯系統的彙編器需要把編譯器生成的彙編語言程式轉化為x86格式的二進制機器指令序列，然後将這些二進制資訊存儲為elf格式的目标檔案。是以需要先了解二進制機器指令的基本結構。

　　如圖2-10所示，在x86的指令結構中，指令被分為字首、操作碼、modr/m、sib、偏移量和立即數六個部分。本書設計的編譯器生成的彙編指令中不包含字首，這裡暫時不介紹它的含義。操作碼部分決定了指令的含義和功能，modr/m和sib位元組為擴充操作碼或者為指令操作數提供各種不同的尋址模式。如果指令含有偏移量和立即數資訊，就需要把它們放在指令後邊的對應位置。

圖2-10  x86指令格式

　　這裡使用一個簡單的例子與表2-2說明x86指令結構的含義，例如彙編指令：

表2-2  二進制指令編碼

指令格式

操作碼

mod字段

reg字段

r/m字段

指令編碼

add r/m32,reg

0x01

11

000

0000 0011 1100 0011

add reg,r/m32

0x03

0000 0001 1101 1000　　查閱intel的指令手冊，當操作數為32位寄存器時，add指令的操作碼是0x01或者0x03，它們對應的指令格式是add r/m32,reg和add reg,r/m32。在modr/m位元組的定義中，高兩位mod字段為0b11時表示指令的兩個操作數都是寄存器，低三位表示r/m操作數寄存器的編号，中間三位表示reg操作數寄存器的編号。intel定義eax寄存器編号為0b000，ebx寄存器編号為0b011。如果我們采用操作碼0x01，reg應該記錄ebx的編号0b011，r/m32記錄eax編号0b000，mod字段為0b11。是以該指令的modr/m位元組為：

11 011 000  =>  0xd8

　　同理，若采用操作碼0x03的話，modr/m位元組應該是：

11 000 011  =>  0xc3

　　指令不再含有其他資訊，是以不存在sib和偏移量、立即數字段。這樣“add eax,ebx”指令就有兩種二進制表示形式：0x01d8與0x03c3。

　　通過這個例子可以得出結論：在彙編器文法分析階段，應該記錄生成的二進制指令需要的資訊。指令的名稱決定操作碼，指令的尋址方式決定modr/m和sib字段，指令中的常量決定偏移量和立即數部分。

　　由于本書設計的編譯器所生成的彙編指令的種類有限，是以降低了彙編器對指令資訊分析的複雜度，但是還有大量的其他類型的指令需要具體分析，這些内容會在以後章節中闡述。

2.3  elf檔案格式

　　elf檔案格式描述了linux下可執行檔案、可重定位目标檔案、共享目标檔案、核心轉儲檔案的存儲格式。本書設計的編譯系統隻關心可執行檔案和可重定位目标檔案的格式，如果要設計動态連結器的話，則還需要了解共享目标檔案的内容。

　　elf檔案資訊的一般存儲形式如圖2-11所示。

　　在linux下，可以使用readelf指令檢視elf檔案的資訊。如果要檢視1.3.3節生成的hello.o的資訊，可以使用如下指令檢視elf的所有關鍵資訊：

readelf –a hello.o

　　在elf檔案中，最開始的52個位元組記錄elf檔案頭部的資訊，通過它可以确定elf檔案内程式頭表和段表的位置及大小。以下列出了hello.o檔案頭資訊。

elf header:

  magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 

  class: elf32

  data: 2's complement, little endian

  version: 1 (current)

  os/abi: unix - system v

  abi version: 0

  type: rel (relocatable file)

  machine: intel 80386

  version: 0x1

  entry point address: 0x0

  start of program headers: 0 (bytes into file)

  start of section headers: 224 (bytes into file)

  flags: 0x0

  size of this header: 52 (bytes)

  size of program headers: 0 (bytes)

  number of program headers: 0

  size of section headers: 40 (bytes)

  number of section headers: 11

  section header string table index: 8

　　緊接着檔案頭便是程式頭表，它記錄程式運作時作業系統如何将檔案加載到記憶體，是以隻有可執行檔案包含程式頭表。使用readelf檢視1.3.4節靜态連結生成的hello檔案，可以看到它的程式頭表，類型為load的表項表示需要加載的段。以下列出它的程式頭表資訊。

program headers:

  type        offset     virtaddr    physaddr     filesiz  memsiz  flg  align

  load        0x000000  0x08048000  0x08048000  0x84fd2  0x84fd2  r e  0x1000

  load        0x085f8c  0x080cdf8c  0x080cdf8c  0x007d4  0x02388  rw    0x1000

  note        0x0000f4  0x080480f4  0x080480f4  0x00044  0x00044  r     0x4

  tls         0x085f8c  0x080cdf8c  0x080cdf8c  0x00010  0x00028  r     0x4

  gnu_stack  0x000000  0x00000000  0x00000000  0x00000  0x00000  rw   0x4

  gnu_relro  0x085f8c  0x080cdf8c  0x080cdf8c  0x00074  0x00074  r     0x1

　　elf檔案最關鍵的結構是段表，這裡的段表示檔案内的資訊塊，與彙編語言内的段并非同一個概念。段表記錄了elf檔案内所有段的位置和大小等資訊。在所有的段中，有儲存代碼二進制資訊的代碼段、存儲資料的資料段、儲存段表名稱的段表字元串表段和存儲程式字元串常量的字元串表段。符号表段記錄彙編代碼中定義的符号資訊，重定位表段記錄可重定位目标檔案中需要重定位的符号資訊。hello.o的段表如下：

section headers:

  [nr] name              type       addr      off     size   es flg lk inf al

  [0]                      null       00000000  000000  000000 00 0 0 0

  [1] .text               progbits  00000000  000034  00001d 00 ax 0 0 4

  [2] .rel.text          rel        00000000  000350  000010 08 9 1 4

  [3] .data               progbits  00000000  000054  000000 00 wa 0 0 4

  [4] .bss                nobits     00000000  000054  000000 00 wa 0 0 4

  [5] .rodata            progbits  00000000  000054  00000d 00 a 0 0 1

  [6] .comment           progbits  00000000  000061  00002c 01 ms 0 0 1

  [7] .note.gnu-stack  progbits  00000000  00008d  000000 00 0 0 1

  [8] .shstrtab          strtab    00000000  00008d  000051 00 0 0 1

  [9] .symtab            symtab    00000000  000298  0000a0 10 10 8 4

  [10].strtab            strtab    00000000  000338  000015 00 0 0 1

　　符号表段是按照表格形式存儲符号資訊的，我們可以看到主函數和printf函數的符号項。

symbol table '.symtab' contains 10 entries:

   num: value      size type  bind vis      ndx name

     0: 00000000     0 notype  local default  und 

     1: 00000000     0 file  local default  abs hello.c

     2: 00000000     0 section  local default   1

     3: 00000000     0 section  local default   3

     4: 00000000     0 section  local default   4

     5: 00000000     0 section  local default   5

     6: 00000000     0 section  local default   7

     7: 00000000     0 section  local default   6

     8: 00000000    29 func  global default   1 main

     9: 00000000     0 notype  global default   und printf

　　重定位表也是按照表格形式存儲的，很明顯，printf作為外部符号是需要重定位的。

relocation section '.rel.text' at offset 0x350 contains 2 entries:

offset info type sym.value sym.name

0000000a 00000501    r_386_32 00000000 .rodata

00000012 00000902    r_386_pc32 00000000 printf

　　從elf檔案格式的設計中可以看出，可執行檔案其實就是按照一定标準将二進制資料和代碼等資訊包裝起來，友善作業系統進行管理和使用。從檔案頭可以找到程式頭表和段表，從段表可以找到其他所有的段。是以，在彙編語言輸出目标檔案的時候，就需要收集這些段的資訊，并按照elf格式組裝目标檔案。這樣做不僅有利于使用作業系統現有的工具調試檔案資訊，也為後期連結器的實作提供了友善。

　　另外需要說明的是，對于elf檔案格式的定義，linux提供了頭檔案描述。在系統目錄/usr/include/elf.h提供的elf.h頭檔案中描述了标準elf檔案的資料結構的定義，在實作彙編器和連結器的代碼中都使用了該頭檔案。

2.4  彙程式設計式的設計

　　通過對彙編器已有的了解，可以發現彙編器和編譯器的實作非常相似。編譯器是将進階語言翻譯為彙編語言的轉換程式，彙編器則是将彙編語言翻譯為目标機器二進制代碼的轉換程式。彙編器實際就是彙編語言的“編譯器”，雖然彙編語言并非進階語言。

　　彙編器也包含詞法分析、文法分析、語義處理、代碼生成四個基本流程。但前面讨論過，本書設計的彙編器面向編譯器所生成的彙編代碼，彙編代碼的正确性由編譯器保證，是以彙編器不需要進行錯誤檢查以及語義的正确性檢查。本書設計的彙編器結構如圖2-12所示。

　　相比于編譯器，彙編器的工作重點放在目标檔案資訊的收集和二進制指令的生成上。下面分别介紹彙編器的基本子產品。

圖2-12  彙編器結構

2.4.1  彙編詞法、文法分析

　　彙編語言有獨立的詞法記号，對于彙編詞法的分析，隻需要構造相應的詞法有限自動機就可以了。舉一個簡單的例子：

mov eax,[ebp-8]

　　該指令有8個詞法記号，它們分别是：＇mov＇＇eax＇逗号＇[＇＇ebp＇＇–＇＇8＇和＇]＇。彙編器的詞法分析器将詞法記号送到文法分析器用于識别彙編語言的文法子產品。同樣，我們需要構造彙編語言文法分析器，在這裡可以提前看一下上述彙編指令的抽象文法樹，如圖2-13所示。

圖2-13  彙編指令抽象文法子樹

　　圖2-13中是簡化後的抽象文法樹，與編譯器類似，文法分析器會在非葉子節點處識别文法子產品，以産生語義動作。由于彙編器要輸出可重定位目标檔案，是以在文法分析時要收集目标檔案的相關資訊。比如記錄代碼段和資料段的長度、目标檔案符号表的内容、重定位表的内容等，這些操作都在文法分析器識别每個文法子產品時使用文法制導的方式完成。

　　另外，彙編器和編譯器最大的不同是彙編器需要對源檔案進行兩遍掃描，其根本原因是彙編語言允許符号的後置定義，例如彙編語言常見的跳轉指令：

     jmp l

l:

　　很明顯，在第一遍分析jmp指令的時候，彙編器并不知道符号l是否已經定義。是以，彙編器需要通過第一遍掃描擷取符号的資訊，在第二遍掃描時使用符号的資訊。

2.4.2  表資訊生成

　　彙編器的符号表除了記錄符号的資訊之外，還需要記錄段相關的資訊以及重定位符号的資訊，這些資訊都是生成可重定位目标檔案所必需的。

　　對于段表的資訊，可以在彙編器識别section文法子產品時進行處理。比如聲明代碼段的彙編代碼及段表資訊生成（見圖2-14）。

section .text

圖2-14  段表資訊生成

　　彙編器的文法分析器隻要計算兩次section聲明之間的位址差，便能獲得段的長度，進而将段的名稱、偏移、大小記錄到段表項内。如果規定段按照4位元組對齊，則需要對段偏移進行擴充，如圖2-14所示。

　　彙編器的符号表與elf檔案的符号表并非同一個概念。彙編器的符号表來源于彙編語言定義的符号，elf檔案的符号表是彙編器根據需要導出的符号資訊，如圖2-15所示。最明顯的一個例子就是使用equ指令定義的符号，這個符号對彙編器來說是一個符号，但在elf檔案内，它就是一個數字常量，不存在符号資訊。

圖2-15  符号表資訊生成

　　目标檔案連結時會重新組織代碼段、資料段的位置。這樣段内定義的所有符号的位址以及引用符号的資料和指令都會産生偏差，這時就重新計算符号的位址，修改原來的位址，也就是常說的重定位。重定位一般分為兩大類：絕對位址重定位和相對位址重定位。在重定位表内，需要記錄符号重定位相關的所有資訊（見圖2-16）。

圖2-16  重定位表資訊生成

2.4.3  指令生成

　　2.2節介紹了x86指令的基本結構。同樣，在彙編器文法分析時，需要根據指令的文法子產品收集這些指令的結構資訊。比如操作碼、modr/m字段、sib字段、偏移量、立即數，然後按照指令的結構将上述資訊寫入檔案即可。

　　首先，指令名和操作碼一般是一對多的關系，是以需要根據具體的操作數類型或長度來決定操作碼的值。按照操作數不同建立一張指令的操作碼表來執行操作碼的查詢是一種有效的解決方案。

　　其次，有些指令的modr/m字段的reg部分與操作碼有關，但不需要輸出modr/m字段，彙編器需要單獨處理這些特殊的指令操作碼。另外，modr/m字段中包含是否擴充了sib字段的資訊。

　　除了正确輸出指令的二進制資訊外，彙編器在遇到對符号引用的指令時還要記錄相關重定位資訊，比如重定位位址、重定位符号、重定位類型等。

　　最後，參考之前介紹的elf檔案結構，彙編器将收集到的段資訊和二進制資料組裝到目标檔案内。

　　至此，根據已描述的彙編器主要工作流程，可以生成标準的elf可重定位目标檔案。那麼，如何把這些分散的目标檔案合并成我們最終想要的可執行檔案，便是接下來要介紹的連結器的工作内容。

2.5  連結程式的設計

　　本書欲設計一個簡潔的靜态連結器，以滿足上述彙編器産生的目标檔案的連結需求。它的工作内容是把多個可重定位目标檔案正确地合并為可執行檔案，但連結器不是對檔案進行簡單的實體合并。除了合并同類的段外，連結器需要為段配置設定合适的位址空間，還需要分析目标檔案符号定義的完整性，同時對符号的位址資訊進行解析，最後還有連結器最關鍵的工作——重定位。本書設計的連結器結構如圖2-17所示。

圖2-17  連結器結構

　　段的位址空間配置設定除了為加載器提供相應的資訊外，還可為段内符号位址的計算提供依據。符号解析除了驗證符号引用和定義的正确性之外，還需要計算出每個符号表内符号的虛拟位址。重定位可以讓每個引用符号的資料或者代碼具有正确的内容，以保證程式的正确性，下面就按照這三個方面分别介紹連結器的工作。

2.5.1  位址空間配置設定

　　在彙編器生成的目标檔案内，是無法确定資料段和代碼段的虛拟位址的，是以将它們的段位址都設定為0。連結器是這些代碼和資料加載到記憶體執行之前的最後一道處理，是以要為它們配置設定段的基址。

　　連結器按照目标檔案的輸入順序掃描檔案資訊，從每個檔案的段表中提取出各個檔案的代碼段和資料段的資訊。假設可執行檔案段加載後的起始位址是0x080408000，連結器從該位址開始，就像“擺積木”似的将所有檔案的同類型段合并，按照代碼段、資料段、“.bss”段的順序依次決定每個段的起始位址，此時需要考慮段間對齊産生的偏移以及特殊的位址計算方式（參考第5章關于程式頭表的描述）。

　　圖2-18展示了連結器将目标檔案a.o和b.o連結為可執行檔案ab時，位址空間配置設定的效果。a.o的資料段大小為0x08位元組，代碼段大小為0x4a位元組；b.o的資料段大小為0x04位元組，代碼段大小為0x21位元組。連結後的可執行檔案ab的資料段大小為0x0c位元組，代碼段大小為0x6d位元組（對齊b.o的代碼段消耗2位元組）。代碼段的起始位址為0x08048080，結束位址為0x08048080+0x6d=0x080480ed。資料段起始位址為0x080490f0，結束位址為0x080490f0+ 0x0c=0x080490fc。

圖2-18  位址空間配置設定

2.5.2  符号解析

　　如果說位址空間配置設定是為段指定位址的話，那麼符号解析就是為段内的符号指定位址。對于一個彙編檔案來說，它内部使用的符号分為兩類：一類來自自身定義的符号，稱為内部符号。内部符号在其段内的偏移是确定的，當段的起始位址指定完畢後，内部符号的位址按照如下方式計算：

　　符号位址 = 符号所在段基址 + 符号所在段内偏移

　　另一類來自其他檔案定義的符号，本地檔案隻是使用該符号，這類符号稱為外部符号。外部符号位址在本地檔案内是無法确定的，但是外部符号總定義在其他檔案中。外部符号相對于定義它的檔案就是内部符号了，同樣使用前面的方式計算出它的位址，而使用該符号的本地檔案需要的也是這個位址。

　　在重定位目标檔案内，符号表記錄了符号的所有資訊。對于本地定義的符号，符号表項記錄符号的段内偏移位址。對于外部引用的符号，符号表項辨別該符号為“未定義的”。當連結器掃描到定義該外部符号的目标檔案時，就需要将該外部符号的位址修改為正确的符号位址。最終的結果使得所有目标檔案内的符号資訊，無論是本地定義的還是外部定義的都是完整的、正确的。

　　連結器在掃描重定位目标檔案的符号表時會動态地維護兩個符号集合。一個記錄所有檔案定義的全局符号集合export，該集合内的所有符号允許被其他檔案引用。還有一個記錄所有檔案使用的未定義符号的集合import，該集合内所有符号都來源于其他目标檔案。檔案掃描完畢後，連結器需要驗證import集合是否是export的子集。如果不是，就表明存在未定義的符号。未定義的符号資訊是未知的，連結器無法進行後續的操作，因而會報錯。如果驗證成功，則表明所有檔案引用的外部符号都已定義，連結器才會将已定義的符号資訊拷貝到未定義符号的符号表項。

　　符号解析完畢後，所有目标檔案符号表内的所有符号都獲得了完整、正确的符号位址資訊。比如圖2-18内的符号var、ext和fun在符号解析後的符号位址分别為0x080490f4、0x080490f8和0x080480cc。

2.5.3  重定位

　　重定位從本質上來說就是位址修正。由于目标檔案在連結之前不能擷取自己所使用符号的虛拟位址資訊，是以導緻依賴于這些符号的資料定義或者指令資訊缺失。彙編器在生成目标檔案的時候就記錄下所有需要重定位的資訊。連結器擷取這些重定位資訊，并按照重定位資訊的含義修改已經生成的代碼，使得最終的代碼正确、完整。

　　之是以稱重定位是連結器最關鍵的操作，主要是因為位址空間配置設定和符号解析都是為重定位做準備的。程式在運作時，段的資訊、符号的資訊都顯得“微不足道”，因為cpu隻關心檔案内的代碼和資料。即便如此，也不能忽略位址空間配置設定和符号解析的重要性。既然重定位是對已有二進制資訊的修改，是以作為連結器需要清楚幾件事情：

　　1）在哪裡修改二進制資訊？

　　2）用什麼資訊進行修改？

　　3）按照怎樣的方式修改？

　　這三個問題反映在重定位中對應的三個參數：重定位位址、重定位符号和重定位類型。

　　重定位位址在重定位表中沒有直接記錄，因為在重定位目标檔案内，段位址還沒确定下來，它隻記錄了重定位位置所在段内的偏移，在位址空間配置設定結束後，我們使用如下公式計算出重定位位址：

　　重定位位址 = 重定位位置所在段基址 + 重定位位置的段内偏移

　　重定位符号記錄着被指令或者資料使用的符号資訊，比如call指令的标号、mov指令使用的變量符号等。在符号解析結束後，重定位符号的位址就已經确定了。

　　重定位類型決定修改二進制資訊的方式，即絕對位址重定位和相對位址重定位。

　　在确定了重定位符号位址和重定位位址後，根據重定位的類型，連結器便可以正确修改重定位位址處的符号位址資訊。

　　至此，連結器的主要工作流程描述完畢。作為編譯系統的最後一個功能子產品，連結器與作業系統的關系是最密切的，比如它需要考慮頁面位址對齊、指令系統結構以及加載器工作的特點等。

2.6  本章小結

　　本章介紹了編譯系統的設計，并按照編譯、彙編和連結的順序闡述了它們的内部實作。同時，也介紹了x86指令和elf檔案結構等與作業系統及硬體相關的知識。

　　通過以上的描述，可以了解進階語言如何被一步步轉化為彙編語言，以及詞法分析、文法分析、語義分析、符号表和代碼生成作為編譯器的主要子產品，其内部是如何實作的。彙編器在把彙編語言程式轉化為二進制機器代碼時，做了怎樣的工作；彙編器的詞法和文法分析與編譯器有何不同；彙編器如何生成二進制指令和目标檔案的資訊。連結器在處理目标檔案時是如何進行位址配置設定、符号解析以及重定位的，它生成的可執行檔案和目标檔案有何不同等。

　　通過對這些問題的簡要描述，我們對編譯系統的工作流程有了全局的認識。至于具體的實作細節會在以後的章節中以一個自己動手實作的編譯系統為例詳細進行介紹，下面就讓我們開始實作一個真正的編譯系統吧！