抽象语法树的生命周期
你已抵达计算机编程的涅槃境界。在经历多种编程范式后，最终明悟：所有问题都可以通过再写一个编译器来解决。就连即将统治人类的人工智能，本质上也不过是编译器——正如预言所述。
既然每个程序都应包含编译器，那么如何编写编译器？本文将聚焦抽象语法树(AST)的设计实践。作为曾将LLVM字节码反编译为Clang AST的开发者，我将分享教科书不会教授的实战经验：AST的API设计、内存布局等"语用学"考量。
什么是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;
}
|
这种设计清晰简单，依赖GC自动管理内存。但在C++中，我们需要更精细地控制节点所有权。
朴素方案
1
2
3
4
|
struct BinExpr : Expr {
std::shared_ptr<Expr> lhs;
std::shared_ptr<Expr> rhs;
};
|
使用shared_ptr通过引用计数模拟GC行为。但循环引用会导致内存泄漏（虽然树结构本身无环）。
“倒金字塔"方案
1
2
3
4
|
struct BinExpr : Expr {
std::unique_ptr<Expr> lhs;
std::unique_ptr<Expr> rhs;
};
|
改用unique_ptr消除引用计数开销，通过所有权链确保析构顺序。Rust中的等效实现：
1
2
3
4
|
enum Expr {
IntConstant(i32),
BinExpr(Box<Expr>, Box<Expr>)
}
|
进阶优化技巧
不可变API设计
1
2
3
4
5
6
7
8
|
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; }
};
|
集中存储方案
将节点所有权转移给ASTContext：
1
2
3
|
vector<unique_ptr<Expr>> node_storage;
auto &binexp = node_storage.emplace_back(
make_unique<BinExpr>(*lhs, *rhs));
|
变体模式
使用std::variant替代继承：
1
2
3
4
5
|
using Expr = std::variant<IntConstant, BinExpr>;
struct BinExpr {
Expr &lhs;
Expr &rhs;
};
|
连续内存布局
1
2
3
|
std::vector<Expr> node_storage;
node_storage.reserve(max_num_nodes); // 关键！
auto &binexp = node_storage.emplace_back(BinExpr{lhs, rhs});
|
注意：必须预分配内存防止地址失效。替代方案包括：
- std::deque（非完全连续但安全）
- 使用索引替代指针（增加间接层）
结语
编译器设计远不止于语法分析，每个抽象概念都需要具体的实现决策。记住两条准则：
- 过早优化是万恶之源
- 永远先进行性能分析
有趣的是，本文讨论的多数技术难以在托管语言中实现。这是否意味着这些语言的编译器（如Roslyn）存在性能损失？欢迎分享你的编译器开发实战经验！