从0到1，构建抽象代码树

1.前言

参考 babel 工具链对 JavaScript 代码的静态分析过程，笔者实现了一套简易的抽象语法树构造过程，由于抽象语法树相关的中文文档较少，故有此文以此记录。

2.关键词：抽象语法树

抽象语法树（Abstract Syntax Tree，以下简称 AST）是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的，是因为这里的语法并不会表示出真实语法中出现的每个细节。比如，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现。以上是搜索引擎也能给到的介绍，下面就讲讲文档较少覆盖的 AST 生成过程和一种特定的AST使用方式。

3.AST生成过程

3.1 词法分析：生成 token 对象数组。

词法分析将读取字符串形式的代码，将代码按照规则解析、生成由一个个 token 组成的 tokens 数组（令牌流），同时，它会移除空白、注释等。在代码中拆解出 token 对象的常用步骤如下：

1.确定 token 类型，如数字、字符串、关键词、变量等
2.确定 token 的匹配方法：tokenizer 函数。函数读取代码时，按照代码字符串中字符的下标递增进行迭代，递归执行 tokenizer 函数，根据 token 类型，函数以对应的正则表达式、强等于等方式匹配字符。
3.生成 token 对象：token 对象的属性常包括 token 的类型和代码内容。根据实际需要，token 对象也可以携带自身在编辑器中的坐标等辅助信息。
复制代码

一段自定义语法规则的代码“if A 5 then B 8”转化而成的 tokens 令牌流如下。

let tokens = [
  {
    token: "if",
    type: "Identifier",
  },
  {
    token: "A",
    type: "identifier",
  },
  {
    token: "5",
    type: "number",
  },
  {
    token: "then",
    type: "identifier",
  },
  {
    token: "B",
    type: "identifier",
  },
  {
    token: "8",
    type: "number",
  },
];
复制代码

3.2 语法分析：生成 AST

语法分析将每个 token 对象按照一定形式解析，形成树形结构，树的每一层结构称为节点，节点们共同作用于程序代码的静态分析，同时验证语法，抛出语法错误信息。

3.2.1 节点构造

语义本身就代表了一个值的节点是字面量节点，在树形结构担任“叶子”角色。由于每一个被解析出的 token 都携带 type（类型）属性，我们很容易通过type属性匹配得到对应的字面量节点，如：type属性为“number”的 token，其本身的语义就代表了一个 Number 类型值，作为叶子，在树结构中没有其他子节点可被其包含，因此可以由其生成一个字面量节点，为其设置 type 属性为“NumberLiteral”，义为 Number 类型字面量。字符串、布尔类型值、正则表达式等亦然。详细的节点命名可参照 AST 对象文档。

Number 类型字面量节点的生成函数如下。

if (curToken.type === 'number') {
    // 数字或字符串，说明此处是个常量表达式
    const literal = {
      type: 'NumberLiteral',
      value: eval(curToken.value),
    };
    // 将current指向下一个token对象
    nextToken(); 
    return literal;
 }
复制代码

AST 利用“枝干”节点可以将多个节点组合成为更庞大的语法枝干，它们将单个或多个叶子节点、枝干节点组合成为复杂的程序语法。if 语句节点、块状域节点、函数表达式节点等，都可以看做语法树的枝干节点，下面举个例子。
if 语句节点常带有三个属性：test、consequent、alternate。
1.test 属性表示一个条件表达式节点。
2.consequent 属性表示条件为 true 时的执行语句，通常是一个块状域节点。
3.alternate 属性表示 else 后跟随的语句节点，通常是一个块状域节点或 null，也可能是新的 if 语句节点，这种情况下的语法结构形似：if(a){ … }else if(b){ … }

