【算法】搞懂抽象语法树（AST）

说明：文中的AST的JSON结构的字段都是用 esprima 的格式，不同的解析器所生成的结构会有所不同，但是概念是一致的。
文章中出现 AST （Abstract Syntax Tree） 就是表示抽象语法树的简写

什么是AST

抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构 — 摘自维基百科

当写下一段代码的时候，其实写的就是一段字符串，如何让机器能够理解代码的逻辑，比如下面这段JS代码：

const x = 1 + 2

每一种编程语言都有其独特的语法规则，而写下的代码是一个个的字符，为了让机器读懂书写的代码，需要一个个字符的去读取，第一步就是把其中的所有关键词提取出来，并且判断这些关键词属于什么类型，关系结构是怎么样。比如 const 是保留关键词，+和= 号是操作符等等，并且把不同字段间的关系也表达出来，比如 1 + 2 是要赋值给x的等等。上述代码的 抽象语法树如下：

// 采用 esprima 生成
{
  "type": "Program",
  "body": [
    {
      "type": "VariableDeclaration",
      "declarations": [
        {
          "type": "VariableDeclarator",
          "id": { "type": "Identifier", "name": "x" },
          "init": {
            "type": "BinaryExpression",
            "operator": "+",
            "left": { "type": "Literal", "value": 1, "raw": "1" },
            "right": { "type": "Literal", "value": 2, "raw": "2" }
          }
        }
      ],
      "kind": "const"
    }
  ],
  "sourceType": "script"
}

这是用JSON的格式来表现了，不同的解析器其字段名可能有些不同，但是其本质是一样的。

如何生成AST

生成AST的第一步就是读取字符串，然后识别出一个个的token，比如下面这个JS的代码片段，需要识别出 const,a,=,19,1,2,-,a,/,10 这些标识(token)，这些标识是有分类的，比如 const 是保留关键词，a、b是变量，=、*、-、/ 这些的操作符。

const a = 10
const b = sum(1 * 2 - a / 10, 10)

然后根据语言的语法规则来排列、分类这些token，从而形成一种树状结构（AST）。

Shunting-Yard算法

了解这个算法前，先来复习一些概念，下面摘录自wikipedia:

中缀表示法（Infix notation，或中缀记法）是一个通用的算术或逻辑公式表示方法， 操作符是以中缀形式处于操作数的中间。例：1 * 2 - 10 / 10 波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。 逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。例：1 2 * 10 10 / -

Shunting-Yard算法就是把中缀表示法转换为逆波兰表示法。也就是把 1 * 2 - a / 10 转换为 1 2 * 10 10 / - 的形式。这种形式非常易于计算机处理

为什么要使用逆波兰表示法？这种表示方法非常易于计算机处理，具体的解释不是本文的重点，可以看这里：https://zh.wikipedia.org/wiki/逆波兰表示法

这和抽象语法树有什么关系？把几种表示方式放在一起比较一下

逆波兰表示法： 1 2 * 10 10 / -

把 1 * 2 - 10 / 10转换为下面的树形表示法，
      -
  *        /
1   2   10   10

再把上述的结构转换为，JSON数据结构表示：
{
  "type": "Program",
  "body": [
    {
      "type": "ExpressionStatement",
      "expression": {
        "type": "BinaryExpression",
        "operator": "-",
        "left": {
          "type": "BinaryExpression",
          "operator": "*",
          "left": { "type": "Literal", "value": 1, "raw": "1" },
          "right": { "type": "Literal", "value": 2, "raw": "2" }
        },
        "right": {
          "type": "BinaryExpression",
          "operator": "/",
          "left": { "type": "Identifier", "name": "a" },
          "right": { "type": "Literal", "value": 10, "raw": "10" }
        }
      }
    }
  ],
  "sourceType": "script"
}

当把几种方式放在一起比较的时候，发现其实是一致的，AST的数据结构只是给每一个token添加更多的属性，以实现更加复杂的语法，其本质没有变化。

算法实现原理

直接用一个例子来看看算法的实现吧：

// 这里操作符的优先级，默认为从小学的数学的操作符的优先级，没有什么特殊哦
1 * 2 + (10 - 2) * 5

转换为 RPN 和 AST 的过程

转换为AST的过程和上述非常相似，最终的结果 1 2 * 10 2 - 5 * +
如果把这个放入一个堆栈，然后再一个个出栈就可以构建AST树了，来试试看：

最后生成如下AST：

• Addition +
  • Multiply *
    • Number 1
    • Number 2
  • Multiply *
    • Minus -
      • Number 10
      • Number 2

这个例子中，只有数字和操作符，如果加入变量，那么过程也是一样的，只是类型不同罢了。

AST的一些应用场景

AST的应用场景是非常广泛的，在写代码的过程中，在不知觉中就用到了，代码可以转换为AST，AST也可以转换为代码。下面是一些应用场景的例子：

• IDE
  • 代码高亮，纠错等功能都是基于AST的
• 代码转译
  • 经常使用babel，通过分析AST，把新的语法转换为旧的语法实现。
  • 比如像Typescript作为JS的超集，编译到JS的过程需要用到AST
• 代码的一些处理，比如JS的minify
• 通过代码生成文档的实现
• 代码静态扫描

解析器

下面列举一些 js、ts的解析器的实现库

其中像babel, typescript是比较常见，babel是转译工具，ts是一门新的语言。

Babel

babel是一个编译器，可以把新的js语法编译为老的语法实现。现在基本上为了提高生产力，babel必然是所用的构建工具中的一环。所以很有必要了解，简单从AST的角度介绍下。

babel主要三步走来完成编译的过程

1. 读入JS源代码，转换成AST
2. 遍历AST所有节点，运行插件，执行转换任务，比如把变量 a 重命名为 x，这个过程生成了一个新的转换过的AST
3. 把新的AST生成新的JS代码

这三个过程分别对应了三个包：@babel/parser, @babel/traverse, @babel/generator

当时通常不需要主动调用这些包的方法来自己手动做，只要通过一定的规范格式，写插件即可。

下面是一个简单的直接使用的例子：

const parser = require("@babel/parser");
const traverse = require("@babel/traverse").default;
const generate = require("@babel/generator").default;
const sampleCode = `
function add(a, b) {
  return a + b
}
`;
// 1.解析为AST
const ast = parser.parse(sampleCode);
// 2.遍历，并做转换
traverse(ast, {
  FunctionDeclaration: function(path) {
    path.node.id.name = 'addTwo'
  }
});
// 3.重新生成新的代码
const result = generate(ast)
console.log(result.code)
// 打印的结果是
// function addTwo(a, b) {
//    return a + b
// }

这是一个非常基本的例子，但是涵盖了babel整个工作的基本打框架，可以看到AST在其中的关键作用。

总结

从AST的概念，然后AST如何生成，最后写到AST使用的一些场景。

虽然在平时工作中，尤其在业务开发中很少用到，但是当想要对一些编程工具、编译工具、写一些babel或者webpack的插件，去构建一些提效工具的时候，就需要涉及AST的概念，所以去理解，去了解是很有必要的。