抽象语法树（AST）的设计与内存管理实战

本文深入探讨抽象语法树在编译器设计中的内存管理策略，对比托管语言与C++/Rust的实现差异，分析节点所有权、API设计和性能优化技巧，为编译器开发者提供实用指导。

抽象语法树的生命周期 - Trail of Bits博客

你已抵达计算机编程的涅槃境界。在经历诸多探索路径（包括曾相信上帝用LISP编写宇宙）后，此刻你心中真理昭然：所有问题都能通过再写一个编译器来解决。

没错。就连即将统治我们的人工智能霸主也不过是编译器——正如预言所示。那个为你革命性DeFi平台编写的智能合约？它终将在某个时刻经过编译器的处理。

既然我们已确立"所有程序都应至少包含一个编译器"的原则，现在来探讨如何编写编译器。这个话题极为庞大，本文难以全面阐述，因此我将聚焦于**抽象语法树（AST）**的设计实践。

我曾参与将LLVM位码反编译为Clang AST的项目，这使我对AST形成了独特见解。这些是学校不会教你的实战经验：AST的API应如何设计？内存布局该如何规划？从零设计组件时，我们必须考虑超越纯功能性的"语用学"层面。下面让我们探讨这些内容，助你未来处理AST时跳过令人抓狂的细节，直接解决核心问题！

什么是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++开发编译器。作为C++守旧派，我喜欢随时保持"备枪上膛"的状态：没有垃圾回收器帮忙清理现场，我必须深思每个节点的所有权归属。

朴素实现方式 

 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;
};

C++的共享指针使用引用计数（可视为自动垃圾回收的一种形式），最终效果类似Java/C#：每个节点至少会存活到最后一个持有其引用的对象消亡。这里的"至少"很关键：若处理的是抽象语法图而非树，可能出现节点循环引用而无法释放的情况。虽然树结构本身是无环的，但这一点仍需注意。

Rust中的近似实现：

1
2
3
4

enum Expr {
    IntConstant(i32),
    BinExpr(Arc<Expr>, Arc<Expr>)
}

使用此表示法时，编译器通常持有根节点的引用以维持整个节点金字塔。一旦该引用消失，所有节点随之释放。

但每个指针都因原子引用计数而带来额外计算和内存开销。虽然Rust中可使用Rc替代Arc避免原子操作，但C++无等效方案。实践中，完全可以摒弃引用计数，采用更规范的所有权管理策略。

“倒金字塔” approach 

1
2
3
4

struct BinExpr : Expr {
    std::unique_ptr<Expr> lhs;
    std::unique_ptr<Expr> rhs;
};

使用唯一指针可在无需引用计数的情况下自动管理内存。虽然多个节点不能同时拥有同一节点的所有权，但仍可通过解引用存储普通引用来表达循环数据结构（大致等效于std::weak_ptr的用法）。

与朴素方式相同，销毁AST根节点将连带销毁所有子节点。但此处我们获得确定性保证：因为每个子节点均被其父节点唯一拥有。

Rust等效实现：

1
2
3
4

enum Expr {
    IntConstant(i32),
    BinExpr(Box<Expr>, Box<Expr>)
}

插曲：改进API

我们已接近理想表示法，但我偏好尽可能使数据结构不可变。实际代码库中的BinExpr实现：

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; }
};

这传递了几个重要信息：

  • 节点不可变
  • 节点不可为null
  • 节点不可移动（所有者固定）

解除安全防护

下一步是在不"搬石砸脚"的前提下，通过解除某些安全防护来提升性能。由于AST本质上是加强版链表，而Rust厌恶链表，此处不提供Rust实现示例。

此前的核心思想是节点拥有其他节点，这种自包含特性使AST处理变得安全。但若将节点所有权转移给其他实体呢？像Clang那样使用ASTContext对象管理节点生命周期是完全合理的方案。

首先修改Expr节点定义：

1
2
3
4

struct BinExpr : Expr {
    const Expr& lhs;
    const Expr& rhs;
};

然后创建节点存储池：

1
2
3
4

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));

现在node_storage拥有所有节点，无需遍历树即可迭代访问。如果你保持节点创建模式的可预测性，存储容器可能已按后序遍历等顺序排列！

变体模式

现在借鉴Rust的技巧：此前使用的Expr类是通过继承实现多态的经典案例。虽然继承有其适用场景，但我认为AST是使用 discriminated unions（可辨识联合）的理想场合。

Rust称其为enum，C++17称其为std::variant。本质相同但体验迥异：Rust提供语法级原生支持，而C++需要用户进行模板元编程技巧（即使他们未必意识到）。

选用variant而非继承的主要原因在于它将AST对象变为"值类型"，允许直接存储Expr对象而非通过指针间接引用。这点稍后会显得重要。

此模式还免费提供了访问者模式实现，无需自行发明动态类型转换系统就能确定值所持有的节点类型（看看LLVM、Clang和MLIR吧）。

