人人都能读懂的编译器原理

编程语言的工作原理是如何的？了解编译器的内部原理可以帮助您更有效地使用它。通过按照编译的工作顺序逐步深入了解编程语言和编译器的工作方式，本文提供了大量的链接、示例代码和图表，以帮助您理解编译器。作者注：这是我在Medium上的第二篇文章的再版，上一版已经有超过21000次阅读。我很高兴能够帮助到读者学习，因此根据上一版的评论，我完全重写了这篇文章。

我选择Rust作为本文的主要语言。Rust是一种详尽、高效、现代化的语言，它的设计使得编写编译器变得简单。我非常喜欢使用它。

写这篇文章的目的主要是吸引读者的注意力，而不是提供20多页令人头疼的阅读材料。对于那些对更深层次话题感兴趣的人，文章中有许多链接可以引导您找到相关的资料，大多数链接指向维基百科。

感谢您的关注，我希望您会喜欢我花费超过20个小时写出的这篇文章。欢迎在文章底部的评论区留下任何问题或建议。

简单介绍
编译器是什么？您所说的编程语言本质上只是一个软件，这个软件叫做编译器。编译器读取一个文本文件，并经过大量处理，最终生成一个二进制文件。编译器的语言部分就是它处理的文本样式。因为计算机只能读取1和0，而人们编写Rust程序要比直接编写二进制程序简单得多，所以编译器被用来将人类可读的文本转换为计算机可识别的机器码。

编译器可以是任何将文本文件转换为其他文件的程序。例如，下面是一个用Rust语言编写的编译器示例，它将0转换为1，将1转换为0：

// 将0转换为1，将1转换为0的示例编译器
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
}

编译器的作用是什么？
简而言之，编译器接收源代码并生成一个二进制文件。由于直接从复杂的、人类可读的代码转换为0/1二进制会非常复杂，因此编译器在生成可运行程序之前有多个步骤：

1. 从给定的源代码中读取单个词。将这些词按照单词、数字、符号、运算符进行分类。
2. 通过模式匹配从分类好的词中找出运算符，并确定这些运算符要进行的运算，然后生成一个运算符树（表达式树）。
3. 最后，遍历表达式树中的所有运算符，生成相应的二进制数据。

尽管我说编译器直接从表达式树转换为二进制，但实际上它会生成汇编代码，然后将汇编代码汇编/编译为二进制数据。汇编代码类似于一种高级、人类可读的二进制。

解释器是什么？
解释器与编译器非常相似，它也读取编程语言的代码并处理这些代码。然而，解释器会跳过代码生成的步骤，直接即时编译并执行抽象语法树（AST）。解释器的最大优点在于在调试期间运行程序所需的时间较短。编译器编译一个程序可能需要几秒钟到几分钟的时间，而解释器可以立即开始执行程序，无需编译。解释器的最大缺点在于它必须安装在用户的计算机上才能执行程序。

虽然本文主要关注编译器，但是了解编译器和解释器之间的区别以及与编译器相关的内容非常重要。

1. 词法分析
   第一步是将输入拆分为一个个单词。这一步被称为词法分析或分词。关键在于将字符组合成所需的单词、标识符、符号等。词法分析通常不需要处理逻辑运算，例如计算2+2-，实际上这个表达式只有三个标记：一个数字2，一个加号，另一个数字2。

让我们假设您正在解析一个类似于12+3的字符串：它会读取字符1、2、+和3。我们已经将这些字符拆分开了，但现在我们需要将它们组合起来；这是分词器的主要任务之一。例如，我们得到了两个单独的字符1和2，但我们需要将它们组合在一起，然后将它们解析为一个整数。对于+，我们需要识别它为加号，而不是其字符值-字符值为43。

如果您能够阅读上面的代码并理解其含义，接下来的Rust分词器将将数字组合为32位整数，然后将加号解析为标记值Plus（加）。

您可以点击Rust Playground左上角的“Run”按钮来编译和执行您在浏览器中的代码。

在编程语言的编译器中，词法解析器可能需要处理许多不同类型的标记。例如：符号、数字、标识符、字符串、操作符等。要从源文件中提取哪些标记完全取决于编程语言本身。

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. 解析
   解析器是语法解析的核心。解析器接收词法分析器生成的标记，并尝试确定它们是否符合特定的模式，然后将这些模式与函数调用、变量调用、数学运算等表达式相关联。解析器逐词地定义编程语言的语法。

