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