深入編程語(yǔ)言和編譯器是怎樣工作的

理解編譯器內(nèi)部原理，可以讓你更高效利用它。按照編譯的工作順序，逐步深入編程語(yǔ)言和編譯器是怎樣工作的。本文有大量的鏈接、樣例代碼和圖表幫助你理解編譯器。

作者注：

這是我在 Medium 上的第二篇文章的再版，上一版有超過(guò) 21000 的閱讀量。很高興我能夠幫助到各位的學(xué)習(xí)，因此我根據(jù)上一版的評(píng)論，完完全全重寫(xiě)了。

我選擇 Rust 作為這篇文章的主要語(yǔ)言。它是一種詳盡的、高效的、現(xiàn)代的而且看起來(lái)特意使得設(shè)計(jì)編譯器變得簡(jiǎn)單。我很喜歡使用它。

https://www.rust-lang.org/

寫(xiě)這篇文章的目的主要是吸引讀者的注意力，而不是提供 20 多頁(yè)的令人頭皮發(fā)麻的閱讀材料。對(duì)于那些你感興趣的更深層次的話題，文章中有許多鏈接會(huì)引導(dǎo)你找到相關(guān)的資料。大多數(shù)鏈接到維基百科 。

感謝你的關(guān)注，我希望你能夠喜歡這些我花費(fèi)了超過(guò) 20 個(gè)小時(shí)的寫(xiě)出的文章。歡迎在文章底部評(píng)論處留下任何問(wèn)題或者建議。

簡(jiǎn)單介紹

編譯器是什么？

你口中所說(shuō)的編程語(yǔ)言本質(zhì)上只是一個(gè)軟件，這個(gè)軟件叫做編譯器，編譯器讀入一個(gè)文本文件，經(jīng)過(guò)大量的處理，最終產(chǎn)生一個(gè)二進(jìn)制文件。編譯器的語(yǔ)言部分就是它處理的文本樣式。因?yàn)?a href="http://wenjunhu.com/v/tag/1247/" target="_blank">電腦只能讀取 1 和 0 ，而人們編寫(xiě) Rust 程序要比直接編寫(xiě)二進(jìn)制程序簡(jiǎn)單地多，因此編譯器就被用來(lái)把人類可讀的文本轉(zhuǎn)換成計(jì)算機(jī)可識(shí)別的機(jī)器碼。

編譯器可以是任何可以把文本文件轉(zhuǎn)換成其他文件的程序。例如，下面有一個(gè)用 Rust 語(yǔ)言寫(xiě)的編譯器把 0 轉(zhuǎn)換成 1，把 1 轉(zhuǎn)換成 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|

ifc == '1'{'0'}

elseifc == '0'{'1'}

else{c}// if not 0 or 1, leave it alone

).collect();

println!("{}",output);// 0 1 0 A 0 1 0 3

}

編譯器是做什么的？

簡(jiǎn)言之，編譯器獲取源代碼，產(chǎn)生一個(gè)二進(jìn)制文件。因?yàn)閺膹?fù)雜的、人類可讀的代碼直接轉(zhuǎn)化成0/1二進(jìn)制會(huì)很復(fù)雜，所以編譯器在產(chǎn)生可運(yùn)行程序之前有多個(gè)步驟：

從你給定的源代碼中讀取單個(gè)詞。

把這些詞按照單詞、數(shù)字、符號(hào)、運(yùn)算符進(jìn)行分類。

通過(guò)模式匹配從分好類的單詞中找出運(yùn)算符，明確這些運(yùn)算符想進(jìn)行的運(yùn)算，然后產(chǎn)生一個(gè)運(yùn)算符的樹(shù)（表達(dá)式樹(shù)）。

最后一步遍歷表達(dá)式樹(shù)中的所有運(yùn)算符，產(chǎn)生相應(yīng)的二進(jìn)制數(shù)據(jù)。

盡管我說(shuō)編譯器直接從表達(dá)式樹(shù)轉(zhuǎn)換到二進(jìn)制，但實(shí)際上它會(huì)產(chǎn)生匯編代碼，之后匯編代碼會(huì)被匯編/編譯到二進(jìn)制數(shù)據(jù)。匯編程序就好比是一種高級(jí)的、人類可讀的二進(jìn)制。

解釋器是什么？

