AST

什么是AST

抽象语法树（Abstract Syntax Tree，AST）是源代码语法结构的一种抽象表示，它以树状的形式表现编程语言的语法结构。

在代码语法的检查、代码风格的检查、代码的格式化、代码的高亮、代码错误提示、代码自动补全等等场景均有广泛的应用。

通过js编译流程引入AST

一个完整的编译器整体执行过程可以分为三个步骤：

**Parsing(解析过程)**：这个过程要经词法分析、语法分析、构建AST（抽象语法树）一系列操作；
Transformation（转化过程）：这个过程就是将上一步解析后的内容，按照编译器指定的规则进行处理，形成一个新的表现形式；
Code Generation（代码生成）：将上一步处理好的内容转化为新的代码；

解析

词法分析

令牌 Token 是一个不可分割的最小单元（关键字/标识符/操作符）

词法分析也称扫描。调用 next() 方法，一个一个字母的来读取字符，然后与定义好的 JavaScript 关键字做比较，生成对应的令牌流Tokens （数组）。

扫描的过程中，会过滤掉源代码中的注释和空白字符。

n * n;

[
  { type: { ... }, value: "n",  loc: { ... } },
  { type: { ... }, value: "*",  loc: { ... } },
  { type: { ... }, value: "n",  loc: { ... } },
  ...
]

每一个 type 有一组属性来描述该令牌：

{
  type: {
    label: 'name',
    keyword: undefined,
    beforeExpr: false,
    startsExpr: true,
    rightAssociative: false,
    isLoop: false,
    isAssign: false,
    prefix: false,
    postfix: false,
    binop: null,
    updateContext: null
  },
  ...
}

语法分析

语法分析会将词法分析出来的令牌流转化成有语法含义的抽象语法树结构。同时，验证语法，如果有错抛出错误。

抽象语法树

一个 AST 可以由单一的节点或是成百上千个节点构成。

节点拥有相同的结构

// 节点接口
interface Node {
  type: string;
}

字符串形式的 type 字段表示节点的类型（如： “FunctionDeclaration“，”Identifier“，或 “BinaryExpression“）。每一种类型的节点定义了一些附加属性用来进一步描述该节点类型。

{
  type: "FunctionDeclaration",
  id: {...},
  params: [...],
  body: {...}
}
{
  type: "Identifier",
  name: ...
}
{
  type: "BinaryExpression",
  operator: ...,
  left: {...},
  right: {...}
}

一个简单的转换例子

// 源代码
function square(n) {
  return n * n;
}

// 转换
{
  type: "FunctionDeclaration",
  id: {
    type: "Identifier",
    name: "square"
  },
  params: [{
    type: "Identifier",
    name: "n"
  }],
  body: {
    type: "BlockStatement",
    body: [{
      type: "ReturnStatement",
      argument: {
        type: "BinaryExpression",
        operator: "*",
        left: {
          type: "Identifier",
          name: "n"
        },
        right: {
          type: "Identifier",
          name: "n"
        }
      }
    }]
  }
}