compiler-construction - 编译一门语言的优势 vs 一构建就执行 AST

Question

将程序编译为机器代码而不是简单地从源构建 AST 并在遍历树时执行操作有什么好处/缺点？

您是否有某些原因想要做一个而不是另一个？

Answer 1

解释 AST 通常比运行执行相同操作的机器代码慢得多。 20 的系数是典型的。

一个优点是 AST 生成速度更快，因此生成代码所需的时间比大多数编译器少。 AST 解释器也往往比编译器更简单，因为可以忽略整个代码生成阶段。

因此，如果您有一个不进行大量计算的程序，它会在解释器的帮助下启动并运行得更快。另一方面，如果您的代码在循环稀缺的环境中经常或连续运行，则最好编译。

一些编程环境(例如许多 lisps)包括用于开发代码的解释器，因为它支持快速调试周期和用于在开发完成时生成快速代码的编译器。其中一些系统允许自由混合解释和编译的代码，这本身就很有趣。

编译为字节码是一个折衷方案:编译速度比机器码快，但执行速度比 AST 快。尽管如此，现代字节码解释器通常会在您的程序运行时“及时”编译为 native 代码。这例如是 Sun 的 HotSpot JVM 名称的来源。它将 Java 字节码中的“热点”编译为 native 代码，以在运行时加速程序。

回复评论中的问题

关于上面提到的20的因数有一个问题。支持这个数字的引用文献很旧，因为很少有现代语言系统使用纯 AST 解释器。 (一个值得注意的异常(exception)是命令 shell ，但它们中的大多数是很久以前开发的，速度基准并不常见。)它们太慢了。我的上下文是 lisp 解释器。我已经实现了几个。 Here for example is one set of Scheme benchmarks .与 AST 解释器对应的列很容易挑选出来。如果有需求，我可以从 ACM 数字图书馆文件中发布更多类似的内容。

另一个粗略的基准测试:Perl 使用高度优化的 AST 解释器。在我的机器上以紧密循环方式添加 1000 万个浮点数需要大约 7 秒。编译后的 C (gcc -O1) 大约需要 1/20 秒。

评论者以添加 4 个变量为例。分析忘记了查找的成本。解释器和编译器之间的一条明确分界线是符号的预计算地址或帧偏移。在“纯”解释器中，没有。所以添加 4 个数字需要在运行时环境中进行 4 次查找，通常是一个哈希表——至少 100 条指令。在良好的编译代码中，在 x86 上添加 4 个整数需要 2 条指令，另外还有一条指令来存储结果。

“纯”AST interpeters 和编译后的机器代码之间有很多阴影。根据语言的不同，可以将符号偏移量编译到 AST 中。这有时称为“快速链接”。该技术通常将速度提高一倍或 2 倍或更多。然后是“编译为字节码并运行”的系统，如 Python、PHP、Perl、Ruby 1.9+。它们的字节码是有效的线程代码(操作码会导致非常复杂的事情发生)，因此它们比机器代码更接近 AST。然后是我上面提到的 JIT 字节码解释器。

关键是 20 个纯 AST 解释器的因素是一个书挡，而机器码是另一个。中间有许多变体，每个变体都有优点和缺点。