抽象语法树：它们实际上随处可见——但它们是什么？

VS Code会将过时的代码行灰显，这难道不奇妙吗？哎呀，我的 return 语句在第 3 行。第 4 行根本运行不了……但我还没调用这个函数呢。那么，当代码最终运行时，VS Code 究竟是如何知道哪些代码行将来不会用到的呢？

如果我们有一个条件语句，VS Code 会准确评估我们击中其外部代码的可能性：

bool最终结果可能为 false。但如果我们将条件改为trueVS Code 知道我们将始终运行该代码块，并且（如果代码块中不可避免地包含 return 语句）永远不会到达最后一行：

VS Code 几乎可以理解代码的语义。但实际上，VS Code 是使用代码来实现这一点的！具体怎么做到的？

输入：抽象语法树（AST）

AST 是一种数据结构，它对一段代码的抽象信息进行编码。

这是专门针对上面的示例代码声明的function foo(bool)。

AST 是一种“树”，它是一种图。图是一种非常有用的数据结构，在软件工程中无处不在。为了理解 AST，我们必须理解图。（您也可以跳过本节，直接学习更多关于AST 的知识，或者参考这些工具来自己制作和使用 AST。）

图表如何工作？

图由“节点”和“边”组成，可以用（通常是嵌套的）对象或数组表示。图也可以混合使用对象和数组，将一种对象嵌套在另一种对象中，达到任意复杂程度。

每个节点和边都可以包含信息。你可以通过它们之间的边从一个节点移动到另一个节点。边也有方向。这是一个连接节点 A 和节点 B 的简单图：

从最基本的层面上讲，如果你用 Javascript 编写这个代码，它可能看起来像这样：

[ ["A", ["B"] ], [ "B", [] ] ]

或者

{ 
   A: { value: data_set1, children: ["B"] }, 
   B: { value: data_set2, children: [] }
}

你可以改变方向

得到如下代码：

[ ["A", [] ], [ "B", ["A"] ] ]

或者这个

{ 
   A: { value: data_set1, children: [] }, 
   B: { value: data_set2, children: ["A"] }
}

您可以将边设为双向的，通常用没有箭头的普通线表示。

使用如下代码

[ ["A", ["B"] ], [ "B", ["A"] ] ]

或者这个

{ 
   A: { value: data_set1, children: ["B"] }, 
   B: { value: data_set2, children: ["A"] }
}

这些都是简单的例子，实际上，图表可以编码大量数据。例如，谷歌借助页面排名图表来显示搜索结果。以下是其中一个图表的简化表示：

图也可以有一些约束。我们可以这样说：“图将以一个节点开始，除第一个节点之外的每个节点都只有一个父节点。不过，每个节点可以有多个子节点。”

这是一类树的示例。通常，树会分叉。第一个节点（根节点）之后的每个节点都只有一个父节点。树是分层的，不包含环路。（图可以包含环路，但不一定包含根节点。）

但现在我们先来关注一下树。因为当我们构建 AST 时，我们会从代码中获取抽象的语法数据，并将其编码成树。

AST 设计标准和遍历函数

由于 AST 经常用于代码编译过程（编译过程始终存在——每次尝试运行任何代码时都会发生），因此 AST 设计标准相当健壮。编译器（和解释器）本质上是将我们编写的代码（用 JavaScript、Python、Ruby 或 C++ 编写）转换为计算机 CPU 可以运行的机器语言指令。

AST 设计标准包括：

• 变量（及其在源代码中的声明位置）必须保留
• 语句执行的顺序有明确的定义和保留
• 在二元运算的情况下，左右定位保持不变
• 标识符及其值被存储

最终，有问题的代码无法转化为 AST。在构建 AST 的过程中，我们可能会遇到诸如缺少括号、类型不明确的变量（例如 Typescript 中的变量）或其他语法错误等错误。与其继续进行，不如标记这些错误并将其显示给用户以供纠正。

但是，一旦我们成功构建了 AST，就应该能够使用代码生成器将其反解析为与原始代码非常相似的代码。并且生成的代码的功能应该与原始代码完全相同。

例如，使用像这样的 AST...

我们可以重建如下所示的代码：

function euclid(a,b) {
   while (b !== 0) {
      if (a > b) { a = a - b; } 
      else { b = b - a; }
   } 
   return a;
}

所以，我们可以把一段代码转换成 AST，最终再把它转换回代码。等等……还有更多：我们用来单步执行 AST 的函数（称为 AST 遍历函数）足够智能，能够理解语义编码，并帮助我们利用这些信息做一些有用的事情。

我们可以使用 AST 遍历函数沿着结构走动来发现“死分支”（永远不会运行的代码片段）。

Tree Shaking 及其他

摇树优化 (Tree Shaking) 是指 JavaScript 中的死代码消除。为了进行摇树优化，我们会结合使用 AST 和 AST 遍历函数来查找哪些代码“分支”是“死的”。VS Code 就是这样将未使用的代码行灰显的。摇树优化会消除这些未使用的代码行，从而获得更干净、更精简的代码库。

当代码库足够庞大时，消除死代码是必要的。死角会变成负担，如果产品发布后，臃肿的代码急需修剪，可能会导致性能下降。（有趣的是，这可不是双关语。他们就是这么叫的！不过，我在写这篇文章的时候，看到了很多关于树修剪的文章。）

这对双方都有好处，因为湿代码对于开发人员来说也更加令人困惑。

有趣的是，同样的遍历函数可以根据预设规则帮助我们将自己的代码注入到给定的代码块中。（更多信息请参见下文。）

制作和使用 AST 的工具

创建 AST：Esprima

遍历 AST 并替换或注入代码：Extraverse

将修改后的 AST 解析回 JavaScript：Escodegen

AST 与 CPT

我之前提到过，AST 用于编译或解释过程。其实还有另一种选择：具体解析树 (CPT)。与 AST 不同，CPT 包含更细粒度（可能不必要的）的信息。AST 可以省略一些语法信息，例如分组括号，因为 AST 的结构已经对这些信息进行了编码。

CST 比 AST 大得多。但好处是它们可以提高编译效率。实际上，两者都会用到。

跟进

我对 AST 的迷恋受到我正在开发的一个应用程序的启发：一个 Big O（时间复杂度）计算器。

在我对大 O 近似的研究中，我发现大多数工具都会计算机器在不同大小的数据集上运行某个函数所需的时间。它们使用计算出的时间量来确定时间增长率是亚线性的、线性的、指数的等等。

我希望创建一个工具，可以统计执行的操作数量（而不是特定机器的运行时间），这样我就能在任何代码片段中指出开销最大的行，并指出它们运行了多少次。这可以帮助学生在学习大O算法时，更具体、更深入地了解代码的运行情况。

停机问题

稍微超出了本文的讨论范围，但足够酷，值得一提：1936 年，艾伦·图灵（下图，当时他 16 岁）证明了，不可能编写出能够检查另一段代码及其输入并判断其是否会终止的代码。这被称为停机问题。

因此，输入 Big O 计算器的代码可能会无限循环运行太久，最终导致用户电脑死机。我计划为此内置一个故障保护机制。

我们将拭目以待

我最终想把这个项目扩展成一个更全面的教学工具。目前，我把项目范围限定在计算器上，看看是否可行。