bison - Lex Yacc C 中的解释器

Question

我正在用 Flex 和 Bison 为 C 语言编写一个解释器。我不知道如何生成 AST，我想知道如果我只是按照解释器看到的那样解释代码，会有什么样的性能差异？

我还想知道 Bison 是否会在幕后生成 AST，我在某些论坛和其他网站上听说过它会在幕后生成 AST，而在其他网站上我看到人们创建了自己的 AST？

在此先感谢弗朗西斯

Answer 1

回复：如何使用 Bison 构建 AST：

有关从 Bison 构建 AST 的简单示例，请参阅此站点：EPaperPress。

另请参阅Mitsuhisa Sato 的示例（这是使用 Bison 的简单解释器的代码）。

回复：使用 AST 的解释器与直接解释的性能差异。

有很多方法可以编写解释器 - 下面的列表是从（通常）最慢到最快的性能（注意对于琐碎的程序，可能差别不大。但是对于多次重复相同代码的程序，可能会有差别很大）：

1. 直译
2. 做一些预处理，例如，标记化和剥离评论
3. 建立一个 AST 并解释它
4. 转换为中间代码 - 字节代码 - 通过 AST 与否 - 并解释

对于速度比较，您可以执行以下操作：

访问：Tom Gibson 的 Tiny C 网站。

并下载适当的解释器——Tom Gibson 的 Tiny C for DOS，也许是 Windows或Tom Gibson 的 Tiny C for Linux。

这是一个纯粹的解释器——上面的#1。编写一个计算素数或类似的小程序，然后计时。

Sato 网站上的“Tiny C”包括一个解释器，它从上面的 AST - #3 进行解释。为它写一个类似的程序，并计时。

最后，从Marc Feeley 的 Tiny C获得另一个 Tiny C。

这个创建了一个 AST，将其转换为字节码，然后解释它 - 上面的 #4。为这个重写你的小程序，然后计时。

我希望这有帮助！

Answer 2

Bison 不会自行生成 AST，但它确实具有旨在帮助您编写代码来构建 AST 的功能。

首先，该%union语句允许您定义一个联合，表示您将在 AST 中使用的节点类型，因此您可以为变量声明、表达式等定义类型。

然后，它允许您指定联合成员与在识别特定模式时执行的代码相关联，因此您可以进行类型检查，即使 C 编译器基本上不对联合进行类型检查。

就性能差异而言：几乎无法猜测。通常首先构建 AST 旨在作为一种优化，但优化的效果究竟取决于您正在解释的语言和（尤其是）您编写的代码。