抽象语法树的生命与时代

你已抵达计算机编程的涅槃之境。你的旅程带你走过许多道路，包括相信上帝用LISP编写了宇宙，但现在你心中真理昭然：每个问题都可以通过再写一个编译器来解决。

这是真的。即使我们即将迎来的人工智能霸主也不过是编译器，正如传说所预言。你为革命性DeFi平台编写的智能合约？它终将通过某个编译器。

既然我们已经确定每个程序至少应包含一个编译器（如果还没有的话），让我们谈谈如何编写一个。事实证明，这是一个相当广泛的话题，我不太可能在这篇博客的边距中容纳对此主题的全面论述。相反，我将专注于抽象语法树（AST）的主题。

过去，我曾致力于一个将LLVM位码转换为Clang AST的反编译器，这使我对AST有了自己的见解。这些是学校不教的东西，比如：AST的API应该是什么样子？它应该如何布局在内存中？从头设计一个组件时，我们必须考虑超越其功能之外的方面——我想你可以称这些方面为“语用学”。让我们回顾其中一些，这样如果你将来发现自己需要处理AST，你可以跳过更令人头疼的部分，直接解决更相关的问题！

什么是AST？

就其本身而言，AST并不是编译器中非常有趣的部分。它们主要是为了将我们作为输入接收的可怕字符流转换为更易于后续编译器操作的格式。然而，AST的设计方式在处理编译器时会产生差异。让我们探讨一下。

管理不可管理之物

如果你在使用托管语言如C#或Java，一种带有垃圾收集器和非常OOP类型系统的语言，你的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#或Java。我是一个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++中没有等效物，我的示例也不会工作得那么好。根据我的经验，完全摆脱每个节点持有引用计数的仪式是相当容易的，而是决定采用更有纪律的所有权方法。

“反向金字塔”方法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


struct Expr {
    virtual ~Expr();
};
struct IntConstant : Expr {
    int value;
};
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。
节点不能移动；它们的所有者是固定的。

移除保护措施

下一步是看看如何通过移除我们迄今为止使用的一些保护措施来改进事情，而不会完全搬起石头砸自己的脚。我不会提供如何在Rust中实现这些方法的片段，因为上次我在公司Slack频道中询问如何做到这一点时，我收到的回复是“不要”和“你为什么要这样做？”以及“有人请叫保安”。这不应该令人惊讶，因为AST基本上是一个带有额外步骤的链表，而Rust讨厌链表。

到目前为止，总体思路是节点拥有其他节点。这使得安全处理AST变得相当容易，因为节点是自包含的。

如果我们决定将节点的所有权转移给某个其他实体呢？毕竟，拥有某种ASTContext对象是相当合理的，我们可以假设它处理节点的生命周期，类似于Clang中发生的情况。

让我们首先改变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现在是所有节点的所有者，我们可以迭代它们而无需进行树访问。事实上，去看看关于Carbon编译器设计的这个演讲，大约37分钟处：如果你保持创建节点的模式可预测，你最终会得到一个已经按，例如，后访问顺序排序的存储容器！

主题变奏

现在让我们从Rust的书中借用一个技巧：我迄今为止一直在使用的Expr类是通过继承实现多态性的老派案例。虽然我确实相信继承有其地位，并且在许多情况下应该是首选解决方案，但我确实认为AST是区分联合（discriminated unions）是正确选择的地方之一。

Rust将区分联合称为enum，而C++17称它们为std::variant。虽然实质相同，但人体工程学不同：Rust在其语法中对它们有一流支持，而C++让用户进行模板元编程技巧来使用它们，即使他们不一定意识到这一点。

我选择variant而不是继承最感兴趣的一个特性是它将我们的AST对象变成“值类型”，允许我们直接存储Expr对象，而不必通过引用或指针进行间接访问。这在一会儿会很重要。

这种模型解锁的另一个特性是我们免费获得了访问者模式的实现，并且我们可以弄清楚某个值持有哪种节点，而不必发明我们自己的动态类型转换系统。看看你，LLVM。还有Clang。还有MLIR。

偏离轨道

让我们回顾一下我之前做的一个例子：

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

有一件事让我困扰：双重间接和非连续内存分配。想想这种存储机制的内存布局是什么样的：向量将有一块连续的内存块用于存储指向所有节点的指针，然后每个指针将有一个关联的内存块，其大小为一个节点，如前所述，每个节点种类不同。

这意味着我们的节点，即使顺序分配，也有可能最终散落在各处。他们说早期优化是万恶之源，但为了耗尽我袖中的所有技巧，我将继续展示一种避免这种情况的方法。

让我们开始做我之前说我会做的事情，并对我们的节点使用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;
};

既然每个节点都具有相同的大小，我们终于可以将它们连续存储在内存中：

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中榨取最后一滴性能和内存效率，你可能愿意用其中一些来换取一些易用性。我可以想到三种实现这一点的方法：

使用std::list。
使用std::deque。
使用索引而不是原始指针。

让我们一次一个地浏览这些选项。

使用std::list而不是std::vector

不要。说得够多了。

好吧，好吧。我会详细说明。

链表在RAM的“随机访问”部分还不是谎言且内存访问模式无关紧要的时代是好的。使用链表存储节点只是撤销了我们为优化布局所做的所有努力。

使用std::deque而不是std::vector

这种方法已经更好了！由于我们大多只是将节点附加到节点存储容器的末尾，并且由于双端队列保证这样做是可能的而不使任何现有内容的地址无效，这看起来是一个非常

抽象语法树（AST）的设计与内存管理：从托管语言到C++的实战解析

本文深入探讨抽象语法树（AST）在编译器中的设计与实现，对比托管语言与C++的不同内存管理策略，涵盖shared_ptr、unique_ptr、std::variant等技术的应用与优化，并讨论性能与安全性的权衡。