自己動手構造編譯系統：編譯、彙編與鏈接（簡體書）

本書以作者實現的一個基於Intelx86指令集的編譯系統為例，結合程式碼的主要部分詳細闡述了編譯系統的實現原理和過程。本書對編譯器、彙編器、連結器、編譯優化器涉及的關鍵演算法、資料結構和程式實現流程，以及ELF檔的格式、Intel指令格式均作了詳細的說明，並結合大量的圖表，展示了編譯系統工作過程中代碼資訊的流動和存儲格式的變化。是一本“手把手”教讀者實現編譯系統的貼心手冊。

范志東　就職於騰訊資料平臺部，負責騰訊大資料平臺的產品化，涉及自動化部署、應用調度、交互分析、集群監控、性能調優等，對開源工具Ambari、Hadoop、Spark等有深入的瞭解。在校期間屢次獲得國家獎學金和勵志獎學金。獨立開發了基於Intel x86指令集的自訂類C語言的編譯系統，包括編譯器、彙編器與連結器的實現，對電腦程式的載入和運行原理有深刻的認識。深入分析過Linux內核關於CPU功耗方面的代碼。愛好廣泛，對程式設計語言、作業系統、編譯系統、電腦安全、分散式系統有著濃厚的興趣。閒暇時會在技術博客上分享自己的學習心得，期望通過互聯網把獲得知識的快樂心情傳遞出去。參與了“十一五”校級立項正式出版教材《電腦作業系統原理》以及全國自學考試教材《電腦應用技術》編寫的相關工作。

張瓊聲　湖北省松滋縣人，中國石油大學（華東）電腦與通信工程學院副教授，碩士生導師。主講課程:《作業系統》《作業系統課程實習》和《嵌入式作業系統》。主持的《電腦作業系統》課程被評為校級精品課，先後獲得中國石油大學優秀教學研究成果一、二、三等獎各一項；曾獲評中國石油大學優秀教師、山東省優秀學士論文指導教師；主持或參與科研、教研專案十四項。專業及研究興趣為系統軟體發展技術，包括：作業系統、編譯系統、電腦系統安全性。發表科研、教學論文二十餘篇。參與翻譯《深入理解Linux內核》第3版，編著“十一五”校級立項正式出版教材《電腦作業系統原理》、主編全國自學考試教材《電腦應用技術》。

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

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

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

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

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

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

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

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

 

張瓊聲

2016年春於北京

序
前言
第1章代碼背後1
從程式設計聊起 1
歷史淵源 2
GCC的工作流程 3
1.3.1預編譯 4
1.3.2編譯 5
1.3.3彙編 6
1.3.4連結 7
設計自己的編譯系統 8
本章小結 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
第4章編譯優化147
第5章二進位表示191
第6章彙編器構造219
第7章連接器構造263
參考文獻

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的彙編代碼。