人人都能讀懂的編譯器原理
程式語言是怎樣工作的
理解編譯器內部原理，可以讓你更高效利用它。按照編譯的工作順序，逐步深入程式語言和編譯器是怎樣工作的。本文有大量的連結、樣例程式碼和圖表幫助你理解編譯器。
作者注：
這是我在 Medium 上的第二篇文章的再版， ofollow,noindex">上一版 有超過 21000 的閱讀量。很高興我能夠幫助到各位的學習， 因此我根據上一版的評論，完完全全重寫了。
我選擇 Rust 作為這篇文章的主要語言。它是一種詳盡的、高效的、現代的而且看起來特意使得設計編譯器變得簡單。我很喜歡使用它。 https://www.rust-lang.org/
寫這篇文章的目的主要是吸引讀者的注意力，而不是提供 20 多頁的令人頭皮發麻的閱讀材料。對於那些你感興趣的更深層次的話題，文章中有許多連結會引導你找到相關的資料。大多數連結到維基百科 。
感謝你的關注，我希望你能夠喜歡這些我花費了超過 20 個小時的寫出的文章。歡迎在文章底部評論處留下任何問題或者建議。
簡單介紹
編譯器是什麼？
你口中所說的程式語言本質上只是一個軟體，這個軟體叫做編譯器，編譯器讀入一個文字檔案，經過大量的處理，最終產生一個二進位制檔案。編譯器的語言部分就是它處理的文字樣式。因為電腦只能讀取 1 和 0 ，而人們編寫 Rust 程式要比直接編寫二進位制程式簡單地多，因此編譯器就被用來把人類可讀的文字轉換成計算機可識別的機器碼。
編譯器可以是任何可以把文字檔案轉換成其他檔案的程式。例如，下面有一個用 Rust 語言寫的編譯器把 0 轉換成 1，把 1 轉換成 0 ：
// An example compiler that turns 0s into 1s, and 1s into 0s.
fn main() {
let input = "1 0 1 A 1 0 1 3";
// iterate over every character `c` in input
let output: String = input.chars().map(|c|
if c == '1' { '0' }
else if c == '0' { '1' }
else { c } // if not 0 or 1, leave it alone
).collect();
println!("{}", output); // 0 1 0 A 0 1 0 3
}
編譯器是做什麼的？
簡言之，編譯器獲取原始碼，產生一個二進位制檔案。因為從複雜的、人類可讀的程式碼直接轉化成0/1二進位制會很複雜，所以編譯器在產生可執行程式之前有多個步驟：
- 從你給定的原始碼中讀取單個詞。
- 把這些詞按照單詞、數字、符號、運算子進行分類。
- 通過模式匹配從分好類的單詞中找出運算子，明確這些運算子想進行的運算，然後產生一個運算子的樹（表示式樹）。
- 最後一步遍歷表示式樹中的所有運算子，產生相應的二進位制資料。
儘管我說編譯器直接從表示式樹轉換到二進位制，但實際上它會產生彙編程式碼，之後彙編程式碼會被彙編/編譯到二進位制資料。彙編程式就好比是一種高階的、人類可讀的二進位制。更多關於組合語言的閱讀資料在 這裡 。
直譯器是什麼？
直譯器 非常像編譯器，它也是讀入程式語言的程式碼，然後處理這些程式碼。儘管如此， 直譯器會跳過了程式碼生成，然後 即時編譯 並執行 AST。 直譯器最大的優點就在於在你 debug 期間執行程式所消耗的時間。編譯器編譯一個程式可能在一秒到幾分鐘不等，然而直譯器可以立即開始執行程式，而不必編譯。直譯器最大的缺點在於它必須安裝在使用者電腦上，程式才可以執行。
雖然這篇文章主要是關於編譯器的，但是對於編譯器和直譯器之間的區別和編譯器相關的內容一定要弄清楚。
1. 詞法分析
第一步是把輸入一個詞一個詞的拆分開。這一步被叫做 詞法分析 ,或者說是分詞。這一步的關鍵就在於 我們把字元組合成我們需要的單詞、識別符號、符號等等。 詞法分析大多都不需要處理邏輯運算像是算出 2+2 – 其實這個表示式只有三種 標記 ：一個數字： 2 ,一個加號，另外一個數字： 2 。
讓我們假設你正在解析一個像是 12+3 這樣的字串：它會讀入字元 1 ， 2 ， + ，和 3 。我們已經把這些字元拆分開了，但是現在我們必須把他們組合起來；這是分詞器的主要任務之一。舉個例子，我們得到了兩個單獨的字元 1 和 2 ，但是我們需要把它們放到一起，然後把它們解析成為一個整數。至於 + 也需要被識別為加號，而不是它的字元值 – 字元值是43 。
如果你可以閱讀過上面的程式碼，並且弄懂了這樣做的含義，接下來的 Rust 分詞器會組合數字為32位整數，加號就最後了標記值 Plus（加）.
你可以點選 Rust playgroud 左上角的 “Run” 按鈕來編譯和執行你瀏覽器中的程式碼。
在一種程式語言的編譯器中，詞法解析器可能需要許多不同型別的標記。例如：符號，數字，識別符號，字串，操作符等。想知道要從原始檔中提取怎樣的標記完全取決於程式語言本身。
int main() {
int a;
int b;
a = b = 4;
return a - b;
}
Scanner production:
[Keyword(Int), Id("main"), Symbol(LParen), Symbol(RParen), Symbol(LBrace), Keyword(Int), Id("a"), Symbol(Semicolon), Keyword(Int), Id("b"), Symbol(Semicolon), Id("a"), Operator(Assignment), Id("b"),
Operator(Assignment), Integer(4), Symbol(Semicolon), Keyword(Return), Id("a"), Operator(Minus), Id("b"), Symbol(Semicolon), Symbol(RBrace)]
2. 解析
解析器確實是語法解析的核心。 解析器提取由詞法分析器產生的標記，並嘗試判斷它們是否符合特定的模式，然後把這些模式與函式呼叫，變數呼叫，數學運算之類的表示式關聯起來。 解析器逐詞地定義程式語言的語法。
int a = 3 和 a: int = 3 的區別在於解析器的處理上面。解析器決定了語法的外在形式是怎樣的。它確保括號和花括號的左右括號是數量平衡的，每個語句結尾都有一個分號，每個函式都有一個名稱。當標記不符合預期的模式時，解析器就會知道標記的順序不正確。
你可以寫好幾種不同 型別的解析器 。最常見的解析器之一是從上到下的， 遞迴降解的解析器 。遞迴降解的解析器是用起來最簡單也是最容易理解的解析器。我寫的所有解析器樣例都是基於遞迴降解的。
解析器解析的語法可以使用一種 語法 表示出來。像 EBNF 這樣的語法就可以描述一個解析器用於解析簡單的數學運算，像是這樣 12+3 :
expr = additive_expr ;
additive_expr = term, ('+' | '-'), term ;
term = number ;
那種語法的解析器應該是 expr 解析器，因為它直接與所有內容都相關的頂層。唯一有效的輸入必須是任意數字，加號或減號，任意數字。 expr 需要一個 additive_expr ,這主要出現在加法和減法表示式中。 additive_expr 首先需要一個 term （一個數字），然後是加號或者減號，最後是另一個 term 。
解析 12+3 產生的樣例 AST
我之前補充了我們的詞法分析器程式碼，以便它與我們的語法想匹配，並且可以產生像圖表一樣的 AST。我用 // BEGIN PARSER // 和 // END PARSER // 的註釋標記出了新的解析器程式碼的開頭和結尾。
我們可以再深入一點。假設我們想要支援只有數字沒有運算子的輸入，或者新增除法和乘法，甚至新增優先順序。只要簡單地修改一下語法檔案，這些都是完全有可能的，任何調整都會直接反映在我們的解析器程式碼中。
expr = additive_expr ;
additive_expr = multiplicative_expr, { ('+' | '-'), multiplicative_expr } ;
multiplicative_expr = term, { ("*" | "/"), term } ;
term = number ;
針對 C 語言語法編寫的解析器（又叫做詞法分析器）和解析器樣例。從字元序列的開始 “if(net>0.0)total+=net(1.0+tax/100.0);”,掃描器組成了一系列標記，並且對它們進行分類，例如，識別符號，保留字，數字，或者運算子。後者的序列由解析器轉換成語法樹，然後由其他的編譯器分階段進行處理。掃描器和解析器分別處理 C 語法中的規則和與上下文無關的部分。引自：Jochen Burghardt. 來源 .
3. 生成程式碼
程式碼生成器 接收一個 AST ,然後生成相應的程式碼或者彙編程式碼。程式碼生成器必須以遞迴下降的順序遍歷AST中的所有內容-就像是解析器的工作方式一樣-之後生成相應的內容，只不過這裡生成的不再是語法樹，而是程式碼了。
如果開啟上面的連結，你就可以看到左側樣例程式碼產生的彙編程式碼。彙編程式碼的第三行和第四行展示了編譯器在AST中遇到常量的時候是怎樣為這些常量生成相應的程式碼的。
Godbolt Compiler Explorer 是一個很棒的工具，允許你用高階語言編寫程式碼，並檢視它產生的彙編程式碼。你可以有點暈頭轉向了，想知道產生的是哪種程式碼，但不要忘記給你的程式語言編譯器新增優化選項來看看它到底有多智慧。（對於 Rust 是 -O ）
如果你對於編譯器是在組合語言中怎樣把一個本地變數儲存到記憶體中感興趣的話， 這篇文章 （“程式碼生成”部分）非常詳細地解釋了堆疊的相關知識。大多數情況下，當變數不是本地變數的時候，高階編譯器會在堆區為變數分配空間，並把它們儲存到堆區，而不是棧區。你可以從 這個 StackOverflow 的回答上 閱讀更多關於變數儲存的內容。
因為彙編是一個完全不同的，而且複雜的主題，因此這裡我不會過多地討論它。我只是想強調程式碼生成器的重要性和它的作用。此外，程式碼生成器不僅可以產生彙編程式碼。 Haxe 編譯器有一個可以產生 6 種以上不同的程式語言的後端：包括 C++,Java,和 Python。
後端指的是編譯器的程式碼生成器或者表示式解析器；因此前端是詞法分析器和解析器。同樣也有一箇中間端，它通常與優化和 IR 有關，這部分會在稍後解釋。後端通常與前端無關，後端只關心它接收到的 AST。這意味著可以為幾種不同的前端或者語言重用相同的後端。大名鼎鼎的 GNU Compiler Collection 就屬於這種情況。
我找不到比我的 C 編譯器後端更好的程式碼生成器示例了；你可以在 這裡 檢視。
在生成彙編程式碼之後，這些彙編程式碼會被寫入到一個新的彙編檔案中 ( .s 或 .asm )。然後該檔案會被傳遞給彙編器，彙編器是組合語言的編譯器，它會生成相應的二進位制程式碼。之後這些二進位制程式碼會被寫入到一個新的目標檔案中 ( .o ) 。
目標檔案是機器碼，但是它們並不可以被執行。為了讓它們變成可執行檔案，目標檔案需要被連結到一起。連結器讀取通用的機器碼，然後使它變為一個可執行檔案、 共享庫 或是 靜態庫 。更多關於連結器的知識在 這裡 。
連結器是因作業系統而不同的應用程式。隨便一個第三方的連結器都應該可以編譯你後端產生的目的碼。因此在寫編譯器的時候不需要建立你自己的連結器。
編譯器可能有 中間表示 ,或者簡稱 IR 。 IR 主要是為了在優化或者翻譯成另一門語言的時候，無損地表示原來的指令。 IR 不再是原來的程式碼；IR 是為了尋找程式碼中潛在的優化而進行的無損簡化。 迴圈展開 和 向量化 都是利用 IR 完成的。更多關於 IR 相關的優化可以在這個 PDF 中找到。
總結
當你理解了編譯器的時候，你就可以更有效地使用你的程式語言。或許有一天你會對建立你自己的程式語言感興趣？我希望這能夠幫到你。
資源&更深入的閱讀資料
- http://craftinginterpreters.com/ – 指導你編寫一個 C 和 Java 的直譯器。
- https://norasandler.com/2017/11/29/Write-a-Compiler.html – 大概是對我來說最有用的 “編寫編譯器” 的教程了
- 我的 C 編譯器和科學計算解析器可以在 這裡 和 這裡 找到。
- 另一類的解析器，被稱作自底向上的解析器,可以在 這裡 找到。來源於：Wesley Norris.