從源頭就優化 - 動手開發自己的編譯器實戰

序言
隨著晶片技術的高速發展，與之伴隨的編譯器開發也迅速增多，但相關的技術資料卻晦澀難懂。編譯器領域由AlfredV.Aho 等著的經典名著《編譯原理》偏重理論，缺少範例，入門難度很高。開放原始碼專案LLVM 和GCC 的程式架構複雜且技術資料多為英文，不太適合初學者入門。作者根據自己對Linux 和C/C++ 的長期使用經驗撰寫了一個簡單編譯器框架（Simple Compiler Framework，SCF），詳細說明一門程式語言的開發過程，為初學者提供了一個編譯器領域的入門途徑。

本書以作者撰寫的SCF 編譯器框架為基礎，以高階語言的編譯連接過程為脈絡，一步步地說明編譯器的架構及其各模組的實現細節。

本書主要內容

第1章主要說明編譯器的發展史、應用場景和程式架構，讓讀者對該領域有個初步印象。
第2章由淺入深地說明詞法分析模組的實現細節，以儘量簡單通俗的方式啟動讀者入門。

第3章拋開了編譯理論，從實踐的角度說明怎麼撰寫語法分析模組，展現把原始程式碼轉換成電腦可以理解的樹形資料結構的過程。該樹形資料結構即通常所講的抽象語法樹。

第4章說明語義分析和運算元多載的支援方法。

第5章是三位址碼的生成，說明怎麼把樹形資料結構變成類似組合語言的線性程式序列。

第6章是基本區塊的劃分，介紹編譯器內部對程式流程的表示方式。

第7章為中間程式最佳化，說明編譯器怎麼生成簡潔高效的程式和怎麼支援自動記憶體管理。

第8章介紹在不同類型的CPU 上怎樣為變數分配暫存器。

第9章詳細講解X86_64 的機器碼生成過程，並簡單描述ARM64 的機器碼生成過程。

第10章以Linux 為平臺說明連接器的撰寫和可執行程式的執行。

第11章說明指令碼語言的位元組碼和虛擬機器。

第12章介紹泛編譯器問題的數學模型及其簡單解法，該章的最後兩句為本書的總綱。

閱讀建議

編譯器屬於電腦領域的核心技術，與作業系統和CPU 指令的連結較多。前4章的閱讀需要熟悉C 語言，第5章之後的章節需要讀者具有一定的組合語言基礎，第10章需要讀者熟悉Linux 系統。

致謝

感謝我的父母，感謝北京清華大學出版社趙佳霓編輯的細心指導，感謝我的所有關注者，正是你們的支持才完成了編譯器程式的開發和本書的撰寫。

由於時間倉促，書中難免存在疏漏之處，請讀者見諒，並提出寶貴意見。
于東亮

序言
隨著晶片技術的高速發展，與之伴隨的編譯器開發也迅速增多，但相關的技術資料卻晦澀難懂。編譯器領域由AlfredV.Aho 等著的經典名著《編譯原理》偏重理論，缺少範例，入門難度很高。開放原始碼專案LLVM 和GCC 的程式架構複雜且技術資料多為英文，不太適合初學者入門。作者根據自己對Linux 和C/C++ 的長期使用經驗撰寫了一個簡單編譯器框架（Simple Compiler Framework，SCF），詳細說明一門程式語言的開發過程，為初學者提供了一個編譯器領域的入門途徑。

本書以作者撰寫的SCF 編譯器框架為基礎，以高階語言的編譯連接過程為脈絡，...

