深入理解編譯器（第二版）

sudozhange? 看雪學(xué)院? 今天

編程語言是如何工作的

從內(nèi)部理解編譯器會(huì)使你更有效的使用它。在這個(gè)時(shí)間順序的摘要中，概括了編程語言和編譯器是如何工作的。我們排版了大量的鏈接，示例代碼，和圖表來幫助你理解。

作者注

理解編譯器—— 是我的在Medium上第二篇文章的后續(xù)，超過了21000的閱讀量。我很高興我能在人們的教育產(chǎn)生積極的影響，我很興奮能夠 根據(jù)我從原始文章收到的反饋進(jìn)行完全的重寫。

Understanding Compilers—For Humans

Do you click that green run button, but don’t really know what’s going on under the hood? Do you want to know how a…

我選擇Rust作為這部作品的主要語言。它是冗長(zhǎng)，高效，現(xiàn)代的，并且在設(shè)計(jì)上似乎對(duì)編寫器非常簡(jiǎn)單。我喜歡使用它：https://www.rust-lang.org/

本文的目的是為了保持讀者的注意力而非20頁的麻木閱讀。本文有許多鏈接會(huì)導(dǎo)航您到引起您興趣的主題以進(jìn)行更深入的探索。大多數(shù)鏈接會(huì)帶領(lǐng)你到Wikipedia。

在底部的評(píng)論區(qū)，歡迎提出任何問題或建議。感謝您的關(guān)注，希望您能喜歡本文。

簡(jiǎn)介

什么是編譯器？

總的來說，你所謂的編程語言其實(shí)就是軟件，叫做編譯器，它讀取文本文件，做了許多處理，并生成二進(jìn)制文件。 由于計(jì)算機(jī)只能讀1或0，人們寫Rust更高質(zhì)量，而不是寫二進(jìn)制文件，編譯器被用來將人類可讀的文本轉(zhuǎn)換為計(jì)算機(jī)可讀的機(jī)器碼。

編譯器可以是任何一個(gè)能將一個(gè)文本翻譯為另一個(gè)文本的程序。例如，這是一個(gè)用Rust寫的編譯器，它將所有的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|

? ? ? 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

}

盡管這個(gè)編譯器不讀取文件，不生成AST，不產(chǎn)生二進(jìn)制文件，但是它仍然被認(rèn)為是一個(gè)編譯器，因?yàn)樗g了輸入。

編譯器做了什么？

簡(jiǎn)單來說，編譯器讀取源代碼生成二進(jìn)制文件。由于直接將復(fù)雜的、人類可讀的代碼轉(zhuǎn)為一和零是非常復(fù)雜的，編譯器在程序可運(yùn)行前有幾個(gè)步驟要做：

讀取你給它的源代碼中的獨(dú)立字符。

將字符分類為字，數(shù)字，符號(hào)和操作符。

獲取已排序完的字符，并通過將它們與模式匹配相匹配和生成操作樹來確定它們嘗試進(jìn)行的操作。

迭代上一步中生成操作樹中的每一個(gè)操作，并生成等效的二進(jìn)制文件。

當(dāng)我說編譯器立刻從一個(gè)操作樹轉(zhuǎn)化到二進(jìn)制文件時(shí)，它實(shí)際生成了匯編代碼，匯編代碼隨后被匯編/編譯成二進(jìn)制文件。匯編像是更高級(jí)的，人類可讀的二進(jìn)制文件。在這里閱讀關(guān)于匯編更多的東西：

https://en.wikipedia.org/wiki/Assembly_language

解釋器（Interpreter）是什么？

解釋器非常像編譯器，它們讀取一門語言并處理它。但是，解釋器跳過代碼生成并且會(huì)即時(shí)執(zhí)行AST。解釋器的最大的優(yōu)點(diǎn)是它在調(diào)試期間運(yùn)行你的程序時(shí)所用的時(shí)間。一個(gè)編譯器在程序執(zhí)行前可能會(huì)花費(fèi)一秒到幾分鐘時(shí)間編譯程序，然而解釋器立刻執(zhí)行，不需要編譯。解釋器最大的缺點(diǎn)是它要求在程序可被執(zhí)行前，用戶的電腦上必須安裝解釋器。

本文主要談?wù)摼幾g器，但是你應(yīng)該清楚他們之間的不同以及和編譯器之間的關(guān)系。

##1. 詞法分析

第一步是按字符分割輸入字符。這步叫做詞法分析，或者符號(hào)化。詞法分析主要的思想是 將字符組合在一起形成單詞，標(biāo)識(shí)符，符號(hào)等等。詞法分析大多不處理任何類似2+2的邏輯——它只會(huì)說有三個(gè)符號(hào)：一個(gè)數(shù)字：2，一個(gè)加號(hào)，以及另一個(gè)數(shù)字：2。