突破常规

回顾之前的示例：

1
2

vector<unique_ptr<Expr>> node_storage;
// ... 节点创建代码

有两点令人不安：双重间接引用和非连续内存分配。这种存储机制的内存布局是：vector有连续内存块存储节点指针，每个指针又指向大小不等的节点内存块。

这意味着即使顺序分配，节点也可能分散在内存各处。虽然过早优化是万恶之源，但为展示所有技术手段，我将演示如何避免这种情况。

首先实践前言，对节点使用variant：

1
2
3
4
5
6

struct IntConstant;
struct BinExpr;
using Expr = std::variant<IntConstant, BinExpr>;

struct IntConstant { int value; };
struct BinExpr { Expr &lhs; Expr &rhs; };

现在所有节点大小相同，可以连续存储在内存中：

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});

这里的node_storage.reserve调用不是优化——而是此机制的绝对核心支撑。

我必须明确强调：这正是C++招致批评的那种操作。这好比将上膛的枪对准你的脚，稍有不慎就会炸断你的腿。

使用reserve是为了确保所有可能用于存储节点的内存都预先分配，这样当使用emplace_back添加节点时，能保证内存块不会重新分配地址（否则包含引用的节点将指向垃圾数据，恶魔会从你的鼻孔飞出）。

当然，vector和reserve并非唯一方案：如果最大节点数在编译期已知，使用std::array也是有效的。

关于max_num_nodes的计算：没有标准答案，但可找到合理的启发式方法。例如解析C语言时，最小语句可能是a;或甚至单独一个a。为绝对安全，可分配与源代码字符数相等的节点数。虽然大多数程序不会出现这种极端情况，但这意味着大部分内存将被浪费。遗憾的是，无法通过简单的shrink_to_fit回收浪费的内存，因为这可能引发重新分配。

此时可用的技术（或在必须分配额外内存时）是对AST进行深克隆：遍历每个节点并在新容器中创建对应新节点。

以此方式存储AST节点时，需注意每个节点的大小现在等于可表示的最大节点的大小。虽然这应该不太重要（毕竟你应尽力保持所有节点尽可能小），但仍值得考虑。

当然，你可能不需要榨干AST的最后一点性能和内存效率，愿意用部分效率换取易用性。我有三种实现方案：

  1. 使用std::list
  2. 使用std::deque
  3. 使用索引替代原始指针

让我们逐一分析。

使用std::list替代std::vector

不要这样做。言尽于此。

好吧，还是详细说明：在"随机存取"还不是谎言、内存访问模式无关紧要的时代，链表是可行的。但使用链表存储节点会抵消我们为优化布局付出的所有努力。

使用std::deque替代std::vector

这种方法更好！由于我们主要向节点存储容器末尾追加节点，而双端队列保证这样做不会使现有内容的地址失效，这看起来是非常好的折衷方案。

遗憾的是内存布局不再完全连续，但你可能不在意这一点。如果你使用微软的STL，还会面临更严重的问题。

使用索引替代原始指针

其理念是存储子节点在vector中的索引而非指针。这重新引入了一层间接引用，且你现在还需确定：该索引引用哪个vector？在每个节点中存储vector引用？这有点浪费。全局存储？依我看这有点令人不适。

结语

我已阐述众多内容，却仅触及编译器编写者必须做出的决策的皮毛。我讨论了如何内存中存储AST，却未谈及应在AST中存储什么内容。

这篇精彩概述的核心主题是：编译器远不止解析而已，所有构建编译器所需的抽象概念都需要具体化，而实现方式的具体细节至关重要。我还必须提及进行此类操作时应牢记的两条格言： premature optimization is the root of all evil（过早优化是万恶之源），以及 always profile your code（始终分析你的代码）——在决定微调AST存储之前，代码库中很可能存在更容易优化的部分。

有趣的是，本文展示的大多数技术在托管语言中难以实现。这是否意味着这些都不重要？抑或用这些语言编写的编译器（如Roslyn）牺牲了性能？如果如此，这种性能损失的意义何在？

最后，我希望本文能引发关于编译器及类编译器工具内部机制的讨论：这些通常高度复杂的软件表面之下隐藏着什么？关于编译的通用材料（词法分析、解析、寄存器分配）容易找到，但关于人们编写需要快速高效处理大型代码库的程序时产生的巧妙想法却较少见。如果有人有实战故事分享，我洗耳恭听！

如果你喜欢这篇文章，请分享至： Twitter | LinkedIn | GitHub | Mastodon | Hacker News

本文内容基于Trail of Bits博客2024年5月2日发布的技术文章，作者Francesco Bertolaccini，专注于编译器研究与实战经验。

comments powered by Disqus
© 2020 - 2025 qife
使用 Hugo 构建
主题 Stack 由 Jimmy 设计
本站总访问量次 本站访客数人次