Foreword序
小范從本科畢業(yè)設計開始寫編譯器的實現(xiàn)代碼，為他選擇這個題目的初衷是希望把編譯系統(tǒng)與操作系統(tǒng)、計算機體系結(jié)構相關的結(jié)合點找出來、弄清楚，為教學提供可用的實例。本科畢業(yè)設計結(jié)束時小范完成了一個最簡單的C語言子集的編譯器，生成的匯編程序經(jīng)過匯編和鏈接后可以正確執(zhí)行。研究生期間我們決定繼續(xù)編譯系統(tǒng)實現(xiàn)技術方向的研究工作，主要完成匯編器和鏈接器這兩大模塊。小范用一顆好奇、求知的心指引自己，利用一切可以搜集到的資料，用“日拱一卒”的勁頭一步一步接近目標。每天的日子都可能有不同的“干擾”——名企的實習、發(fā)論文、做項目、參加競賽、考認證，身邊的同學在快速積攢各種經(jīng)歷和成果的時候，小范要保持內(nèi)心的平靜，專注于工作量巨大而是否有回報還未曾可知的事情。三年的時間里，沒有獎學金，沒有項目經(jīng)費，有的是沒完沒了的各種問題，各種要看的書、資料和要完成的代碼，同時還要關注大數(shù)據(jù)平臺、編程語言等新技術的發(fā)展。
“匯編器完成了”“鏈接器完成了”，好消息接踵而至。小范說，“把編譯器的代碼重寫一下，加上代碼優(yōu)化吧？”我說“好”，其實，這個“好”說起來容易，而小范那里增加的工作量可想而知，這絕不是那么輕松的事情。優(yōu)化的基本原理有了，怎么設計算法來實現(xiàn)呢？整個編譯器的文法比本科畢業(yè)設計時擴充了很多。編譯器重寫、增加代碼優(yōu)化模塊、完成匯編器和鏈接器，難度和工作量可想而知。每當小范解決一個問題，完成一個功能，就會非常開心地與我分享。看小范完成的一行行規(guī)范、漂亮的代碼，聽他興奮地講解，很難說與聽郎朗的鋼琴協(xié)奏曲《黃河之子》、德沃夏克的《自新大陸》比哪一個更令人陶醉，與聽交響曲《嘎達梅林》比哪一個更令人震撼。當小范完成鏈接器后，我說：“小范，寫書吧，不寫下來太可惜了�！本瓦@樣，小范再次如一輛嶄新的裝甲車，轟隆前行，踏上了筆耕不輟的征程。2015年暑假，細讀和修改這部30多萬字的書稿，感慨萬千，完成編譯系統(tǒng)的工作量、四年的甘苦與共、超然物外的孤獨都在這字里行間跳躍。寫完這部原創(chuàng)書對一個年輕學生來說是極富挑戰(zhàn)的，但是他完成了，而且完成得如此精致、用心。
小范來自安徽的農(nóng)村，面對生活中的各種困惑、困難，他很少有沮喪、悲觀的情緒，永遠有天然的好奇心，保留著頑童的天真、快樂與坦率。他開始寫本書時23歲，完成全書的初稿時25歲。寫編譯系統(tǒng)和操作系統(tǒng)內(nèi)核并非難以企及，只是需要一份淡然、專注和堅持。
如果你想了解計算機是如何工作的，為什么程序會出現(xiàn)不可思議的錯誤？高級語言程序是如何被翻譯成機器語言代碼的？編譯器在程序的優(yōu)化方面能做哪些工作？軟件和硬件是怎么結(jié)合工作的？各種復雜的數(shù)據(jù)結(jié)構和算法，包括圖論在實現(xiàn)編譯系統(tǒng)時如何應用？有限自動機在詞法分析中的作用是什么？其程序又如何實現(xiàn)？那么本書可以滿足你的好奇心和求知欲。如何實現(xiàn)編譯系統(tǒng)？如何實現(xiàn)編譯器？如何實現(xiàn)匯編器？如何使用符號表？如何結(jié)合操作系統(tǒng)加載器的需要實現(xiàn)鏈接器？Intel的指令是如何構成的？如何實現(xiàn)不同的編譯優(yōu)化算法？對這些問題，本書結(jié)合作者實現(xiàn)的代碼實例進行了詳盡的闡述，對提高程序員的專業(yè)素質(zhì)有實際的助益，同時本書也可以作為計算機科學相關專業(yè)教師的參考書和編譯原理實習類課程的教材。
2013年在新疆參加全國操作系統(tǒng)和組成原理教學研討會時，我?guī)е蛴〕鰜淼膬烧聲褰o了機械工業(yè)出版社的溫莉芳老師，與她探討這本書出版的意義和可行性，她給了我們很大的鼓勵和支持，促成了本書的完成。在此，特別感謝溫莉芳老師。
本書的責任編輯佘潔老師與作者反復溝通，對本書進行了認真、耐心的編輯，感謝她的辛勤付出。
中國石油大學（華東）的李村合老師在編譯器設計的初期給予了我們指導和建議。馬力老師在繁忙的工作之余，認真審閱書稿，給出了詳細的修改意見。王小云、程堅、梁紅衛(wèi)、葛永文老師對本書提出了他們的意見，并給出了認真的評價。趙國梁同學對書中的代碼和文字做了細心的校對。在此，對他們表示衷心的感謝。最后要感謝小范勤勞、堅韌的爸爸媽媽，是他們一直給予他無私的支持和持續(xù)的鼓勵。
感恩所有給予我們幫助和鼓勵的老師、同學和朋友！
張瓊聲
2016年春于北京
Preface前 言
本書適合誰讀
本書是一本描述編譯系統(tǒng)實現(xiàn)的書籍。這里使用“編譯系統(tǒng)”一詞，主要是為了與市面上描述編譯器實現(xiàn)的書籍進行區(qū)分。本書描述的編譯系統(tǒng)不僅包含編譯器的實現(xiàn)，還包括匯編器、鏈接器的實現(xiàn)，以及機器指令與可執(zhí)行文件格式的知識。因此，本書使用“編譯系統(tǒng)”一詞作為編譯器、匯編器和鏈接器的統(tǒng)稱。
本書的目的是希望讀者能通過閱讀本書清晰地認識編譯系統(tǒng)的工作流程，并能自己嘗試構造一個完整的編譯系統(tǒng)。為了使讀者更容易理解和學習編譯系統(tǒng)的構造方法，本書將描述的重點放在編譯系統(tǒng)的關鍵流程上，并對工業(yè)化編譯系統(tǒng)的實現(xiàn)做了適當?shù)暮喕�。如果讀者對編譯系統(tǒng)實現(xiàn)的內(nèi)幕感興趣，或者想自己動手實現(xiàn)一個編譯系統(tǒng)的話，本書將非常適合你閱讀。
閱讀本書，你會發(fā)現(xiàn)書中的內(nèi)容與傳統(tǒng)的編譯原理教材以及描述編譯器實現(xiàn)的書籍有所不同。本書除了描述一個編譯器的具體實現(xiàn)外，還描述了一般書籍較少涉及的匯編器和鏈接器的具體實現(xiàn)。而且本書并非“紙上談兵”，在講述每個功能模塊時，書中都會結(jié)合具體實現(xiàn)代碼來闡述模塊功能的實現(xiàn)。通過本書讀者將會學習如何使用有限自動機構造詞法分析器，如何將文法分析算法應用到語法分析過程，如何使用數(shù)據(jù)流分析進行中間代碼的優(yōu)化，如何生成合法的匯編代碼，如何產(chǎn)生二進制指令信息，如何在鏈接器內(nèi)進行符號解析和重定位，如何生成目標文件和可執(zhí)行文件等。
本書的宗旨是為意欲了解或親自實現(xiàn)編譯系統(tǒng)的讀者提供指導和幫助。尤其是計算機專業(yè)的讀者，通過自己動手寫出一個編譯系統(tǒng)，能加強讀者對計算機系統(tǒng)從軟件層次到硬件層次的理解。同時，深入挖掘技術幕后的秘密也是對專業(yè)興趣的一種良好培養(yǎng)。GCC本身是一套非常完善的工業(yè)化編譯系統(tǒng)（雖然我們習慣上稱它為編譯器），然而單憑個人之力無法做到像GCC這樣完善，而且很多時候是沒有必要做出一個工程化的編譯器的。本書試圖幫助讀者深入理解編譯的過程，并能按照書中的指導實現(xiàn)一個能正常工作的編譯器。在自己親自動手實現(xiàn)一個編譯系統(tǒng)的過程中，讀者獲得的不僅僅是軟件開發(fā)的經(jīng)歷。在開發(fā)編譯系統(tǒng)的過程中，讀者還會學習很多與底層相關的知識，而這些知識在一般的專業(yè)教材中很少涉及。
如果讀者想了解計算機程序底層工作的奧秘，本書能夠解答你內(nèi)心的疑惑。如果讀者想自定義一種高級語言，并希望使該語言的程序在計算機上正常運行，本書能幫助你較快地達到目的。如果讀者想從實現(xiàn)一個編譯器的過程中，加強對編譯系統(tǒng)工作流程的理解，并嘗試深入研究GCC源碼，本書也能為你提供很多有價值的參考。
基礎知識儲備
本書盡可能地不要求讀者有太多的基礎知識準備，但是編譯理論屬于計算機學科比較深層次的知識領域，難免對讀者的知識儲備有所要求。本書的編譯系統(tǒng)是基于Linux x86平臺實現(xiàn)的，因此要求讀者對Linux環(huán)境的C/C++編程有所了解。另外，理解匯編器的實現(xiàn)內(nèi)容需要讀者對x86的匯編指令編程比較熟悉。本書不會描述過多編譯原理教材中涉及的內(nèi)容，所以要求讀者具備編譯原理的基礎知識。不過讀者不必過于擔心，本書會按照循序漸進的方式描述編譯系統(tǒng)的實現(xiàn)，在具體的章節(jié)中會將編譯系統(tǒng)實現(xiàn)的每個細節(jié)以及所需的知識闡述清楚。
本書內(nèi)容組織
本書共7章，各章的主要內(nèi)容分別如下。
第1章代碼背后
從程序設計開始，追溯代碼背后的細節(jié)，引出編譯系統(tǒng)的概念。
第2章編譯系統(tǒng)設計
按照編譯系統(tǒng)的工作流程，介紹本書編譯系統(tǒng)的設計結(jié)構。
第3章編譯器構造
描述如何使用有限自動機識別自定義高級語言的詞法記號，如何使用文法分析算法識別程序的語法模塊，如何對高級語言上下文相關信息進行語義合法性檢查，如何使用語法制導翻譯進行代碼生成，以及編譯器工作時符號信息的管理等。
第4章編譯優(yōu)化
介紹中間代碼的設計和生成，如何利用數(shù)據(jù)流分析實現(xiàn)中間代碼優(yōu)化，如何對變量進行寄存器分配，目標代碼生成階段如何使用窺孔優(yōu)化器對目標代碼進行優(yōu)化。
第5章二進制表示
描述Intel x86指令的基本格式，并將AT&T匯編與Intel匯編進行對比。描述ELF文件的基本格式，介紹ELF文件的組織和操作方法。
第6章匯編器構造
描述匯編器詞法分析和語法分析的實現(xiàn)，介紹匯編器如何提取目標文件的主要表信息，并描述x86二進制指令的輸出方法。
第7章鏈接器構造
介紹如何為可重定位目標文件的段進行地址空間分配，描述鏈接器符號解析的流程，以及符號地址的計算方法，并介紹重定位在鏈接器中的實現(xiàn)。
隨書源碼
本書實現(xiàn)的編譯系統(tǒng)代碼已經(jīng)托管到github，源碼可以使用GCC 5.2.0編譯通過。代碼的github地址是https://github.com/fanzhidongyzby/cit。代碼分支x86實現(xiàn)了基于Intel x86體系結(jié)構的編譯器、匯編器和鏈接器，編譯系統(tǒng)生成的目標文件和可執(zhí)行文件都是Linux下標準的ELF文件格式。代碼分支arm實現(xiàn)了基于ARM體系結(jié)構的編譯器，目前支持生成ARM 7的匯編代碼。
機工授權書
范志東 就職于騰訊數(shù)據(jù)平臺部，負責騰訊大數(shù)據(jù)平臺的產(chǎn)品化，涉及自動化部署、應用調(diào)度、交互分析、集群監(jiān)控、性能調(diào)優(yōu)等，對開源工具Ambari、Hadoop、Spark等有深入的了解。在校期間屢次獲得國家獎學金和勵志獎學金。獨立開發(fā)了基于Intel x86指令集的自定義類C語言的編譯系統(tǒng)，包括編譯器、匯編器與鏈接器的實現(xiàn)，對計算機程序的加載和運行原理有深刻的認識。深入分析過Linux內(nèi)核關于CPU功耗方面的代碼。愛好廣泛，對編程語言、操作系統(tǒng)、編譯系統(tǒng)、計算機安全、分布式系統(tǒng)有著濃厚的興趣。閑暇時會在技術博客上分享自己的學習心得，期望通過互聯(lián)網(wǎng)把獲得知識的快樂心情傳遞出去。參與了“十一五”校級立項正式出版教材《計算機操作系統(tǒng)原理》以及全國自學考試教材《計算機應用技術》編寫的相關工作。
張瓊聲 湖北省松滋縣人，中國石油大學（華東）計算機與通信工程學院副教授，碩士生導師。主講課程:《操作系統(tǒng)》《操作系統(tǒng)課程實習》和《嵌入式操作系統(tǒng)》。主持的《計算機操作系統(tǒng)》課程被評為校級精品課，先后獲得中國石油大學優(yōu)秀教學研究成果一、二、三等獎各一項；曾獲評中國石油大學優(yōu)秀教師、山東省優(yōu)秀學士論文指導教師；主持或參與科研、教研項目十四項。專業(yè)及研究興趣為系統(tǒng)軟件開發(fā)技術，包括：操作系統(tǒng)、編譯系統(tǒng)、計算機系統(tǒng)安全性。發(fā)表科研、教學論文二十余篇。參與翻譯《深入理解Linux內(nèi)核》第3版，編著“十一五”校級立項正式出版教材《計算機操作系統(tǒng)原理》、主編全國自學考試教材《計算機應用技術》。
新書資訊