假設(shè)你正在分析如12+3這樣的字符串：它會(huì)讀取字符1,2,+,和3。我們有了獨(dú)立的字符，但我們必須將他們組合在一起，這是符號(hào)化的主要任務(wù)之一。例如，我們得到了1和2作為獨(dú)立的字母，但是我們需要將他們放在一起，并解析他們作為一個(gè)單獨(dú)的整型數(shù)字。+同樣需要被認(rèn)為是一個(gè)加號(hào)，而不是它的文字字符值——字符碼43。

如果你可以看到代碼，并以這種方式賦予更多的意義，隨后，按照Rust符號(hào)化可以組合數(shù)字位32-bit整型，加號(hào)作為Token值Plus。

Rust Playground

play.rust-lang.org

你可以在Rust 操作界面點(diǎn)擊左上角的“運(yùn)行”按鈕來在瀏覽器中編譯和執(zhí)行代碼。

在編程語言的編譯器中，詞法分析器可能需要幾種不同類型的符號(hào)。例如：符號(hào)（symbols），數(shù)字，標(biāo)識(shí)符，字符串，操作符等。它完全依賴于語言自身，才能知道您需要從源代碼中提取哪種類型的符號(hào)。

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

這是一段經(jīng)過詞法分析的C語言源碼，且它的符號(hào)都被打印了出來。

##2. 解析

解析器是語法（分析）的核心。解析器使用詞法分析器生成的符號(hào)，嘗試判斷它們是否處于某種排列樣式，隨后，將那些排列形式與表達(dá)式聯(lián)系，如調(diào)用函數(shù)，召回變量或者數(shù)學(xué)操作。 解析器是按照字面定義語言的語法。

int a = 3 和a: int = 3的不同在解析器中。解析器決定了語法的外觀。它確定了括號(hào)和花括號(hào)平衡，每條語句以分號(hào)結(jié)束，每個(gè)函數(shù)有一個(gè)名字。解析器知道當(dāng)符號(hào)不能匹配到預(yù)設(shè)的樣式時(shí)，有些東西的順序出現(xiàn)了問題。

你可以編寫幾種不同類型的解析器。其中最常見的是自上而下，遞歸下降解析器。遞歸下降解析是最容易使用和理解的。我編寫的許多解析器示例都是基于遞歸解析的。

可以使用語法來概括語法解析器解析。如EBNF這樣的語法可以描述解析器的簡(jiǎn)單數(shù)學(xué)操作，如12+3：

expr = additive_expr ;

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

term = number ;

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

記住，語法文件不是解析器，但是它的確概括了解析器所做的。你按照這樣的語法構(gòu)造一個(gè)類似的解析器。它被人類使用，相對(duì)于直接查看解析器的代碼更容易閱讀和理解。

該語法的解析器是expr解析器，因?yàn)樗琼敿?jí)項(xiàng)目，基本所有都與它有關(guān)。唯一有效的輸入必須是任何數(shù)字，接加號(hào)或減號(hào)，接任何數(shù)字。expr期望一個(gè)additive_expr，這是加法和減法主要出現(xiàn)的地方。additive_expr首先期望一項(xiàng)(term)（一個(gè)數(shù)字），隨后是加號(hào)或減號(hào)，另一項(xiàng)。

解析12+3生成的AST示例

當(dāng)解析器解析時(shí)生成的樹稱為抽象語法樹（abstract syntax tree）,或AST。 AST包含了所有的操作。解析器不需要計(jì)算（所解析的）操作，只需以正確的順序收集它們即可。

我之前添加了我們的詞法分析器代碼，以便與我們的語法匹配，并生成如圖中的ASTs。我用// BEGIN PARSER //和// END PARSER //標(biāo)記了新解析器代碼的開始和結(jié)束。

Rust Playground

play.rust-lang.org

我們實(shí)際上可以更深入。假設(shè)我們想支持只有數(shù)字沒有操作的輸入，或者添加乘法或除法，甚至添加優(yōu)先級(jí)。這可以快速更改語法文件，并在我們解析器代碼中做調(diào)整來反映出來。

expr = additive_expr ;

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

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

term = number ;

新語法

Rust Playground

play.rust-lang.org

C語言的掃描器（又稱詞法分析器）和解析器的案例。從字符序列“if(net>0.0)total+=net*(1.0+tax/100.0);”開始，掃描器組建了符號(hào)序列，并分類，例如作為標(biāo)識(shí)符，保留字，數(shù)字字符，或操作符。后面的序列由解析器轉(zhuǎn)換成語法樹，然后由生于的編譯器階段處理。掃描器和解析器處理C語言語法常規(guī)的和正確的無上下文的部分。版權(quán)所有： Jochen Burghardt。

