編譯器的代碼架構

編譯器，是把高級語言轉化爲機器語言的工具軟件。

高級語言的代碼也是個文本字符串，所以編譯器的前端與 sed、gawk、grep 是差不多的，都是廣義上的字符串匹配。

編譯器把代碼轉化爲機器碼的過程如下：

1，詞法分析，

這是編譯器裏最簡單的模塊。

詞法分析，就是通過查看下一個字符來確定怎麼把代碼字符串分割成一個個的語法詞彙。

起始符、終止符，是詞法分析的主要概念。

int day = 24 * 3600;

這行代碼的第 1 個詞是 int，起始符是 i，終止符是空格。

在詞法分析時它是一個標誌符，也就是字母、下劃線、數字組成的一個字符串，必須以字母或下劃線開頭。

在分析出 int 這個標誌符之後，它後面的空格就沒用了，直接丟棄它。

第 2 個詞 day 也是一個標誌符，起始符是 d，終止符也是空格。

習慣把代碼寫得密集的人可能這麼寫：int day=24*3600;

這時 day 的終止符是 =，它同時還是下一個詞的起始符，在把 day 加入詞彙序列之後需要從 = 開始接着分析。

第 3 個詞是 =，第 4 個詞是 24，第 5 個詞是 *，第 6 個詞是 3600，第 7 個詞是分號;

在詞法分析時要把數字字符串 24 和 3600 轉化爲整數 24 和 3600，這兩個在程序裏是不同的。

10 進制、16 進制、8 進制、2 進制、浮點數的支持，都是詞法分析時的任務。

另外，轉義字符串也要在這裏支持。

'\0' 在源代碼裏是字符串文本，包含着 4 個字符'\ 0'，要轉義成單個字符 0。

'\r' '\n' '\t'的處理和'\0'一樣。

詞法分析還是很好寫的。

2，語法分析，

這是編譯器前端最難寫的模塊，它需要把源代碼轉化成一棵描述整個程序結構的多叉樹。

這個多叉樹叫做抽象語法樹（英文縮寫 AST）。

類型、變量、運算符、函數定義、函數調用、if 語句、for/while 循環，都是這個這棵樹的一部分。

抽象語法樹的層次結構，與源代碼的結構是一樣的。

如果是這樣的源代碼的話：

int sum = 0;

for (int i = 0; i < 8; i++) {

if (i % 2 == 0)

sum += i;

}

那麼語法樹是這樣的：

語法樹

初始化語句 sum = 0 與後續的 for 循環是順序執行的，它們屬於同一個順序塊，在語法樹上有同一個父節點。

for 循環有 4 個子節點：初始化表達式 i = 0，條件 i < 8，循環體 if 語句、更新表達式 i++。

其中循環體又是個 if 語句，具有 2 個子節點：條件表達式 i % 2 == 0，主體 sum += i。

while 循環的結構與 for 類似，只要去掉初始化表達式和更新表達式就行，只有 2 個節點。

把詞法分析之後的詞彙序列轉化成抽象語法樹時，常用的方法是有限自動機。

也可以把代碼直接寫成遞歸函數調用，但是後續改起語法來就比較麻煩。

我一開始就是把 scf 的 parse 模塊寫成了遞歸函數調用，後來爲了可以編輯語法，又自己做了個簡單的有限自動機。

3，語義分析，

把語法樹遍歷一遍，檢查一下類型是否匹配，就是語義分析。

如果要支持面向對象的話，就可以在這裏進行函數重載和運算符重載。

常量表達式也要在這裏計算出來，int day = 24 *3600 要轉化成 day = 86400。

常量表達式的計算

對語法樹進行遍歷時，不同的語法節點使用的處理函數是不同的，這就是語義。

符號 = 要當作賦值，符號 + 要當作加法，其他類似。

C 語言裏常見的函數調用，語法樹是這樣的：

int printf(const char* fmt, ...);

int main()

{

printf("hello world\n");

}

函數調用也是一個運算符，具有一個單獨的語法節點，它的子節點都是它的參數：

其中函數名也是一個參數，要轉化爲對應的函數體的節點的指針。

通過這個指針纔可以找到函數的代碼，進行內聯優化（inline）。

函數調用和定義

如果要是調用的外部函數，只有聲明沒有實現，那就沒法內聯了。

4，中間代碼生成（三地址碼），從這裏開始就是編譯器的後端了。

這一步也是對語法樹進行遍歷，把對應的表達式、函數、if 語句、for 循環都變成類似彙編的三地址碼。

上面那段 for 循環，這時會被變成如下的三地址碼序列：

assign sum, 0

assign i, 0

start: // for 循環的開頭

cmp i, 8

jge end // 條件不成立，則結束循環

assign t, i % 2 // t 是編譯器生成的臨時變量

cmp t, 0

jne next

add sum, sum, i // 這行纔是三地址碼

next: // 下一輪 for 循環

inc i // 循環變量 + 1

jmp start // 跳轉回開頭，繼續循環

end：// for 循環結束

到了這裏，那個複雜的樹型結構已經變成線形結構了，可以按順序寫到一個文本文件裏，這就是彙編代碼。

到這裏，編譯器就可以生成類似 gcc -S 的彙編代碼了。

5，中間代碼優化，

這是編譯器後端的主要部分，屬於機器無關優化，這部分的優化是不依賴於 CPU 平臺的。

scf 框架的這部分包含以下功能：

1）內聯函數，

2）有向無環圖 DAG 的生成，

3）帶二級指針參數的函數調用分析，

4）指針別名分析，也就是分析指針指向的變量，

5）活躍變量分析，

6）變量的加載保存分析，

7）需要自動內存管理的變量分析，

8）代碼流程圖的深度優先排序，

9）自動內存管理代碼的添加，

10）基本塊內的優化，

11）循環分析，

會把一些變量儘量在循環的入口加載，在循環出口保存，減少循環內的內存讀寫。

沒有常量傳播的優化，哪天有空我把它添上

6，寄存器分配，

使用圖的着色算法，之前的文章寫過。

7，指令選擇，

直接寫在代碼裏的，沒做龍書裏提到的那個樹的覆蓋。

8，機器碼生成，

根據 intel x64 的手冊編寫機器碼就行。

9，目標文件生成，

也就是 gcc -c 得到那個. o 文件。

Linux 上的 elf 文件是什麼樣的就怎麼寫，可以參考 linux 的 man 手冊裏對 elf 的講解。

10，可執行文件的生成，

這是連接器的功能，它把多個. o .a .so 文件連接成一個可執行文件。

這一步的代碼在 scf/elf 目錄，有興趣的可以看看。

連接之後的文件就可以在 shell 命令行裏運行了。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/gKdfFH9n1AUF3LUt3C54Cw