如何使用上下文无关语法从标记列表构建抽象语法树？

Question

我正在 Javascript 中编写一个 C 编译器，纯粹是为了充实（到目前为止，我预计它没有实际用途，我可能不会维护它）。

我写了一个可以成功标记化的词法分析器，给定一个正则表达式列表和该正则表达式匹配的类型，任何字符串。

我已经能够成功地标记化 C 源代码（公平地说，稍微减少了 C；我需要添加更多标记器模式来捕获所有内容）。我现在想将 AST 构建为源语言和翻译后的程序集之间的中间形式。

为此，我正在尝试实现一个使用上下文无关语法的函数，定义为具有

的对象

键 → 目标（表达式、函数声明、转换表达式等），并且
值 → 映射数组
- （其中映射是构成目标的符号的数组[顺序很重要]）。

这是一个可能会提供给解析器的示例 CFG（这是 this C grammar 的改编摘录）：

var cfg = {
    "cast_exp": [
        ["unary_exp"],
        ["(", "type_name", ")", "cast_exp"]
    ],   
    "unary_exp": [
        ["primary_exp"],
        ["++", "unary_exp"],
        ["--", "unary_exp"]
    ],
    "primary_exp": [
        ["id"]
    ]
};

id 是我的标记器选择的类型之一，所以我想我们可以考虑 "primary_exp" 一个开始符号。

现在，我的想法是递归地做这个；也就是说，拿起第一个标记并将其与一个起始符号相匹配。对剩余的token进行递归，将我们之前调用匹配到的目标发送过去，看看我们刚刚匹配到的目标是由什么生产规则组成的。

这对我和我的看法没有太大意义，我会迷失在无限递归中（或者在非常长的源文件上遇到堆栈溢出）。

我如何编写一个函数来遍历我的标记数组，并使用上述 CFG 构建 AST？ 因为我这样做是为了丰富和作为个人挑战，如果您愿意，可以提供代码，但我正在寻找更多指导和此类算法的广义描述。

Answer 1

您可以实现一个 Earley 解析器。（维基百科网站有代码，所以我不提供任何东西）。

这样的解析器在使用令牌时从一个状态转换到另一个状态。在每个州，它持有 set of "items":

 {  I1  I2 ...  In }

每个单独的项目 Ik 都是一个规则，以及该规则的处理量（一个名为 "dot" 的地方）。

对于规则

  R = A B C D;

其中 A 和 B 已经出现，R 的项目在概念上是相同的规则，但带有点标记：

  R = A B <dot> C D ;

带点的表示已经看到A和B，还需要找到C。 state/item 集（可能）看起来像：

 {  P = Q <dot> R S ;I1
    R = A B <dot> C D ;
    C = <dot> X Y ;
 }

每一项 Ik 代表对目前所见输入的一种可能解释；有多个项目的原因是输入可能有多种解释对输入流中的当前点有效。处理令牌将更改 state/this 项集。

对于我们的示例规则 R，当解析器找到 C （作为输入流中的标记，或者如果某些其他规则减少并生成其左手边作为非终结符），点被移动：

 R = A B C <dot> D;

正在为下一个解析器状态中的项集创建一个新项。

为每个标记处理项目集中的所有规则；如果允许解析器 "shift" 遍历下一个规则元素，则带有修改点的项目将置于下一组的状态中；否则该规则不再是对输入的有效解释，并被丢弃（例如，不放在下一组中）。当点被移动时，它表示新的输入是可能的（对于上面的规则 R，D 现在是可能的），并且允许 D 被处理的规则被添加到新的状态，在规则的开头有点。这可能会向集合中添加几个新规则。

当一个点在远端结束时：

 R = A B C D <dot> ;

那么实际上 R 已被视为非终结符（这称为 "reduction" 到 R）并且可用于在当前状态下提及 R 的其他规则中推进点：

 P = Q <dot> R S ;

过渡到 P = Q R S ；

现在，在处理令牌时，此过程应用于当前状态下的所有个项目（规则+点）。

解析器从第一个状态开始，它有一个单元素集，由 goal（你所谓的 "start symbol"）规则和一个点表示没有部分规则已被消耗，在您的情况下：

{  primary = <dot> id ; }

稍加思考就会得出结论，目标规则始终位于项目集中，其点位于某处。当目标规则中的点从目标规则的末尾脱落时，解析完成，例如，当目标规则减少到目标标记时，和输入流被完全消耗。

Earley 解析器比较快，而且很通用；他们将解析任何上下文无关的语言。那是惊人的强大。（如果您了解 Earley 解析器如何处理项目，那么您就了解了了解 LR 解析器如何工作所需了解的大部分内容）。而且它们很容易构建。

维基百科网站有一个更详细的示例。

至于使用 Earley 解析器（或任何类似类型的解析器）构建树，每当发生 R 的归约时，您都可以构建一个树节点，其根为 R 类型，其子节点是之前为它的元素。

显然，在处理终端令牌t时，我们会为t构建一个单元树。 [很容易理解为什么当你意识到你的词法分析器实际上是一个子解析器时，它是 "reducing" 字符串到终端标记。您可以将词法分析器规则放入对字符终端标记进行操作的语法中；出于效率原因，您只是选择不这样做。你可以这样做很有趣； Earley 解析器会做的很好，但会运行相当慢，因为现在它在更大的规则集上，在每个字符的基础上进行所有的项目集管理。

在解析时跟踪所有这些东西似乎有点棘手，但实际上并不难。我把它留给 reader.

作为对比，see how to do all this parsing and tree building using hand-coded recursive descent parsing。（这些没有那么强大，特别是它们可能很难使用左递归语法规则，但如果你有语法，它们真的很容易写）。

如何使用上下文无关语法从标记列表构建抽象语法树？

How do I construct abstract syntax trees from a list of tokens using a context-free grammar?

javascript

compiler-construction

parsing

abstract-syntax-tree

context-free-grammar