[译] 理解编译器 —— 从人类的角度（版本 2）
- 原文地址：Understanding Compilers?—?For Humans (Version 2)
- 原文作者：Luke Wilson
- 譯文出自：掘金翻譯計劃
- 本文永久鏈接：github.com/xitu/gold-m…
- 譯者：Starrier
- 校對者：Raoul1996, Gavin-Gong
理解編譯器 —— 從人類的角度（版本 2）
編程語言的工作原理
理解編譯器的內部原理會促使你更高效地使用它。在這個按時間排序的概要中，了解編程語言和編譯器的工作原理。（為此）編寫了大量的鏈接、示例代碼和圖表來幫助你理解。
作者標注
理解編譯器 —— 從人類的角度（Version 2）是我在 Medium 上發表的第二篇文章（有超過 21000 的閱讀量）的后續。我很高興自己的內容對大家產生了積極的影響，我也很開心能根據從原文章收集到的意見來對其進行完整的重寫。
- 理解編譯器 —— 從人類的角度：盡管你知道點擊綠色按鈕就可以執行，但你真的知道它的底層發生了哪些事情么？
我選擇 Rust 作為這篇文章的首選語言。因為它詳細、高效、現代化，而且從設計上看，編寫編譯器時會相對簡單。我非常喜歡它。www.rust-lang.org/
寫這篇文章的目的是為了保證讀者能集中精神，而不是 20 頁的精神疲憊閱讀。你可以在文中的許多鏈接中，選擇自己感興趣的內容，去了解相關內容的深層解讀。當然，大部分都是鏈接向維基百科的。
請隨意在文末進行評論，或者說出問題建議。感謝你的關注，希望你可以喜歡這篇文章。
簡介
什么是編譯器
當然，你也可以認為編程語言就是叫做編譯器的軟件，它讀取文本文件，對其進行大量的處理，然后生成二進制文件。由于計算機只能讀 1 和 0，比起二進制，人類更擅長寫 Rust，所以編譯器將人類可讀的文本轉化為計算機可讀的機器代碼。**
編譯器可以是將一個文本轉變成另一個文本的程序。比如，這里有用 Rust 編寫的編譯器，它將 0 與 1 相互轉化：
// 一個示例編譯器，將 0 與 1 互換。fn main() {let input = "1 0 1 A 1 0 1 3";// 對輸入的每個字符 `c` 進行迭代let output: String = input.chars().map(|c|if c == '1' { '0' }else if c == '0' { '1' }else { c } // 如果不是 0 或 1，就忽略它（不進行處理）).collect();println!("{}", output); // 0 1 0 A 0 1 0 3 } 復制代碼盡管這個編譯器不讀取文件，不生成 AST（抽象語法樹）或者二進制文件，但它仍然被看成是一個編譯器，原因很簡單，就是它可以翻譯輸入的內容。
編譯器會做什么事情
簡而言之，編譯器讀取源代碼并生產二進制文件。由于直接從人類可讀的復雜代碼轉換成 1 和 0 非常復雜，因此編譯器在運行之前會有幾個處理步驟：
雖然我說編譯器會立即從運算符樹轉換為二進制，但它實際上會生成匯編代碼，然后組裝/編譯成二進制代碼，匯編是一個更高層次的、人類可讀的二進制文件。更多程序集的相關閱讀可在此查詢。
解釋器是什么
解釋器更像是編譯器，因為它們都讀取一種語言，然后對其進行處理。但是解釋器會跳過代碼生成，即時生成 AST。對解釋器來說，最大的優點就是降低在調試運行期間所花費時間。編譯器在執行前可能需要從一秒鐘到幾分鐘的時間來編譯程序，而解釋器則會立即開始執行，而不需要編譯。解釋器最大的缺點是需要在程序執行之前安裝在用戶的計算機上。
本文主要涉及編譯器，但應該清楚它們之間的區別以及編譯器之間的關系。
1. 詞法分析
第一步是將輸入的內容分割成字符。這一步稱為詞法分析，或標記化。主要目的是將字符組合在一起，形成我們的單詞、標識符、符號等。詞法分析通常不處理任何邏輯上的問題，比如求解 2+2?——?它只會說有三個標記：一個數字：2，一個加號，以及另一個數字：2。
假設你是在給像 12+3 這樣的字符串下定義：它會讀取字符 1、2、+ 和 3。我們有單獨的字符，但我們必須將它們組合在一起；這是 tokenizer 的主要任務之一。比如，盡管我們將 1 和 2 最為單獨的字母，但我們最后還是要將它們組合在一起，然后解析成一個整數。+ 將被識別為一個加號，而不是它的字面量值 —— 字符碼 43。
如果你可以看到代碼并以這種方式使其更具意義，那么以下的 Rust 標記生成器可以將數字分成 32 位整數，并加上符號作為 Token 值 Plus。
Rust Playground：play.rust-lang.org
你可以單擊 Rust Playground 左上角的 “RUn” 按鈕，在你的瀏覽器中編譯并執行代碼。
在編程語言的編譯器中，lexer 詞法分析器可能需要幾種不同類型的標記。例如，符號、數字、標識符、字符串、運算符等。這完全取決于語言本身是否知道你需要從源碼中提取什么樣的標記。
int main() {int a;int b;a = b = 4;return a - b; }掃描生成內容： [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)] 復制代碼已進行詞法分析的 C 源碼示例及其標記。
2. 解析
解析器確實是語法的核心。解析器獲取由 lexer 生成的標記，試圖查看它們是否在某些模式中，然后將這些模式與諸如調用函數、回調變量或者數學操作相關聯。解析器實際上定義了語言的語法。
在解析器中，詞組 int a = 3 和 a: int = 3 之間的區別。解析器決定了語法的外觀。它確保括號和大括號的平衡性，每個語句都以分號結尾，而且每個函數都有一個名稱。當代碼不符合順序，標記與預期模式不符，解析器都會知道。
有幾種不同的類型解析器可以編寫。其中最常見的一種是自頂向下的 recursive-descent 解析器。Recursive-descent 解析器使用和理解起來都是最簡單的方法。我創建的所有解析器示例都是基于 recursive-descent。
解析器解析的語法可以使用語法進行概括。像 EBNF 這樣的語法可以描述像 12+3 這樣簡單數字操作的解析器：
expr = additive_expr ; additive_expr = term, ('+' | '-'), term ; term = number ; 復制代碼用于簡單加減表達式的 EBNF 語法。
請記住，語法文件不是解析器，但是它是解析器所做工作的概要。你可以圍繞這樣的語法構建一個解析器。它將被人類使用，并且比直接查看解析器的代碼更容易閱讀和理解。
該語法的解析器是 expr 解析器，因為它是頂級內容，所以基本上所有的內容都與之相關。唯一有效的輸入必須是任意數字之間的加減。expr 期望 additive_expr 出現的主要是進行加減的地方。additive_expr 首先期望一個 term（一個數字），然后對另一個 term 進行加減。
解析 12 + 3 而生產的示例 AST。
解析器在解析過程生成的樹稱為抽象語法樹，或者 AST。AST 擁有所有的操作。解析器不計算操作，只保證按正確的順序記錄它們。
我將它們添加到之前的 lexer 代碼中，這樣就可以匹配我們的語法，并且可以像圖表一樣生成 AST。我用注釋 // BEGIN PARSER // 和 // END PARSER // 標記了新解析代碼的開頭和結尾。
Rust 頁面：play.rust-lang.org
事實上我們可以了解的更深入。假設我們想要支持僅僅是沒有運算符的數字輸入，或者添加乘法和除法，甚至是添加優先級。這可以快速更改語法文件，并進行調整以將其反映在我們的解析器代碼中。
expr = additive_expr ; additive_expr = multiplicative_expr, { ('+' | '-'), multiplicative_expr } ; multiplicative_expr = term, { ("*" | "/"), term } ; term = number ; 復制代碼新語法。
Rust 頁面：play.rust-lang.org
C 的掃描器（又名詞法分析器）和解釋器示例。從字符 "if(net>0.0)total+=net*(1.0+tax/100.0);" 開始，掃描器組成一系列標記，并為每個標記分類，例如，作為標識符、保留字。數字文字或運算符。后一個序列由解析器轉化為語法樹，然后由其余的編譯器階段處理。掃描器和解析器分別處理 C 語法中正常和適當上下文無關的部分。Credit：Jochen Burghardt。原件。
3. 生成代碼
代碼生成器接受 AST，然后在代碼或匯編中生成等效的代碼代碼生成器必須以遞歸下降的順序遍歷 AST 中的每一項 —— 就像解析器的工作原理 —— 然后在代碼中發出等效項。
- 編譯器資源管理器 —— Rust (rustc 1.29.0)：godbolt.org
如果打開上面的鏈接，你會看到左邊示例代碼生成的程序集。匯編代碼的第 3 行和第 4 行顯示了編譯器在 AST 中遇到常量時是如果生成常量代碼的。
Godbolt 編譯器管理資源是一個優秀的工具，允許你用高級語言編寫代碼并查看其生產的匯編代碼。你可以隨意查看這些，看看應該編寫什么樣的代碼，但不要忘記將優化標志添加到語言的編譯器中，看看它們有多高明（Rust 的 -O）。
如果你對編譯器如何在 ASM 中將局部變量保存到內存中感興趣，這篇文章（“代碼生成”部分）詳細解釋了棧。在變量不是本地變量的多數情況下，高級編譯器將在堆上的為變量分配內存，并將它們存儲在堆中而不是棧中。你可以在 StackOverflow 上關于存儲變量的信息。
由于組裝是一個完全不同的復雜主題，所以我不會詳細討論它。我只想強調代碼生成器的重要性以及工作原理。此外，代碼生成器可以產生的不僅僅是集合內容。Haxe 編譯器有一個 backend，可以生成六種以上不同的編程語言；包括 C++、Java 和 Python。
后端主要是編譯器的代碼生成器或計算程序；因此，前端是 lexer 和解析器。還有一個與優化相關的中間件。IRs 將在本節末解釋。后端大部分與前端無關，它只關心接收到的 AST。這意味著可以為幾種不同的前端或語言重用相同的后端。GNU 編譯器集合就是這種情況。
我想，我再也找不大比我的 C 編譯器生成的后端代碼更好的示例了：你應該可以找到。
生成程序集之后，應該將其寫入一個新的組裝文件（.s 或 .asm）。然后匯編器（程序集的編譯器）會傳遞該文件，并以二進制形式生成等效的文件。二進制代碼會寫入一個稱為對象文件（.o）的新文件。
**對象文件是機器碼，它們是不可執行的。**想讓它們成為可執行文件，就需要將對象文件鏈接在一起。鏈接器接受這個通用的機器代碼，并使它們成為一個可執行文件，一個共享庫 或 靜態庫。更多鏈接器可在此查詢。
鏈接器是基于操作系統變化而來實用性程序。一個獨立的第三方鏈接器應該可以編譯后端生成的對象代碼。在生成編譯器時，不再需要創建自己的鏈接器。
編譯器可能有一個代理中間件，或者是 IR。IR 是為優化或翻譯成另一種語言而無損失的原生指令的表示。IR 不是源代碼，IR 是為了在代碼中發現優化的可能性而進行的無損簡化。展開循環和向量化是使用 IR 完成的。更多 IR 相關的優化示例可在此 PDF 參閱。
結論
在你了解編譯器之后，你的編程開發將會更加高效。將來的某一刻，你也許會對創造自己的編程語言感興趣。希望這篇文章能對你有所幫助。
資源和深入學習的相關文章
- craftinginterpreters.com/?——?指導你使用 C 和 Java 編寫編譯器。
- norasandler.com/2017/11/29/…?—— ?對我來說，可能是最好的“編寫編譯器”教程。
- 我的 C 編譯器和科學計算器解析器在這里以及這里。
- 另一種稱為 precedence climbing 解析器的示例，可以在這里找到。Credit：Wesley Norris。
如果發現譯文存在錯誤或其他需要改進的地方，歡迎到 掘金翻譯計劃 對譯文進行修改并 PR，也可獲得相應獎勵積分。文章開頭的 本文永久鏈接 即為本文在 GitHub 上的 MarkDown 鏈接。
掘金翻譯計劃 是一個翻譯優質互聯網技術文章的社區，文章來源為 掘金 上的英文分享文章。內容覆蓋 Android、iOS、前端、后端、區塊鏈、產品、設計、人工智能等領域，想要查看更多優質譯文請持續關注 掘金翻譯計劃、官方微博、知乎專欄。
總結
以上是生活随笔為你收集整理的[译] 理解编译器 —— 从人类的角度（版本 2）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： css实现让页面的footer始终位于底
- 下一篇： No transaction aspec