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

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 并将其与一个起始符号匹配。递归剩余的 token ，跨上次调用中匹配的目标发送，并查看由刚刚匹配的目标组成的生产规则。

这对我和我的看法来说并没有太大意义，我将在无限递归中迷失(或者在很长的源文件上遇到堆栈溢出)。

如何编写可以遍历 token 数组并使用上述CFG构造AST的函数？ 因为我这样做是为了充实自己和作为个人挑战，所以如果您愿意，您可以提供代码，但是我正在寻找更多有关此类算法的指导和广泛的描述。

Answer 1

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

这样的解析器在消耗 token 时会从状态转换为状态。在每种状态下，它都包含一组“项目”:

 {  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代表到目前为止对输入的可能解释；之所以存在多个项目，是因为输入可能具有对输入流中的当前点有效的多种解释。处理 token 将更改状态/这组项目。

对于我们的示例规则R，当通过解析找到C时(作为输入流中的标记，或者如果某些其他规则减少并且将其左手端作为非终结符生成)，则将移动点:

 R = A B C <dot> D;

为在下一个解析器状态下设置的项目创建一个新项目。

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

当圆点在远端结束时:

 R = A B C D <dot> ;

那么实际上R已被视为非终结符(这称为R的“归约”)，可用于在当前状态下提到R的其他规则中将点推进:

 P = Q <dot> R S ;

转换为P = Q R S；

现在，当处理 token 时，此过程将应用于当前状态下的所有项目(规则+点)。

在第一个状态下，解析器以包含目标(您称为“开始符号”)规则的单元素集开始，并带有一个点，表明在您的情况下该规则的任何部分都没有被消耗:

{  primary = <dot> id ; }

稍加思考，您就可以得出结论，目标规则始终停留在点集位于某处的项目集中。当目标规则中的点落在目标规则的末尾时，例如，当目标规则缩小为目标 token ，并且输入流被完全消耗时，解析完成。

Earley解析器相对较快，并且非常通用。他们将解析任何上下文无关的语言。这是惊人的强大。 (如果您了解Earley解析器如何处理项目，那么您将了解了解LR解析器如何工作所需的大部分知识)。而且它们很容易构建。

Wikipedia网站上有一个更详细的示例。

对于使用Earley解析器(或任何类似类型的解析器)构建树，只要将R简化，就可以构建一个树节点，该树节点的根为R类型，其子代为先前为其元素构建的树。

显然，在处理终端 token t时，会为t建立一个单位树。 [很容易理解，为什么当您意识到您的词法分析器实际上是一个子解析器时，它会将字符串字符串“减少”到终端 token 中。您可能已经将词法分析器规则放到对字符终端标记进行操作的语法中了；您出于效率考虑而选择不这样做。您可以这样做很有趣； Earley解析器可以很好地运行，但运行起来会很慢，因为现在它正在基于每个字符的更大规则集上进行所有项目集管理。]

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

作为对比， see how to do all this parsing and tree building using hand-coded recursive descent parsing。 (这些功能不那么强大，尤其是在使用左递归语法规则时可能会遇到困难，但是如果您有语法的话，它们确实很容易编写)。