徹底理解編譯器工作原理

對於程序員來說編譯器是非常熟悉的，每天都在用，但是當你在點擊 “Run” 這個按鈕或者執行編譯命令時你知道編譯器是怎樣工作的嗎？

這篇文章就爲你解答這個問題。

編譯器就是一個普通程序，沒什麼大不了的

什麼是編譯器？

編譯器是一個將高級語言翻譯爲低級語言的程序。

首先我們一定要意識到編譯器就是一個普通程序，沒什麼大不了的。

在沒有弄明白編譯器如何工作之前你可以簡單的把編譯器當做一個黑盒子，其作用就是輸入一個文本文件輸出一個二進制文件。

圖片

基本上編譯器經過了以下幾個階段，等等，這句話教科書上也有，但是我相信很多同學其實並沒有真正理解這幾個步驟到底在說些什麼，爲了讓你徹底理解這幾個步驟，我們用一個簡單的例子來講解。

假定我們有一段程序：

while (y < z) {
int x = a + b;
y += x;
}

那麼編譯器是怎樣把這一段程序人類認識的程序轉換爲 CPU 認識的二進制機器指令呢？

提取出每一個單詞：詞法分析

首先編譯器要把源代碼中的每個 “單詞” 提取出來，在編譯技術中 “單詞” 被稱爲 token。其實不只是每個單詞被稱爲一個 token，除去單詞之外的比如左括號、右括號、賦值操作符等都被稱爲 token。

從源代碼中提取出 token 的過程就被稱爲詞法分析，Lexical Analysis。

經過一遍詞法分析，編譯器得到了以下 token：

T_While      while
T_LeftParen   （
T_Identifier   y
T_Less         <
T_Identifier   z
T_RightParen   )
T_OpenBrace    {
T_Int         int
T_Identifier   x
T_Assign       =
T_Identifier   a
T_Plus         +
T_Identifier   b
T_Semicolon    ;
T_Identifier   y
T_PlusAssign   +=
T_Identifier   x
T_Semicolon    ;
T_CloseBrace   }

就這樣一個磁盤中保存的字符串源代碼文件就轉換爲了一個個的 token。

這些 token 想表達什麼意思：語法分析

有了這些 token 之後編譯器就可以根據語言定義的語法恢復其原本的結構，怎麼恢復呢？

圖片

原來，編譯器在掃描出各個 token 後根據規則將其用樹的形式表示出來，這顆樹就被稱爲語法樹。

語法樹是不是合理的：語義分析

有了語法樹後我們還要檢查這棵樹是不是合法的，比如我們不能把一個整數和一個字符串相加、比較符左右兩邊的數據類型要相同，等等。

這一步通過後就證明了程序合法，不會有編譯錯誤。

圖片

根據語法樹生成中間代碼：代碼生成

語義分析之後接下來編譯器遍歷語法樹並用另一種形式來表示，用什麼來表示呢？那就是中間代碼，intermediate representation code，簡稱 IR code。

上述語法樹可能就會表示爲這樣的中間代碼：

Loop: x   = a + b
      y   = x + y
      _t1 = y < z
      if _t1 goto Loop

怎麼樣，這實際上已經比較接近最後的機器指令了。

只不過這還不是最終形態。

中間代碼優化

在生成中間代碼後要對其進行優化，我們可以看到，實際上可以把 x = a + b 這行代碼放到循環外，因爲每次循環都不會改變 x 的值，因此優化後就是這樣了：

x   = a + b
Loop: y   = x + y
_t1 = y < z
if _t1 goto Loop

中間代碼優化後就可以生成機器指令了。

代碼生成

將上述優化後的中間代碼轉換爲機器指令：

add $1, $2, $3
Loop: add $4, $1, $4
      slt $6, $1, $5
      beq $6, loop

最終，編譯器將程序員認識的代碼轉換爲了 CPU 認識的機器指令。

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