我目前正在研究设计一个可以在多个阶段转换AST的编译器。其思想是从解析树开始，每次传递都转换树，直到得到优化的AST，并在树的每个节点中包含生成中间代码(在本例中为LLVM IR)所需的所有必要信息。对树的遍历可能会大大改变其结构，例如，通过操作符优先级解析将操作符和操作数列表更改为有序操作的层次结构。注意，传递可能使结构的某些部分完全不变。
所以，我的问题是我如何最好地(读:最容易，尽可能少的重复)表示一个在c++中有多个中间表示的AST ?我希望来自AST的每个阶段版本的节点类型在编译时尊重它们的不兼容性。我认为关键的问题是，我应该如何表示结构的部分，在传递之间不改变，同时避免重复的代码?我想这个问题在过去已经被编译器作者解决过很多次了。
请注意，我目前在AST中使用Boost Variant而不是正常的运行时多态性，并希望有一个与之兼容的解决方案。
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，并且相信结果树是形状良好的。这个想法可以推广到图形重写
下面是一个基于类型安全的boost::variant的AST。
我包含了一个简单的"结构保持转换"，它只更改存储在每个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;
};
}
这只是个开始。
您可以更进一步，让每种类型的节点都有一组不同类型的子节点，甚至是不同数量的子节点。只需为每种类型的节点(如data_type)创建特征类，例如children_types。然后使用与我如何定义Var类似的技术来定义您的孩子的类型。基本上，您通过MapTypes的链得到std::vector< AST_Node<ChildType<type_list_element>>>的variant。你可以把std::vector和data捆绑成一个变体。
这将允许您为单个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树本身。我们可以使用struct s来命名AST的阶段，并将阶段的进程定义为在astFunc<before_phase, before_types, after_phase, after_types>的签名中应用和强制的类型到类型函子。
所以这还不错。我们创建节点类型的type_list。这些类型不一定是实际存储的数据。但它可以。
我们创建一个data_type traits类，将每个节点类型映射到存储的数据。我们创建一个child_types traits类，将每个节点类型映射到子ast的type_list。
每个AST_Node存储一个variant<AST_Concrete_Node<Ts>...>。AST_Concrete_Node包含一个DataType<T> data;和一个MapTypes< std::vector, MapTypes< AST_Node, ChildTypes<T> > > children;(也就是std::vector< AST_Node<ChildrenTypes...> >，但你不能直接说出来)。
接下来，AST_Concrete_Node<T>转换函数在一个复杂的模板元编程中被连接到boost变量访问器中。这一步很棘手，但我认为是可行的。额外的工作是为了跳过未提及的类型，所以我们不必经常说"哦，我们不想转换节点X"，而是必须说"如果我们点击节点Y，不要转换它的子节点"。
int，第二个是Bob，第三个是double"，如果我们走得足够远的话。