if 语句树形节点的生成函数如下：

 if (curToken.type === 'identifier' && curToken.value === 'if') {
   // 解析 if 语句
   const statement = {
     type: 'IfStatement',
   };
   // if 后面必须紧跟着 (
   nextToken();
   if (curToken.type !== 'parens' || curToken.value !== '(') {
     throw new Error('Expected ( after if');
 
   // 后续的一个表达式是 if 的判断条件
   statement.test = nextExpre
   // 判断条件之后必须是 )
   nextToken();
   if (curToken.type !== 'parens' || curToken.value !== ')') {
     throw new Error('Expected ) after if test expression');
 
   // 下一个语句是 if 成立时执行的语句
   statement.consequent = nextStat
   // 如果下一个符号是 else 就说明还存在 if 不成立时的逻辑
   if (curToken === 'identifier' && curToken.value === 'else') {
     statement.alternative = nextStatement();
   } else {
     statement.alternative = null;
   }
   return statement;
 }
复制代码

3.2.2 简单示例

当我们以3.2.1小节的方法解构、定义出更多枝干节点的内部结构后，就能根据这些节点的结构限制来进行 AST 的构造。参照if语句的内部结构为每个 token 所对应的节点类型定义其树形结构，根据这些节点的结构限制，设计出可递归的 AST 构造函数，使函数实现递归形式的执行流程。执行这样的函数，逐步生成枝干结构，直至完整的树形结构构造完成。一段简单javaScript代码的AST生成示例如下：

1.javaScript 代码:

                            if ( 1 > 0 ) { alert( 'aa' ) }
复制代码

2.生成 tokens 令牌流

[
  {type: "identifier", value: "if"},
  {type: "parens", value: "("},
  {type: "number", value: "1"},
  {type: "operator", value: ">"},
  {type: "number", value: "0"},
  {type: "parens", value: ")"},
  {type: "brace", value: "{"},
  {type: "identifier", value: "alert"},
  {type: "parens", value: "("},
  {type: "string", value: "'aa'"},
  {type: "parens", value: ")"},
  {type: "brace", value: "}"},
]
复制代码

3.生成 AST

{
  "type": "Program",
  "body": [
    {
      "type": "IfStatement",
      "test": {
        "type": "BinaryExpression",
        "left": {
          "type": "Literal",
          "value": 1
        },
        "right": {
          "type": "Literal",
          "value": 0
        }
      },
      "consequent": {
        "type": "BlockStatement",
        "body": [
          {
            "type": "ExpressionStatement",
            "expression": {
              "type": "CallExpression",
              "caller": {
                "type": "Identifier",
                "value": "alert"
              },
              "arguments": [
                {
                  "type": "Literal",
                  "value": "aa"
                }
              ]
            }
          }
        ]
      },
      "alternative": null
    }
  ]
}
复制代码

4.AST的一种应用介绍：Babel工具链

AST 在 Babel 工具链中的作用是将 ECMAScript 2015+ 版本的代码转换为向后兼容的 JavaScript 语法，其历经了生成 AST，再将 AST 转换、生成目标代码的过程。

1.设计 visitor，visitor 是一个对象，visitor 的每个 key 是 AST 的每个节点的类型命名，对象的值是一个函数，这个函数需要描述 AST 的转换过程。
2.设计函数，遍历一个树的所有节点，对节点进行转换，生成转换后的一个新的 AST。遍历至枝干节点一般以递归形式遍历其子节点，叶子节点则直接执行其转换函数。
3.生成目标代码。根据新的 AST 和目标语言的语法规范，设计出每个节点对应的代码生成方式，层层遍历节点，为原始代码赋予新的语法。
复制代码

5.结语

本文主要对AST的生成过程和Babel对AST的一种应用方式进行介绍，在生成过程中小节中描述了AST生成过程中的词法解析和语法解析两个步骤；在AST的应用中介绍了Babel工具链对Javascript语言的语法转换过程。除Babel的应用方式外，我们可以对AST做很多操作，如代码执行、语法报警、自定义打包方案等，在面临此类需求时，AST往往能提供重要的能力，希望本文在届时对您有所帮助。

文章版权归作者所有，未经允许请勿转载。

THE END

前端