入門篇
第 1 章 編譯器簡介
1.1 程式語言的發展史
1.2 編譯器在IT 產業裡的核心地位
1.3 編譯器的程式架構
第 2 章 詞法分析
2.1 「理想語言」的詞法分析
2.2 實際程式語言的詞法擴充
2.2.1 程式語言的標識符號
2.2.2 關鍵字
2.2.3 數字
2.2.4 資料結構
2.3 詞法分析的數學解釋
第 3 章 語法分析
3.1 敘述類型的劃分
3.2 敘述的巢狀結構和遞迴分析
3.2.1 變數宣告敘述的分析
3.2.2 類型定義敘述的分析
3.2.3 順序區塊的分析
3.2.4 運算式的分析
3.2.5 運算元的優先順序和結合性
3.2.6 運算式樹的建構步驟
3.2.7 完整的抽象語法樹
3.2.8 抽象語法樹的資料結構
3.2.9 變數和類型的資料結構
3.2.10 變數的語法檢查
3.2.11 星號和乘法的區分
3.3 語法的靈活編輯和有限自動機框架
3.3.1 有限自動機的簡介
3.3.2 語法的編輯
3.3.3 程式語言的語法圖
3.3.4 SCF 框架怎麼實現「遞迴」
3.5.5 語法分析框架的模組上下文
3.3.6 for 迴圈的語法分析模組
3.3.7 小括號的多種含義
3.4 語法分析的數學解釋
第 4 章 語義分析
4.1 類型檢查
4.2 語義分析框架
4.2.1 語義分析的回呼函數
4.2.2 語義分析中的遞迴
4.3 運算元多載
4.3.1 運算元多載的實現
4.3.2 函數呼叫
4.3.3 多載函數的查詢
4.3.4 程式實現
4.3.5 SCF 編譯器的類別物件
4.4 new 關鍵字
4.5 多值函數
4.5.1 應用程式二進位介面
4.5.2 語法層面的支援
4.5.3 語義層面的支援
進階篇
第 5 章 三位址碼的生成
5.1 回填技術
5.1.1 回填的資料結構
5.1.2 三位址碼的資料結構
5.1.3 回填的步驟
5.2 if-else 的三位址碼
5.3 迴圈的入口和出口
5.4 指標與陣列的賦值
5.5 new 關鍵字的三位址碼
5.6 跳躍的最佳化
5.6.1 跳躍的最佳化簡介
5.6.2 邏輯運算元的短路最佳化
5.6.3 死程式消除
5.6.4 程式實現
第 6 章 基本區塊的劃分
6.1 比較、跳躍導致的基本區塊劃分
6.2 函數呼叫
6.3 基本區塊的流程圖
第 7 章 中間程式最佳化
7.1 程式框架
7.2 內聯函數
7.3 有向無環圖
7.3.1 公共子運算式
7.3.2 資料結構
7.3.3 有向無環圖的生成
7.4 圖的搜尋演算法
7.4.1 基本區塊的資料結構
7.4.2 寬度優先搜尋
7.4.3 深度優先搜尋
7.5 指標分析
7.5.1 指標解引用的分析
7.5.2 陣列和結構的指標分析
7.6 跨函數的指標分析
7.7 變數活躍度分析
7.7.1 變數的活躍度
7.7.2 單一基本區塊的變數活躍度分析
7.7.3 基本區塊流程圖上的分析
7.7.4 程式實現
7.8 自動記憶體管理
7.9 DAG 最佳化
7.9.1 無效運算
7.9.2 相同子運算式的判斷
7.9.3 出口活躍變數的最佳化
7.9.4 後++ 的最佳化
7.9.5 邏輯運算元的最佳化
7.9.6 DAG 最佳化的程式實現
7.10 迴圈分析
7.10.1 迴圈的辨識
7.10.2 迴圈的最佳化
第 8 章 暫存器分配
8.1 不同CPU 架構的暫存器組
8.2 變數之間的衝突
8.3 圖的著色演算法
8.3.1 簡單著色演算法
8.3.2 改進的著色演算法
第 9 章 機器碼的生成
9.1 RISC 架構的優勢
9.2 暫存器溢位
9.2.1 暫存器的資料結構
9.2.2 暫存器的衝突
9.2.3 暫存器的溢位
9.3 X86_64 的機器碼生成
9.3.1 X86_64 的機器指令
9.3.2 機器碼的生成
9.3.3 目的檔案
9.4 ARM64 的機器碼生成
9.4.1 指令特點
9.4.2 機器碼生成
第 10 章 ELF 格式和可執行程式的連接
10.1 ELF 格式
10.1.1 檔案標頭
10.1.2 節標頭表
10.1.3 程式標頭表
10.1.4 ELF 格式的實現
10.2 連接器
10.2.1 連接
10.2.2 靜態連接
10.2.3 動態連接
10.2.4 編譯器的主流程
10.3 可執行檔的執行
10.3.1 處理程式建立
10.3.2 程式的載入和執行
10.3.3 動態函數庫函數的載入
10.3.4 原始程式碼的編譯、連接、執行
第 11 章 Naja 位元組碼和虛擬機器
11.1 Naja 位元組碼
11.2 虛擬機器
11.2.1 虛擬機器的資料結構
11.2.2 虛擬機器的執行
11.2.3 動態函數庫函數的載入
第 12 章 資訊編碼的數學哲學
12.1 資訊編碼格式的轉換
12.2 多項式時間的演算法
12.3 自然指數e 和梯度下降演算法
12.4 複雜問題的簡單解法

入門篇
第 1 章 編譯器簡介
1.1 程式語言的發展史
1.2 編譯器在IT 產業裡的核心地位
1.3 編譯器的程式架構
第 2 章 詞法分析
2.1 「理想語言」的詞法分析
2.2 實際程式語言的詞法擴充
2.2.1 程式語言的標識符號
2.2.2 關鍵字
2.2.3 數字
2.2.4 資料結構
2.3 詞法分析的數學解釋
第 3 章 語法分析
3.1 敘述類型的劃分
3.2 敘述的巢狀結構和遞迴分析
3.2.1 變數宣告敘述的分析
3.2.2 類型定義敘述的分析
3.2.3 順序區塊的分析
3.2.4 運算式的分析
3.2.5 運算元的優先順序和結合性
3.2.6 運算式樹的建構步驟
3.2.7 完整...