int a = 3和a: int = 3之间的区别在于解析器的处理方式。解析器决定了语法的外部形式。它确保括号和花括号的左右括号数量平衡，每个语句结尾都有一个分号，每个函数都有一个名称。当标记不符合预期的模式时，解析器会知道标记的顺序不正确。

您可以编写多种不同类型的解析器。其中一种最常见的解析器是自上而下的递归下降解析器。递归下降解析器是最简单且最容易理解的解析器。我提供的所有解析器示例都基于递归下降解析器。

解析器的语法可以使用一种语法表示。例如，像EBNF这样的语法可以描述解析器用于解析简单数学运算的语法，如下所示：

expr = additiveexpr ;
additiveexpr = term, (‘+’ | ‘-‘), term ;
term = number ;

这是简单加法和减法表达式的EBNF语法。

请记住，语法文件本身并不是解析器，但它确实是解析器的一种表达形式。您可以围绕上述语法创建一个解析器。与直接阅读和理解解析器代码相比，语法文件对人来说更容易使用和理解。

对于解析器来说，最重要的是expr解析器，因为它直接与所有内容相关。唯一有效的输入必须是任意数字、加号或减号、任意数字。expr需要一个additiveexpr，这主要出现在加法和减法表达式中。additiveexpr首先需要一个term（一个数字），然后是加号或减号，最后是另一个term。

解析12+3生成的示例AST
解析器在解析过程中生成的树状结构称为抽象语法树（AST）。AST包含了所有要进行操作的信息。解析器不会计算这些操作，它只是以正确的顺序收集标记。

我之前补充了我们的词法分析器代码，以使其与我们的语法匹配，并且可以生成类似图表的AST。我在代码中使用了// BEGIN PARSER//和// END PARSER//的注释标记出新的解析器代码的开头和结尾。

您可以点击上面的链接查看左侧样例代码生成的汇编代码。汇编代码的第三行和第四行展示了编译器在遇到常量时如何为其生成相应的代码。

Godbolt Compiler Explorer是一个很棒的工具，允许您使用高级语言编写代码，并查看生成的汇编代码。您可能会感到有些困惑，想知道生成的是哪种代码，但不要忘记为您的编程语言编译器添加优化选项，看看它有多聪明（对于Rust来说是-O）。

如果您对编译器如何将本地变量保存到内存中的过程感兴趣，这篇文章（“代码生成”部分）非常详细地解释了堆栈的相关知识。在大多数情况下，当变量不是本地变量时，高级编译器会在堆上为变量分配空间，并将它们保存在堆上，而不是栈上。您可以在这个StackOverflow的答案中阅读更多关于变量存储的内容。

由于汇编是一个完全不同且复杂的主题，所以在这里我不会过多讨论它。我只是想强调代码生成器的重要性和作用。此外，代码生成器不仅可以生成汇编代码。Haxe编译器有一个可以生成6种以上不同编程语言的后端，包括C++、Java和Python。

后端是指编译器的代码生成器或表达式解析器；前端是指词法分析器和解析器。还有一个中间端，通常与优化和IR（中间表示）有关，这将在稍后解释。后端通常与前端无关，它只关心接收到的AST。这意味着可以为多个不同的前端或语言重用相同的后端。著名的GNU Compiler Collection就是这种情况。

我找不到比我自己的C编译器后端更好的代码生成器示例了。

在生成汇编代码之后，这些汇编代码将被写入新的汇编文件（.s或.asm）。然后，该文件将传递给汇编器，汇编器是汇编语言的编译器，它将生成相应的二进制代码。然后，这些二进制代码将被写入新的目标文件（.o）。

目标文件是机器码，但它们不能直接执行。为了使它们成为可执行文件，目标文件需要链接在一起。链接器读取通用的机器码，并将其转换为可执行文件、共享库或静态库。链接器是因操作系统而异的应用程序。任何第三方链接器都应该能够编译您的后端生成的目标代码，因此在编写编译器时不需要创建自己的链接器。

编译器可能具有中间表示（IR），用于在优化或转换为另一种语言时无损地表示原始指令。IR不再是原始代码，而是为了寻找代码中潜在优化而进行的无损简化。循环展开和向量化都是使用IR完成的。

总结
当您理解编译器时，您将能够更有效地使用您的编程语言。也许有一天您会对创建自己的编程语言感兴趣？我希望这篇文章能对您有所帮助。

资源和更深入的阅读材料