如何生成从虚构语言解析的AST树代码？

Question

我在http://parsingintro.sourceforge.net/上阅读了这篇文章,并决定尝试将其重写为Ruby中的练习.有两个原因使我这样做,我想了解更多关于如何编写Ruby(Java,PHP,C和一些Python的背景)的知识,我想了解更多关于解析器/编译器的知识.

我在https://github.com/parse/boatcaptain上发布了所有代码.正在生成AST树,不幸的是,本文的作者没有涉及代码生成和优化等概念.

任何人都可以通过指导我如何将这个AST树变成"代码"来帮助我吗？这是生成的AST树

几年前我用Java编写了一个计算器,它使用了很多类似于我在解析器中使用的术语和技术.但是在计算器中,我有eval()的方法 - 我的"类",因此得到输出,我应该在这里做类似的事情吗？计算器来源:https://github.com/parse/Uppsala-University-Courses/blob/master/ImpOOP-Calculator/src/Calculator.java

我也很喜欢我编写Ruby的方式的反馈,我相信我仍然像编写Python一样编写Ruby,缺少Ruby的一些优点.

Answer 1

最基本形式的代码生成只是遍历中间形式 - AST - 并以目标语言发出相应的指令。

首先，您需要选择目标语言。您希望输入文件在什么平台上运行？您可以选择的主要选项有：

• 源到源翻译器
• 本机代码的编译器
• 字节码编译器（在虚拟机上即时运行）

目标语言的选择可以决定您在语言之间进行映射所需的工作量。例如，将面向对象的类映射到 ASM 可能/将会很棘手。将固有的过程代码映射到基于堆栈的代码也可能是一个挑战。

无论您选择哪种语言，问题无疑都会归结为以下过程：访问树的节点，并根据它们的类型发出相应的指令。

假设您在 AST 中遇到以下节点（如您链接到的节点）：

        =
delta       /
      alpha   beta

由于它是一个“赋值”节点，代码生成器知道它必须在将该值粘贴到 LHS 之前评估树的 RHS；'三角洲'。于是我们顺着RHS节点往下看，发现这是一个除法运算。然后我们知道我们必须评估该节点的 LHS 和 RHS，然后再将它们相除，并将结果粘贴到“delta”中。

现在我们向下移动 LHS，看到它是一个变量，然后我们发出一条“加载”指令。我们沿着 RHS 向上然后向下返回，同样为“beta”发出“负载”。然后，我们沿着树向上走（同时携带 alpha 和 beta），对两个操作数发出除法指令，存储该结果，将其沿着树向上传递给赋值发射器，然后将其存储在“delta”中。

所以这个片段的结果代码可能是：

load alpha
load beta
tmp = div alpha beta
store delta tmp

至于预先存在的 Ruby 代码生成器库，我不知道，抱歉。我希望这个答案对您来说不太笼统或过于简单。