c++ - 在 C++ 中表示多遍抽象语法树 (AST)？

Question

我目前正在探索设计一个在多个阶段转换其 AST 的编译器。这个想法是，从解析树开始，每次传递都会转换树，直到生成的 AST 被优化并包含生成中间代码所需的树的每个节点中的所有必需信息(在本例中为 LLVMIR)。遍历树可能会显着改变其结构，例如通过 operator precedence parsing 将运算符和操作数列表更改为有序操作的层次结构。 .请注意，通过可能会使结构的某些部分完全保持不变。

所以，我的问题是如何最好地(阅读:最容易，尽可能少地重复)表示在 C++ 中具有多个中间表示的 AST？我希望每个阶段的 AST 版本中的节点类型在编译时尊重它们的不兼容性。我认为关键问题是我应该如何表示结构中在传递之间不发生变化的部分，同时避免重复代码？我想这是编译器作者过去多次解决的问题。

请注意，我目前使用的是 Boost Variant而不是我的 AST 中的正常运行时多态性，并且希望有一个与之兼容的解决方案。

Answer 1

AST 节点本身并不需要大量的复杂性。我认为所有这些 AST 节点机制都是矫枉过正。

AST 的问题不在于节点类型安全；它的树形安全。 AST 代表(可能)某种语言 L 的一些有效实例。理想情况下，您想要的是对 AST 进行转换以产生其他有效的 AST(语言 L 的实例)。您不会通过保证任何一个节点具有有效类型来保证这一点。你只能通过保证任何树补丁产生一个有效的树来做到这一点。如果树操作是原子的(例如，“更改节点”、“替换子节点”、“替换父节点”)并且单独应用，这将很难做到；经过几个这样的步骤，你能准确地说出这棵树的什么？

这最好使用一种树重写事务来完成，例如，语法结构对语言 L 有效的源到源转换，并且应用于对该转换有效的地方。

大多数标准program transformation systems做这个。他们通过持有 L 的语法模型并检查所提出的转换是否类型良好来实现这一点。这确保了语言 L 到语言 L 的转换保持良好的格式。

如果转换从一种语言 A 映射到另一种语言 B，则更难做到这一点；如果应用了一些这样的转换，您通常会得到一个混合类型的树，这在任何一种语言中都是不合法的。小心，可以定义一组转换，将语言 A 的所有子树映射到语言 B，并详尽地应用它们；那么你希望得到的树对于 B 来说是良好的。你可以通过坚持每当 B 补丁插入混合树中时，如果它与另一个 B 补丁相邻，那么得到的复合 B 补丁是好的形成。您可以使用相同样式的语法检查来做到这一点。

使用这些想法，您可以构建一个通过一系列“表示”(语言 A、B、C ......)映射 AST 的系统，并相信结果树的形状良好。这个想法推广到图重写。