內容簡介

　　本書以作者實現的一個基於Intelx86指令集的編譯係統為例，結閤程序代碼的主要部分詳細闡述瞭編譯係統的實現原理和過程。本書對編譯器、匯編器、鏈接器、編譯優化器涉及的關鍵算法、數據結構和程序實現流程，以及ELF文件的格式、Intel指令格式均作瞭詳細的說明，並結閤大量的圖錶，展示瞭編譯係統工作過程中代碼信息的流動和存儲格式的變化。是一本“手把手”教讀者實現編譯係統的貼心手冊。

作者簡介

範誌東　就職於騰訊數據平颱部，負責騰訊大數據平颱的産品化，涉及自動化部署、應用調度、交互分析、集群監控、性能調優等，對開源工具Ambari、Hadoop、Spark等有深入的瞭解。在校期間屢次獲得國傢奬學金和勵誌奬學金。獨立開發瞭基於Intel x86指令集的自定義類C語言的編譯係統，包括編譯器、匯編器與鏈接器的實現，對計算機程序的加載和運行原理有深刻的認識。深入分析過Linux內核關於CPU功耗方麵的代碼。愛好廣泛，對編程語言、操作係統、編譯係統、計算機安全、分布式係統有著濃厚的興趣。閑暇時會在技術博客上分享自己的學習心得，期望通過互聯網把獲得知識的快樂心情傳遞齣去。參與瞭“十一五”校級立項正式齣版教材《計算機操作係統原理》以及全國自學考試教材《計算機應用技術》編寫的相關工作。

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

精彩書評

愛因斯坦曾說過：“好奇心是科學工作者産生無窮的毅力和耐心的源泉。”
對於實現一個編譯係統來說，打通編譯、匯編和鏈接的全部流程確非易事。然而，當我滿懷新奇地將問題抽絲剝繭，最終觸及本質的那一刻，纔體會到所有的堅持和努力都是值得的。那些抱著和我當初一樣好奇心的人，想必也是為瞭解開心中長埋的疑惑而翻開此書的吧。從對程序語言在計算機上如何運行的不解，到看到自己設計的程序語言執行齣正確結果的興奮，也許隻有好奇心纔能驅使我們在這條看似枯燥的探索道路上一步一個腳印地走下去。最後套用一句名言：“Stay curious, Stay patient.”希望看到本書的人，能找到心中一直想要的答案。
——範誌東

本書介紹編譯器設計與實現中的理論和技術，對構造編譯器的基本知識與關鍵技術進行瞭全新的講解，受眾主要是計算機相關專業的本科生和研究生，以及需要相關知識的程序員，也可以作為教師的參考書。這是近年來在該領域比較全麵的一本專業書籍。
—— 葛永文
科銳安網絡公司全球副總裁兼大中國區總裁

本書*大的亮點是它具有很強的應用性和可讀性。作者不是從復雜深奧的計算機編譯理論入手，而是在各個章節中使用有代錶性的程序模塊作為範例，將它們放入編譯係統中運行以描述它們的編譯過程，然後對代碼和結果給齣詳細的詮釋。 這就像對編譯過程進行細緻解剖一樣。我相信本書會大大降低編譯係統理解的門檻，提高讀者對編譯係統的興趣。
—— 梁紅衛
南京大學少年班本科
中科院自動化所碩士
佐治亞理工學院PHD
定居美國，現就職於Maxim 集成芯片公司

本書知識量很大，作者敘述清晰。基於作者完整實現編譯係統的*一手經驗和體會，本書集閤瞭所有的主要步驟，對編譯原理課堂項目的選題、編程具有非常好的藉鑒作用。完整的可運行示例代碼使得專注於編譯係統的一個特定模塊的課堂項目實踐更加真實。本書將有力地促進編譯原理的實踐教學。
—— Jian Cheng (程堅)
CEO, Analytic Measures Inc., Palo Alto, California, USA

正如作者在前言中所言，這本書既能幫助讀者在學習編譯原理時通過閱讀分析這些代碼從而加深理解，也能讓有興趣的讀者在此基礎上進一步進行實踐。即便對普通的計算機編程人員而言，通過本書也能瞭解到不同方麵的東西。就我個人而言，雖然熟知優化過程中的那些概念，但*一次看到瞭那些方法的具體實現仍讓我很高興。尤其是寄存器分配一節，讓我更加理解瞭程序的局部性原則。總之，這是一本值得擁有的好書。
—— 王曉雲
前Nokia高級軟件架構師

目錄

序
前言
第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
參考文獻

前言/序言

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

學習一下編譯器相關的東西，更好寫代碼

應該不錯，一起湊單滿減的。

專業書籍，很好！！！！！！

書很好，打摺下來還是很便宜的

吾消費京東商城數年，深知各産品琳琅滿目。然，唯此寶物與眾皆不同，為齣淤泥之清蓮。使吾為之動容，心馳神往，以至茶飯不思，寢食難安，輾轉反側無法忘懷。於是乎緊衣縮食，湊齊銀兩，傾吾之所有而能買。東哥之熱心、快遞員之殷切，無不讓人感激涕零，可謂迅雷不及掩耳盜鈴兒響叮當仁不讓世界充滿愛。待打開包裹之時，頓時金光四射，屋內升起七彩祥雲，處處皆是祥和之氣。吾驚訝之餘甚是欣喜若狂，嗚呼哀哉！此寶乃是天上物，人間又得幾迴求！遂沐浴更衣，焚香禱告後與人共賞此寶。人皆贊嘆不已，故生此寶物款型及做工，超高性價比之慨，且贊吾獨具慧眼與時尚品位。産品介紹果然句句實言，毫無誇大欺瞞之嫌。實乃大傢之風範，忠義之商賈。

聽說發錶評論，可以領京豆

還行

詞法分析寫齣來瞭，語法分析器那章寫的都是#？

雙十一買的，支持一下這樣的技術內容，有時間好好學習^_^