解釋器非常像編譯器，它也是讀入編程語(yǔ)言的代碼，然后處理這些代碼。盡管如此，解釋器會(huì)跳過(guò)了代碼生成，然后即時(shí)編譯并執(zhí)行 AST。解釋器最大的優(yōu)點(diǎn)就在于在你 debug 期間運(yùn)行程序所消耗的時(shí)間。編譯器編譯一個(gè)程序可能在一秒到幾分鐘不等，然而解釋器可以立即開(kāi)始執(zhí)行程序，而不必編譯。解釋器最大的缺點(diǎn)在于它必須安裝在用戶電腦上，程序才可以執(zhí)行。

雖然這篇文章主要是關(guān)于編譯器的，但是對(duì)于編譯器和解釋器之間的區(qū)別和編譯器相關(guān)的內(nèi)容一定要弄清楚。

1. 詞法分析

第一步是把輸入一個(gè)詞一個(gè)詞的拆分開(kāi)。這一步被叫做詞法分析,或者說(shuō)是分詞。這一步的關(guān)鍵就在于我們把字符組合成我們需要的單詞、標(biāo)識(shí)符、符號(hào)等等。詞法分析大多都不需要處理邏輯運(yùn)算像是算出2+2– 其實(shí)這個(gè)表達(dá)式只有三種標(biāo)記：一個(gè)數(shù)字：2,一個(gè)加號(hào)，另外一個(gè)數(shù)字：2。

讓我們假設(shè)你正在解析一個(gè)像是12+3這樣的字符串：它會(huì)讀入字符1，2，+，和3。我們已經(jīng)把這些字符拆分開(kāi)了，但是現(xiàn)在我們必須把他們組合起來(lái)；這是分詞器的主要任務(wù)之一。舉個(gè)例子，我們得到了兩個(gè)單獨(dú)的字符1和2，但是我們需要把它們放到一起，然后把它們解析成為一個(gè)整數(shù)。至于+也需要被識(shí)別為加號(hào)，而不是它的字符值 – 字符值是43 。

如果你可以閱讀過(guò)上面的代碼，并且弄懂了這樣做的含義，接下來(lái)的 Rust 分詞器會(huì)組合數(shù)字為32位整數(shù)，加號(hào)就最后了標(biāo)記值 Plus（加）.

https://play.rust-lang.org/?gist=070c3b6b985098a306c62881d7f2f82c&version=stable&mode=debug&edition=2015

你可以點(diǎn)擊 Rust playgroud 左上角的 “Run” 按鈕來(lái)編譯和執(zhí)行你瀏覽器中的代碼。

在一種編程語(yǔ)言的編譯器中，詞法解析器可能需要許多不同類型的標(biāo)記。例如：符號(hào)，數(shù)字，標(biāo)識(shí)符，字符串，操作符等。想知道要從源文件中提取怎樣的標(biāo)記完全取決于編程語(yǔ)言本身。

intmain(){

inta;

intb;

a = b = 4;

returna - 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)]

C 語(yǔ)言的樣例代碼已經(jīng)進(jìn)行過(guò)詞法分析，并且輸出了它的標(biāo)記。

2. 解析

解析器確實(shí)是語(yǔ)法解析的核心。解析器提取由詞法分析器產(chǎn)生的標(biāo)記，并嘗試判斷它們是否符合特定的模式，然后把這些模式與函數(shù)調(diào)用，變量調(diào)用，數(shù)學(xué)運(yùn)算之類的表達(dá)式關(guān)聯(lián)起來(lái)。 解析器逐詞地定義編程語(yǔ)言的語(yǔ)法。

int a = 3 和 a: int = 3 的區(qū)別在于解析器的處理上面。解析器決定了語(yǔ)法的外在形式是怎樣的。它確保括號(hào)和花括號(hào)的左右括號(hào)是數(shù)量平衡的，每個(gè)語(yǔ)句結(jié)尾都有一個(gè)分號(hào)，每個(gè)函數(shù)都有一個(gè)名稱。當(dāng)標(biāo)記不符合預(yù)期的模式時(shí)，解析器就會(huì)知道標(biāo)記的順序不正確。

你可以寫(xiě)好幾種不同類型的解析器。最常見(jiàn)的解析器之一是從上到下的，遞歸降解的解析器。遞歸降解的解析器是用起來(lái)最簡(jiǎn)單也是最容易理解的解析器。我寫(xiě)的所有解析器樣例都是基于遞歸降解的。

