在C++中表示多次传递抽象语法树(AST)？

Question

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

所以,我的问题是我如何最好(阅读:最容易,尽可能少的重复)代表一个在C++中有多个中间表示的AST？我希望每个阶段的AST版本中的节点类型在编译时遵守它们的不兼容性.我认为关键问题是如何在避免重复代码的同时代表结构中不改变通道的部分？我想这是编译器作者过去多次解决的问题.

请注意,我目前在我的AST中使用Boost Variant而不是普通的运行时多态,并且希望解决方案与它兼容.

Answer 1

AST 节点本身不需要大量的复杂性。我认为所有这些 AST 节点机制都太过分了。

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

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

大多数标准程序转换系统都这样做。他们通过持有 L 的语法模型并检查所提出的变换是否类型正确来实现这一点。这确保了语言 L 到语言 L 的转换保持格式良好。

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

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

Answer 2

下面是对基于类型安全的boost::variantAST 的快速介绍。

我添加了一个简单的“结构保留变换”，它只是更改每个 AST 节点中存储的数据类型。然而，从理论上讲，您可以编写一个任意的代码astFunc来对节点进行结构和基于数据的转换 - 只需编写一个type_list包含前后每个节点中的有效类型的代码即可。

template<typename... Ts>
struct type_list {};

// specialize data_type to store something special in your AST node:
// (by default, an entry means "the type of the data")
tempalte<typename T>
struct data_type { typedef T type; };
template<typename T>
using DataType = typename data_type<T>::type;

template<template<typename>class F, typename typelist>
struct map_types;
template<template<typename>class F, template<typename...>L, typename... Ts>
struct map_types<F, L<Ts...>> {
  typedef L< F<Ts>... > type;
};
template<template<typename>class F, typename typelist>
using MapTypes = typename map_types<F, typelist>::type;

template<template<typename...>class F, typename typelist>
struct apply_list;
template<template<typename...>class F, template<typename...>class L, typename... Ts>
struct apply_list<F, L<Ts...>> {
  typedef F<Ts...> type;
};
template<template<typename...>class F, typename typelist>
using ApplyList = typename apply_list<F, typelist>::type;
template<typename typelist>
using Var = ApplyList< boost::variant, MapTypes<DataType, typelist> >;

template<typename type_list>
struct AST_Node {
  typedef std::unique_ptr<AST_Node> upAST_Node;
  std::vector<upAST_Node> children;
  Var<type_list> data;
  template<typename T>
  AST_Node( T&& t ):data( std::forward<T>(t) ) {}
};
template<typename type_list>
using upAST_Node = typename AST_Node<type_list>::upAST_Node;

template<typename before_types, typename after_types>
using typeFunc = std::function< Var<after_types>(Var<before_types>) >;

template<typename before_types, typename after_types>
using astFunc = std::function< upAST_Node<after_types>(upAST_Node<before_types>) >;

template<typename before_types, typename after_types>
astFunc<before_types, after_types> elementWiseTransform( typeFunc<before_types, after_types> func ) {
  return [func]( upAST_Node<before_types> before )->upAST_Nodes<after_types> {
    upAST_Node<after_types> after( new AST_Node<after_types>( func( before ) ) );
    after->children.reserve( before->children.size() );
    for( auto& child: before->children ) {
      after->children.push_back( elementWiseTransform(func)(std::move(child)) );
    }
    return after;
  };
}

现在这只是一个开始。

您可以更进一步，让每种类型的节点都有一组不同类型的子节点，甚至不同的数量。只需为每种类型的节点（例如 my ）创建特征类data_type，例如children_types. 然后使用与我定义类似的技术来Var定义孩子的类型。基本上，您通过 的链接variant获得了。哎呀，你可以将孩子们和一起捆绑成一个变体。std::vector< AST_Node<ChildType<type_list_element>>>MapTypesstd::vectordata

这将允许您为单个类型编写映射AST_Node（这会生成另一种AST_Node类型），将它们聚合在一起并生成一个AST_Node<before, after>函子，然后该函子将遍历树。有些函子会对数据进行操作，然后让父逻辑接管子逻辑，有些函子会转换整个子树，有些函子会对数据进行操作并阻止父逻辑对子逻辑运行。

这项技术很棘手，因为您必须从各个函数中合成 boost 变体访问者，而不需要将它们全部堆积在一起。如果你看这里，你会看到一些关于如何获取一堆std::function<T(U)>并将它们转换为一个函子的技巧，该函子接受 的任何一个并集U。投入一些工作来计算返回类型的并集（type_list删除重复类型的简单方法，然后将其泵入boost::variant，可能会做到这一点）——这样的“合并函子”将是有效的访问者。

现在你可以编写“重新映射operator_add类型的AST节点”函子，以及“重新映射operator_mult类型的AST节点”，以及其他一些函子，将它们捆绑在一起形成一个大型函子，将它们扔给AST遍历算法，然后让它喷出一棵 AST 树，其中一些类型转换为其他类型......

但这会是很多工作。

哦，我们可能需要“阶段标记”，其中阶段 1 和阶段 2 AST 是不同的类型。我们可以用type_list它的阶段来标记每个类型，或者我们可以只标记AST树本身。AST哎呀，我们可以为使用其他未使用的阶段命名struct，并将阶段的进展定义为类型到类型函子，该函子在 的签名中应用和强制执行astFunc<before_phase, before_types, after_phase, after_types>。

所以这还不错。我们创建一系列type_list节点类型。这些类型不必是实际存储的数据。但确实可以。

我们创建一个data_type特征类，将每个节点类型映射到存储的数据。我们创建一个child_types特征类，将每个节点类型映射到子 AST 的 type_list。

每个AST_Node商店都有一个variant<AST_Concrete_Node<Ts>...>. AST_Concrete_Node包含 aDataType<T> data;和 a MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children; （又名std::vector< AST_Node<ChildrenTypes...> >，但你不能直接这么说）。

接下来，AST_Concrete_Node<T>转换函数通过一些棘手的模板元编程结合在一起，成为 boost 变体访问者。这一步确实很棘手，但我认为是可行的。完成了额外的工作，以便跳过未提及的类型，因此我们不必不断地说“哦，我们不想变换节点 X”，而是必须说“如果我们击中节点 Y，则不要改变它的孩子”。

在这一点上，我要说的是我在胡言乱语——以前没有这样做过，在具体实施这种混乱的类型体操时遇到的问题将压倒我抽象推理的能力。但这个想法希望是有用的——我们有类型安全的节点类型转换，我们将它们聚合在一起并生成类型安全的树转换。该树不仅仅是一棵通用变体的抽象树，而且是一棵每个节点都知道其子节点允许的类型的树，并且递归地知道相同的类型。如果我们在兔子洞里走得足够远，我们甚至可以处理“这必须有 3 个孩子，其中第一个是 a int，第二个是 a Bob，第三个是 a ”。double