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

Question

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

javascriptparsingcompiler-constructionabstract-syntax-treecontext-free-grammar

4

我正在使用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" 视为起始符号。

现在，我的想法是递归地执行这个过程；也就是说，捕获第一个标记并将其与一个起始符号进行匹配。对剩余的标记进行递归处理，在上一次调用中匹配到的目标作为参数传递，并查看由刚刚匹配到的目标组成的产生式规则。

这对我来说没有太多意义，我认为我会陷入无限递归（或在非常长的源文件上遇到堆栈溢出）。

我该如何编写一个函数，能够遍历我的标记数组，并使用上述 CFG 构建 AST？ 因为我正在做这个工作以丰富自己并挑战自己，如果您愿意，您可以提供代码，但我更希望得到指导和广义上的算法描述。

- Purag

2

Closer：问题并不过于宽泛，答案也不会太多，而且可以提供符合该网站格式的答案（请参见我的回答！）。你的关闭理由是无效的。 - Ira Baxter

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ira Baxter · Accepted Answer

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

这样的解析器在消耗标记时从状态转换到状态。在每个状态下，它都持有一组“项”：

 {  I1  I2 ...  In }

每个单独的项目Ik都是一条规则，表示已处理该规则的程度（一个称为“点”的位置）。

对于一条规则：

  R = A B C D;

当A和B都被看到时，R的项目在概念上与带有点标记的相同规则。

  R = A B <dot> C D ;

用点号表示A和B已经被找到，需要找到C。状态/项目集可能如下：

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

每个项Ik表示到目前为止输入的可能解释；之所以有多个项是因为输入可能有多个当前点上有效的解释。处理令牌将改变状态/这个项集。

对于我们的示例规则R，当解析器找到一个C 时（无论是作为输入流中的令牌还是如果某些其他规则缩减并将其左侧产生为非终端符号），点会被移动：

 R = A B C <dot> D;

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

当点最终到达末端时：

 R = A B C D <dot> ;

然后实际上R被视为一个非终结符（这被称为对R的“规约”），并且可以用于推进当前状态中提到R的其他规则中的点：

 P = Q <dot> R S ;

转换为 P = Q R S;

现在，随着处理标记的进行，该过程应用于当前状态中所有项目（规则+点）。

解析器从第一个状态开始，其中包含一个元素集，该集合由具有点表示未使用规则任何部分的目标（您称之为“起始符号”）规则组成，在您的情况下：

{  primary = <dot> id ; }

稍加思考，您就会得出结论：目标规则始终与其点在某个项目集中。当目标规则中的点掉落到末尾时（例如，当目标规则减少为目标令牌，并且输入流被完全消耗时），解析就完成了。

Earley分析器相对较快，并且非常通用；它们将解析任何上下文无关的语言。这是令人惊讶的强大。（如果您了解Earley分析器如何使用项，您就了解大部分需要了解LR分析器的知识）。而且它们相当容易构建。

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

至于使用Earley分析器（或任何类似类型的解析器）构建树，在发生到R的减少时，您可以构建一个根为类型R，子节点为其元素先前构建的树的树节点。

显然，在处理终端令牌时，需要为t构建一个单元树。[当你意识到你的词法分析器实际上是子解析器时，“缩减”字符字符串成终端令牌就变得很容易理解了。你可以将词法分析规则放入操作字符终端令牌的语法中；出于效率原因，你选择不这样做。你可以为此而尝试一下；Earley解析器会表现得很好，但运行速度会相当慢，因为现在它正在对更大的规则集进行所有那些项目集管理，以每个字符为基础。]

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

作为对比，请看如何使用手写递归下降解析来完成所有这些解析和树构建。（它们的功能不如强大，特别是对于左递归语法规则可能会有困难，但如果你有一个语法，它们非常容易编写）。