解析器解析的語(yǔ)法可以使用一種 語(yǔ)法 表示出來(lái)。像 EBNF 這樣的語(yǔ)法就可以描述一個(gè)解析器用于解析簡(jiǎn)單的數(shù)學(xué)運(yùn)算，像是這樣 12+3 :

expr = additive_expr;

additive_expr = term,('+' | '-'),term;

term = number;

簡(jiǎn)單加法和減法表達(dá)式的 EBNF 語(yǔ)法。

請(qǐng)記住語(yǔ)法文件并不是解析器，但是它確實(shí)是解析器的一種表達(dá)形式。你可以圍繞上面的語(yǔ)法創(chuàng)建一個(gè)解析器。語(yǔ)法文件可以被人使用并且比起直接閱讀和理解解析器的代碼要簡(jiǎn)單許多。

那種語(yǔ)法的解析器應(yīng)該是expr解析器，因?yàn)樗苯优c所有內(nèi)容都相關(guān)的頂層。唯一有效的輸入必須是任意數(shù)字，加號(hào)或減號(hào)，任意數(shù)字。expr需要一個(gè)additive_expr,這主要出現(xiàn)在加法和減法表達(dá)式中。additive_expr首先需要一個(gè)term（一個(gè)數(shù)字），然后是加號(hào)或者減號(hào)，最后是另一個(gè)term。

解析 12+3 產(chǎn)生的樣例 AST

解析器在解析時(shí)產(chǎn)生的樹(shù)狀結(jié)構(gòu)被稱為抽象的語(yǔ)法樹(shù)，或者稱之為 AST。ast 中包含了所有要進(jìn)行操作。解析器不會(huì)計(jì)算這些操作，它只是以正確的順序來(lái)收集其中的標(biāo)記。

我之前補(bǔ)充了我們的詞法分析器代碼，以便它與我們的語(yǔ)法想匹配，并且可以產(chǎn)生像圖表一樣的 AST。我用// BEGIN PARSER //和// END PARSER //的注釋標(biāo)記出了新的解析器代碼的開(kāi)頭和結(jié)尾。

https://play.rust-lang.org/?gist=205deadb23dbc814912185cec8148fcf&version=stable&mode=debug&edition=2015

我們可以再深入一點(diǎn)。假設(shè)我們想要支持只有數(shù)字沒(méi)有運(yùn)算符的輸入，或者添加除法和乘法，甚至添加優(yōu)先級(jí)。只要簡(jiǎn)單地修改一下語(yǔ)法文件，這些都是完全有可能的，任何調(diào)整都會(huì)直接反映在我們的解析器代碼中。

expr = additive_expr;

additive_expr = multiplicative_expr,{('+' | '-'),multiplicative_expr};

multiplicative_expr = term,{("*" | "/"),term};

term = number;

新的語(yǔ)法。

https://play.rust-lang.org/?gist=1587a5dd6109f70cafe68818a8c1a883&version=nightly&mode=debug&edition=2018

針對(duì) C 語(yǔ)言語(yǔ)法編寫(xiě)的解析器（又叫做詞法分析器）和解析器樣例。從字符序列的開(kāi)始 “if(net>0.0)total+=net(1.0+tax/100.0);”,掃描器組成了一系列標(biāo)記，并且對(duì)它們進(jìn)行分類，例如，標(biāo)識(shí)符，保留字，數(shù)字，或者運(yùn)算符。后者的序列由解析器轉(zhuǎn)換成語(yǔ)法樹(shù)，然后由其他的編譯器分階段進(jìn)行處理。掃描器和解析器分別處理 C 語(yǔ)法中的規(guī)則和與上下文無(wú)關(guān)的部分。引自：Jochen Burghardt.來(lái)源.

3. 生成代碼

代碼生成器接收一個(gè) AST ,然后生成相應(yīng)的代碼或者匯編代碼。代碼生成器必須以遞歸下降的順序遍歷AST中的所有內(nèi)容-就像是解析器的工作方式一樣-之后生成相應(yīng)的內(nèi)容，只不過(guò)這里生成的不再是語(yǔ)法樹(shù)，而是代碼了。

https://godbolt.org/z/K8416_

