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

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章 代碼背後

<a href="https://yq.aliyun.com/articles/81953" target="_blank">1.1 從程式設計聊起</a>

<a href="https://yq.aliyun.com/articles/81956" target="_blank">1.2 曆史淵源</a>

<a href="https://yq.aliyun.com/articles/81960" target="_blank">1.3 gcc的工作流程</a>

<a href="https://yq.aliyun.com/articles/81962" target="_blank">1.3.1 預編譯</a>

<a href="https://yq.aliyun.com/articles/81963" target="_blank">1.3.2 編譯</a>

<a href="https://yq.aliyun.com/articles/81965" target="_blank">1.3.3 彙編</a>

<a href="https://yq.aliyun.com/articles/81969" target="_blank">1.3.4 連結</a>

<a href="https://yq.aliyun.com/articles/81972" target="_blank">1.4 設計自己的編譯系統</a>

<a href="https://yq.aliyun.com/articles/81975" target="_blank">1.5 本章小結</a>

第2章 編譯系統設計

<a href="https://yq.aliyun.com/articles/81978" target="_blank">2.1 編譯程式的設計</a>

<a href="https://yq.aliyun.com/articles/81981" target="_blank">2.1.1 詞法分析</a>

<a href="https://yq.aliyun.com/articles/81984" target="_blank">2.1.2 文法分析</a>

<a href="https://yq.aliyun.com/articles/81989" target="_blank">2.1.3 符号表管理</a>

<a href="https://yq.aliyun.com/articles/81992" target="_blank">2.1.4 語義分析</a>

<a href="https://yq.aliyun.com/articles/81993" target="_blank">2.1.5 代碼生成</a>

<a href="https://yq.aliyun.com/articles/81995" target="_blank">2.1.6 編譯優化</a>

<a href="https://yq.aliyun.com/articles/81998" target="_blank">2.2 x86指令格式</a>

<a href="https://yq.aliyun.com/articles/82001" target="_blank">2.3 elf檔案格式</a>

<a href="https://yq.aliyun.com/articles/82005" target="_blank">2.4 彙程式設計式的設計</a>

<a href="https://yq.aliyun.com/articles/82007" target="_blank">2.4.1 彙編詞法、文法分析</a>

<a href="https://yq.aliyun.com/articles/82009" target="_blank">2.4.2 表資訊生成</a>

<a href="https://yq.aliyun.com/articles/82011" target="_blank">2.4.3 指令生成</a>

<a href="https://yq.aliyun.com/articles/82013" target="_blank">2.5 連結程式的設計</a>

<a href="https://yq.aliyun.com/articles/82017" target="_blank">2.5.1 位址空間配置設定</a>

<a href="https://yq.aliyun.com/articles/82020" target="_blank">2.5.2 符号解析</a>

<a href="https://yq.aliyun.com/articles/82023" target="_blank">2.5.3 重定位</a>

<a href="https://yq.aliyun.com/articles/82027" target="_blank">2.6 本章小結</a>

第3章 編譯器構造

3.1 詞法分析

3.1.1 掃描器

3.1.2 詞法記号

3.1.3 有限自動機

3.1.4 解析器

3.1.5 錯誤處理

3.2 文法分析

3.2.1 文法定義

3.2.2 遞歸下降子程式

3.2.3 錯誤處理

3.3 符号表管理

3.3.1 符号表資料結構

3.3.2 作用域管理

3.3.3 變量管理

3.3.4 函數管理

3.4 語義分析

3.4.1 聲明與定義語義檢查

3.4.2 表達式語義檢查

3.4.3 語句語義檢查

3.4.4 錯誤處理

3.5 代碼生成

3.5.1 中間代碼設計

3.5.2 程式運作時存儲

3.5.3 函數定義與return語句翻譯

3.5.4 表達式翻譯

3.5.5 複合語句與break、continue

語句翻譯

3.5.6?目标代碼生成

3.5.7 資料段生成

3.6 本章小結

第4章 編譯優化

4.1 資料流分析

4.1.1 流圖

4.1.2 資料流分析架構

4.2 中間代碼優化

4.2.1 常量傳播

4.2.2 複寫傳播

4.2.3 死代碼消除

4.3 寄存器配置設定

4.3.1 圖着色算法

4.3.2 變量棧幀偏移計算

4.4 窺孔優化

4.5 本章小結

第5章 二進制表示

5.1 x86指令

5.1.1 指令字首

5.1.2 操作碼

5.1.3 modr/m字段

5.1.4 sib字段

5.1.5 偏移

5.1.6 立即數

5.1.7 at&amp;t彙編格式

5.2 elf檔案

5.2.1 檔案頭

5.2.2 段表

5.2.3 程式頭表

5.2.4 符号表

5.2.5 重定位表

5.2.6 串表

5.3 本章小結

第6章 彙編器構造

6.1 詞法分析

6.1.1 詞法記号

6.1.2 有限自動機

6.2 文法分析

6.2.1 彙編語言程式

6.2.2 資料定義

6.2.3 指令

6.3 符号表管理

6.3.1 資料結構

6.3.2 符号管理

6.4 表資訊生成

6.4.1 段表資訊

6.4.2 符号表資訊

6.4.3 重定位表資訊

6.5 指令生成

6.5.1?雙操作數指令

6.5.2?單操作數指令

6.5.3 零操作數指令

6.6 目标檔案生成

6.7 本章小結

第7章 連結器構造

7.1 資訊收集

7.1.1 目标檔案資訊

7.1.2 段資料資訊

7.1.3 符号引用資訊

7.2 位址空間配置設定

7.3 符号解析

7.3.1 符号引用驗證

7.3.2 符号位址解析

7.4 重定位

7.5 程式入口點與運作時庫

7.6 可執行檔案生成

7.7 本章小結

參考文獻