原始鏈接：

https://bbs.pediy.com/thread-247810.htm

生成代碼

代碼生成器使用AST和代碼的等價(jià)物或者匯編代碼。代碼生成器必須以遞歸下降順序遍歷AST中的每一項(xiàng)——很像解析器所做的——隨后發(fā)出等效的代碼。

Compiler Explorer - Rust (rustc 1.29.0)

pub fn main() { let a = 10 * 3; }

godbolt.org

如果你打開了上面的鏈接，你可以看到左側(cè)示例代碼產(chǎn)生的匯編代碼。匯編代碼的3-4行展示了編譯器在遇到常量時(shí)如何生成常量的代碼。

Godbolt Compiler Explorer是非常好的工具，允許你用高級(jí)語言寫代碼并看到它生成的匯編代碼。你可以對(duì)用它做一些有趣的嘗試，看看生成哪一類的代碼，但是，不要忘記對(duì)你的編譯器添加優(yōu)化標(biāo)志來顯示它的智能之處。（Rust語言使用-o）

如果你對(duì)ASM中編譯器是如何保存局部變量到內(nèi)存感興趣，這篇文章（代碼生成節(jié)）詳細(xì)解釋了棧。大多時(shí)候，當(dāng)變量不是局部的，高級(jí)編譯器會(huì)在堆上為變量分配內(nèi)存，并在那里存儲(chǔ)，而不是在棧上。你可以閱讀更多有關(guān)存儲(chǔ)變量的內(nèi)容在StackOverflow答案。

由于匯編是完全不同的，復(fù)雜的主題，我不會(huì)特別談?wù)撍唷Ｎ抑幌霃?qiáng)調(diào)代碼生成器的工作和重要性。并且，代碼生成器可以生成的不僅僅是匯編。Haxe有可以生成超過六種不同編程語言的后端；包括C++，Java和Python。

后端指的是編譯器的代碼生成器或評(píng)估器；因此，前端是詞法分析器和解析器。也有中端，大多數(shù)是做本節(jié)之后的優(yōu)化和IRs解釋。后端大多與前端無關(guān)，只需考慮接受到的AST。這意味著可以為幾個(gè)不同的前端或語言重用相同的后端。眾人皆知的GNU Compiler Collection就是一個(gè)。

我的C編譯器后端是最好的代碼生成器示例；你可以在這里找到它。

匯編產(chǎn)生后，它會(huì)被寫入新的匯編文件（.s或.asm）。這個(gè)文件會(huì)被匯編器傳遞，匯編器是匯編的編譯器，會(huì)生成二進(jìn)制的等價(jià)物。二進(jìn)制代碼隨后會(huì)被寫入稱作對(duì)象文件的新文件（.o）。

對(duì)象文件是機(jī)器碼，但不可執(zhí)行。要讓它們變得可執(zhí)行，對(duì)象文件需要一起被鏈接。鏈接器使用這個(gè)通用機(jī)器碼，并使它變得可執(zhí)行，共享庫或靜態(tài)庫。更多關(guān)于連接器點(diǎn)擊這里 。

鏈接器是基于操作系統(tǒng)的可變有效程序。一個(gè)單獨(dú)的，第三方的鏈接器應(yīng)該能夠編譯你的后端生成的對(duì)象代碼。當(dāng)制作編譯器時(shí)，不需要?jiǎng)?chuàng)建你自己的鏈接器。

編譯器可能有中間表示(intermediate representation,IR)。IR是用于無損地表示原始指令以進(jìn)行優(yōu)化或翻譯成另一種語言。 IR不是原始源代碼；IR是為了在代碼中找到潛在優(yōu)化的無損簡(jiǎn)化。循環(huán)展開和矢量化是使用IR完成的。更多有關(guān)IR的優(yōu)化示例可以在這個(gè)PDF中找到。

總結(jié)

當(dāng)你理解了編譯器，你可以更高效的使用你的編程語言。可能有一天你會(huì)想制作你自己的編程語言？我希望本文可以幫助到你。

參考&拓展閱讀

http://craftinginterpreters.com/——指導(dǎo)您使用C和Java制作解釋器

https://norasandler.com/2017/11/29/Write-a-Compiler.html——可能對(duì)我來說是最有用的“編寫編譯器”的教程

我的C編譯器和科學(xué)計(jì)算器解析器可以在這里和這里被找到

另一種類型解析器示例，稱為優(yōu)先級(jí)攀爬解析器，可以在這里找到。版權(quán)所有：Wesley Norris

原文鏈接

Understanding Compilers—For Humans (Version 2)

https://towardsdatascience.com/understanding-compilers-for-humans-version-2-157f0edb02dd

-