抽象语法树的生命周期 - Trail of Bits博客
什么是AST？
抽象语法树（AST）本身并非编译器中最有趣的部分，其主要作用是将输入的字符流转换为更适合编译器后续处理的格式。然而AST的设计方式会对编译器开发产生重要影响。
管理不可管理的内存
在C#或Java等托管语言中，AST节点通常采用继承体系实现：
1
2
3
4
5
6
7
8
|
class Expr {}
class IntConstant : Expr {
int value;
}
class BinExpr : Expr {
public Expr lhs;
public Expr rhs;
}
|
这种设计清晰有效，由于运行时管理所有内存，节点所有权并不重要。
原生实现方法
简单方法
在C++中，可以使用shared_ptr模拟托管语言的行为：
1
2
3
4
5
6
7
8
9
10
|
struct Expr {
virtual ~Expr();
};
struct IntConstant : Expr {
int value;
};
struct BinExpr : Expr {
std::shared_ptr<Expr> lhs;
std::shared_ptr<Expr> rhs;
};
|
这种方法通过引用计数保证节点有效性，但会带来原子操作的开销。
“反向金字塔"方法
使用unique_ptr可以避免引用计数开销：
1
2
3
4
|
struct BinExpr : Expr {
std::unique_ptr<Expr> lhs;
std::unique_ptr<Expr> rhs;
};
|
这种方法保证子节点完全由父节点拥有，销毁根节点时会自动销毁所有子节点。
改进API设计
通过使数据结构不可变性来改进设计：
1
2
3
4
5
6
7
8
9
|
class BinExpr : Expr {
std::unique_ptr<Expr> lhs, rhs;
public:
BinExpr(std::unique_ptr<Expr> lhs, std::unique_ptr<Expr> rhs)
: lhs(std::move(lhs))
, rhs(std::move(rhs)) {}
const Expr& get_lhs() const { return *lhs; }
const Expr& get_rhs() const { return *rhs; }
};
|
这明确了节点的三个特性：不可变性、非空性和固定所有权。
移除安全措施
可以将节点所有权转移到专门的AST上下文对象：
1
2
3
4
5
6
7
8
9
|
struct BinExpr : Expr {
const Expr& lhs;
const Expr& rhs;
};
vector<unique_ptr<Expr>> node_storage;
auto &lhs = node_storage.emplace_back(make_unique<IntConstant>(...));
auto &rhs = node_storage.emplace_back(make_unique<IntConstant>(...));
auto &binexp = node_storage.emplace_back(make_unique<BinExpr>(*lhs, *rhs));
|
变体模式
使用std::variant替代继承体系：
1
2
3
4
5
6
7
8
9
10
11
|
struct IntConstant;
struct BinExpr;
using Expr = std::variant<IntConstant, BinExpr>;
struct IntConstant {
int value;
};
struct BinExpr {
Expr &lhs;
Expr &rhs;
};
|
这种方法将AST对象变为"值类型”，并免费获得访问者模式实现。
内存布局优化
为了确保内存连续性并避免重分配：
1
2
3
4
5
|
std::vector<Expr> node_storage;
node_storage.reserve(max_num_nodes);
auto &lhs = node_storage.emplace_back(IntConstant{3});
auto &rhs = node_storage.emplace_back(IntConstant{4});
auto &binexp = node_storage.emplace_back(BinExpr{lhs, rhs});
|
reserve调用在此至关重要，它确保内存不会重新分配。
替代方案评估
- std::list: 不推荐使用，会破坏内存局部性
- std::deque: 较好的折衷方案，但不完全连续
- 使用索引代替指针: 增加间接层但提供更多灵活性
总结思考
编译器设计涉及大量超越解析本身的决策。需要记住两个重要原则：过早优化是万恶之源，以及一定要对代码进行分析——在决定优化AST存储之前，代码库中可能已有更容易优化的部分。
有趣的是，本文展示的大多数技术在托管语言中不易实现。这是否意味着这些语言的编译器（如Roslyn）牺牲了性能？如果确实如此，这种性能牺牲的意义又是什么？