编译器做什么：解析

解析是编译故事的开端。虽然这对我们来说可能意味着一些美妙的东西，但我们的源代码仅仅是字符数据流。解析器的作用就是接收这些数据并将其翻译成编译器能理解的东西。这包括提取符号和运算符，创建解析树，然后将其转换为抽象语法树。在本文中，我将稍微探讨一下这个过程是如何发生的。

一个简单的例子：

第一阶段是接收原始代码并生成解析树。考虑下面的基本表达式。

( ( 1+23 ) * 2 ) / ( -1.4 )

第一步是为这些数据创建一个标记流。使用正则表达式、手动扫描文本或使用特殊的词法分析器，文本就被标记化了。上面的表达式会产生这些标记：(, (, 1, +, 23, ), *, 2, ), /, (, -, 1.4, )。

这个标记化通常不是作为一个独立步骤完成的。相反，标记通常是按需一个接一个地读取的。这使得标记能够依赖于上下文：提取方式可以根据正在处理的代码的逻辑部分而有所不同。

需要从标记流中构建一棵树。这棵树将解决所有运算的顺序。对于上面的情况，这相当容易，因为每个子表达式都用括号括起来了。树看起来是这样的。

当然，这种表达式不太可能直接出现在代码中；它更有可能输入时使用更少的括号和空格。

(1+3)*2/-4

尽管这会产生不同的标记流，但必须将此表达式的结果解析为相同的树。这需要解析运算符优先级，这使得解析器稍微复杂一些。幸运的是，这类表达式解析已经很成熟，并且有一些工具可供使用。我在 Leaf 中使用的就是“逆波兰表示法转换算法”（Shunting-yard algorithm）。该算法在上面的表达式上的结果是后缀表达式 1 3 + 2 * -4 /。

实际上，- 在后缀表示法中也应该是一个运算符。它可以是二元加法运算符，也可以是一元负号运算符。在后缀表示法中很难同时显示它们，但如果使用名称，它将看起来像 1 3 add 2 mul 4 neg div。

尽管基本，逆波兰表示法转换算法是自定义解析器的良好起点。在 Leaf 中，我保留了它基本的堆栈设置，但在其工作方式上进行了一些重要的修改，或者说扩展。

语句

编程语言不仅仅由简单的表达式组成。接下来最常见的结构是语句、函数调用和赋值。

var a = pine( 13, b )

这里唯一特殊的部分是 var 关键字。整个 a = pine( 13 ) 部分仍然是一个表达式。整个东西仍然会生成一棵树，但现在它可能有多个子节点。

在这一点上，我们可能会看到编译器之间出现很多分歧。内存中的形式可能是树、列表，或者是每种操作的特殊节点结构。在 Leaf 解析器中，在此初始阶段我严格保持这种抽象树的形式。

在语句之上是代码块、函数以及语言提供的其他任何东西。

defn pine = (x, y) -> {
    return 2 * x + y
}

var a = pine(4,5)
trace(a)

为了好玩，这是 Leaf 为该代码生成的解析树。

它如何解析

我省略了很多细节。显然，解析完整的语言结构需要比逆波兰表示法转换算法更多的东西。

编译器的一种常用方法是使用自定义递归下降解析器。这基本上遵循语言的结构。解析器将拥有类似 parse_block、parse_tuple、parse_expression 或 parse_function 的函数，并在遇到每个语言构造时简单地调用它们。单个标记直接匹配，或使用正则表达式库进行匹配。

还存在称为解析器生成器的工具，它们承诺完成大部分工作。然而，根据我的经验，我发现解析器生成器有些不足。据我所知，许多编译器使用手写的递归下降解析器而不是这些生成器。

语法树

之前的步骤是生成解析树。我们真正想要从解析器得到的是抽象语法树。这样，各种标记就可以正确地翻译成高级语言构造，并且可以消除文本语法的任何残留。

并非所有编译器都严格区分解析树和语法树。也可以将文本更线性地组合成语法树，在它们出现时就处理语句和代码块。

语法树是编译器内存中代码的特定表示。它使用模拟语言的类型，例如 function、variable、statement 或 block。而解析树非常通用，语法树则高度具体。这是编译器实际理解代码所必需的。

创建解析树已经完成了大部分艰苦的工作。与此相比，转换为语法树感觉上更多的是一项繁重的工作。它主要是一个序列化问题，类似于将复杂的 JSON 对象树转换为类型化结构。两棵树匹配得越好，在这个阶段需要进行的调整和平衡就越多。

在不完全像修改过的解析树的情况下，以通用方式显示这些内存结构有些困难。当“展平”为树形结构时，类层次结构也可能更难理解。在 Leaf 中，我基本上以 Leaf 本身的一个展开的、略有修改的形式转储了该结构。

解析后前一段代码的转储。

@lifetime(global) multi pine : literal = ( x : , y : ) ->  {
    return add <- ( mul <- ( 2/1, x ), y );
} 
single a = pine <- ( 4/1, 5/1 )
trace <- ( a )

继续

不幸的是，并非所有语言都设计成允许这种独立的解析阶段。像 C++ 甚至 C# 这样的语言，有一些构造要求解析器做比解析更多的额外工作。一些解析工作，如构造函数和变量声明，需要解析器至少对符号和语义有基本的了解。尽管如此，它们仍然进行解析，最终生成语法树。

拥有语法树就意味着解析器的工作结束了。它完成了它的任务，并将交给编译的下一阶段。

如果您想了解更多关于编译器的信息，请在 Twitter 上关注我。我还有很多关于这个主题的内容要写。如果您想听听某个特别的话题，或者想安排一次演示，请随时联系我。