C++中抽象语法树最常用的表示法是什么

Question

我想为简单类型的lambda演算构造一个简单的解析器/类型检查器/计算器。我已经在Rust中实现了这样的功能，但作为C++的新手，我不确定在中表示AST的最佳方式是什么。例如，在Rust，我可以定义一个递归求和类型。然后我可以使用模式匹配或访问者模式来访问子组。

enum Term {
// de Bruijn index
Var(usize),
// Lambda abstraction x: T. t
Abs(Box<Term>, Box<Term>),
// Application t1 t2
App(Box<Term>, Box<Term>),
}
fn ex(term: &mut Term) {
match term {
Term::Var(idx) => {
},
Term::Abs(ty, tm) => {
ex(tm.as_mut());
},
Term::App(t1, t2) => {
// do something
}
}
}

如果没有sum类型，在C++中似乎有两种主要的方法来表示类似的东西：枚举/并集对(我将在C中使用(，或者具有访问者模式的类层次结构(完整实现未显示(

class Expr {
public:
virtual void visit(Visitor &v) const = 0;
virtual ~Expr() {}
};
class Var : public Expr {
public:
Var(int idx) : debruijn{idx} {}
private:
int debruijn;
};
class App : public Expr {
public:
App(std::unique_ptr<Expr> t1, std::unique_ptr<Expr> t2)
: e1{std::move(t1)}, e2{std::move(t2)} {}
private:
std::unique_ptr<Expr> e1;
std::unique_ptr<Expr> e2;
};
class Abs : public Expr {
public:
Abs(Type ty, std::unique_ptr<Expr> e) : e{std::move(e)}, ty{ty} {}
private:
Type ty;
std::unique_ptr<Expr> e;
};

这是最好的方法吗？我想从用最现代、最地道的风格编写代码开始我的C++学习。

Answer 1

从C++17开始，C++确实有求和类型——在标准库中有点像：std::variant。

您可以使用std::visit和overloaded破解来匹配正确的case类。现在，将其用于AST应该相当习惯。

此外，您可能希望使用std::optional<T>而不是std::unique_ptr<T>。

---

。。。或者，你可以看看生成解析器的BoostSpiritX3库，看看那里到底发生了什么。这是一个C++14库。