编程语言解析过程解析

编程语言的源代码本质上是字符数据流。解析器的作用是将这些数据转换成编译器能够理解的形式。这涉及到提取符号和操作符，创建解析树，并将解析树转换成抽象语法树。本文将探讨这一过程是如何发生的。

简单示例

第一阶段是将原始代码转换成解析树。考虑下面这个基本表达式：

逻辑上的第一步是创建这个数据的标记流。使用正则表达式、手动扫描文本或使用特殊的词法分析器，文本被标记化。上述表达式产生这些标记：

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

从标记流中需要构建一棵树，这棵树能够解析所有操作发生的顺序。在上面的例子中，由于每个子表达式都被括号括起来，所以这相当容易。这棵树看起来像这样：

即使这个表达式产生了不同的标记流，但必须导出相同的树作为结果。这需要解析操作符优先级，使解析器稍微复杂一些。幸运的是，这种类型的表达式解析是老生常谈，有一些工具可以处理。在Leaf中使用的叫做“Shunting-yard算法”。这个算法对上述表达式的结果是一个后缀表达式：

实际上，'-' 也应该是一个后缀表示中的操作符。它可以是二元加法操作符或一元负操作符。在后缀表示中很难同时表示它们，但如果用名字表示，它将看起来像：

虽然基础，但Shunting-yard算法是自定义解析器的良好起点。在Leaf中，保留了它具有的基本栈设置，但对其工作方式进行了一些重要的修改或扩展。

语句

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

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

在这个阶段，编译器可能会有很大的差异。内存中的形式可能是一棵树、一个列表，或者每个操作的特殊节点结构。在Leaf解析器中，在这个初始阶段严格保持这种抽象树形式。

解析树

在语句之上是块、函数以及语言提供的其他内容。

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

如何解析

略过了很多细节。显然，要解析完整的语言结构，需要的不仅仅是Shunting-yard算法。

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

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

抽象语法树

前面的步骤是生成解析树。真正想要从解析器得到的是抽象语法树。在这种树中，各种标记已经被正确地转换成高级语言结构，任何文本语法的痕迹都可以消除。

并非所有编译器都有这种严格的解析树和语法树之间的分离。也有可能以更线性的方式将文本组装成语法树，处理语句和块。

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

创建解析树已经完成了大部分艰苦的工作。与此相比，转换为语法树感觉更像是苦差事。它主要是一个序列化问题，有点像将复杂的JSON对象树转换成类型化结构。这两个树的匹配程度决定了这个阶段需要进行多少洗牌和平衡。

在没有具体说明的情况下，很难以通用方式显示这些内存结构，而不仅仅是看起来像修改过的解析树。类层次结构在“展平”成树时也可能更难理解。在Leaf中，基本上以Leaf本身的扩展形式和稍微修改的形式转储这个结构。

在解析后，上述代码的转储如下：

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