如果打開(kāi)上面的鏈接，你就可以看到左側(cè)樣例代碼產(chǎn)生的匯編代碼。匯編代碼的第三行和第四行展示了編譯器在AST中遇到常量的時(shí)候是怎樣為這些常量生成相應(yīng)的代碼的。

Godbolt Compiler Explorer 是一個(gè)很棒的工具，允許你用高級(jí)語(yǔ)言編寫(xiě)代碼，并查看它產(chǎn)生的匯編代碼。你可以有點(diǎn)暈頭轉(zhuǎn)向了，想知道產(chǎn)生的是哪種代碼，但不要忘記給你的編程語(yǔ)言編譯器添加優(yōu)化選項(xiàng)來(lái)看看它到底有多智能。（對(duì)于 Rust 是-O）

如果你對(duì)于編譯器是在匯編語(yǔ)言中怎樣把一個(gè)本地變量保存到內(nèi)存中感興趣的話，這篇文章（“代碼生成”部分）非常詳細(xì)地解釋了堆棧的相關(guān)知識(shí)。大多數(shù)情況下，當(dāng)變量不是本地變量的時(shí)候，高級(jí)編譯器會(huì)在堆區(qū)為變量分配空間，并把它們保存到堆區(qū)，而不是棧區(qū)。你可以從這個(gè) StackOverflow 的回答上閱讀更多關(guān)于變量存儲(chǔ)的內(nèi)容。

因?yàn)閰R編是一個(gè)完全不同的，而且復(fù)雜的主題，因此這里我不會(huì)過(guò)多地討論它。我只是想強(qiáng)調(diào)代碼生成器的重要性和它的作用。此外，代碼生成器不僅可以產(chǎn)生匯編代碼。Haxe編譯器有一個(gè)可以產(chǎn)生 6 種以上不同的編程語(yǔ)言的后端：包括 C++,Java,和 Python。

后端指的是編譯器的代碼生成器或者表達(dá)式解析器；因此前端是詞法分析器和解析器。同樣也有一個(gè)中間端，它通常與優(yōu)化和 IR 有關(guān)，這部分會(huì)在稍后解釋。后端通常與前端無(wú)關(guān)，后端只關(guān)心它接收到的 AST。這意味著可以為幾種不同的前端或者語(yǔ)言重用相同的后端。大名鼎鼎的GNU Compiler Collection就屬于這種情況。

我找不到比我的 C 編譯器后端更好的代碼生成器示例了。

在生成匯編代碼之后，這些匯編代碼會(huì)被寫(xiě)入到一個(gè)新的匯編文件中 (.s或.asm)。然后該文件會(huì)被傳遞給匯編器，匯編器是匯編語(yǔ)言的編譯器，它會(huì)生成相應(yīng)的二進(jìn)制代碼。之后這些二進(jìn)制代碼會(huì)被寫(xiě)入到一個(gè)新的目標(biāo)文件中 (.o) 。

目標(biāo)文件是機(jī)器碼，但是它們并不可以被執(zhí)行。為了讓它們變成可執(zhí)行文件，目標(biāo)文件需要被鏈接到一起。鏈接器讀取通用的機(jī)器碼，然后使它變?yōu)橐粋€(gè)可執(zhí)行文件、共享庫(kù)或是靜態(tài)庫(kù)。

鏈接器是因操作系統(tǒng)而不同的應(yīng)用程序。隨便一個(gè)第三方的鏈接器都應(yīng)該可以編譯你后端產(chǎn)生的目標(biāo)代碼。因此在寫(xiě)編譯器的時(shí)候不需要?jiǎng)?chuàng)建你自己的鏈接器。

編譯器可能有中間表示,或者簡(jiǎn)稱 IR 。IR 主要是為了在優(yōu)化或者翻譯成另一門語(yǔ)言的時(shí)候，無(wú)損地表示原來(lái)的指令。IR 不再是原來(lái)的代碼；IR 是為了尋找代碼中潛在的優(yōu)化而進(jìn)行的無(wú)損簡(jiǎn)化。循環(huán)展開(kāi)和向量化都是利用 IR 完成的。

總結(jié)

當(dāng)你理解了編譯器的時(shí)候，你就可以更有效地使用你的編程語(yǔ)言?；蛟S有一天你會(huì)對(duì)創(chuàng)建你自己的編程語(yǔ)言感興趣？我希望這能夠幫到你。