AST 抽象语法树

语言: CN / TW / HK

提起 AST 抽象语法树,大家可能并不感冒。但是提到它的使用场景,也许会让你大吃一惊。原来它一直在你左右与你相伴,而你却不知。

一、什么是抽象语法树

在计算机科学中,抽象语法树( abstract syntax tree 或者缩写为 AST ),或者语法树( syntax tree ),是源代码的抽象语法结构的树状表现形式,这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构。

之所以说语法是「抽象」的,是因为这里的语法并不会表示出真实语法中出现的每个细节。

二、使用场景

  • JS 反编译,语法解析
  • Babel 编译 ES6 语法
  • 代码高亮
  • 关键字匹配
  • 作用域判断
  • 代码压缩

三、AST Explorer

我们来看一个 ES6 的解释器,声明如下的代码:

let tips = [
  "Jartto's AST Demo"
];

看看是如何解析的, JSON 格式如下:

{
  "type": "Program",
  "start": 0,
  "end": 38,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 37,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 4,
          "end": 36,
          "id": {
            "type": "Identifier",
            "start": 4,
            "end": 8,
            "name": "tips"
          },
          "init": {
            "type": "ArrayExpression",
            "start": 11,
            "end": 36,
            "elements": [
              {
                "type": "Literal",
                "start": 15,
                "end": 34,
                "value": "Jartto's AST Demo",
                "raw": "\"Jartto's AST Demo\""
              }
            ]
          }
        }
      ],
      "kind": "let"
    }
  ],
  "sourceType": "module"
}

而它的语法树大概如此:

每个结构都看的清清楚楚,这时候我们会发现,这和 Dom 树真的差不了多少。再来看一个例子:

(1+2)*3

AST Tree:

我们删掉括号,看看规则是如何变化的? JSON 格式会一目了然:

{
  "type": "Program",
  "start": 0,
  "end": 6,
  "body": [
    {
      "type": "ExpressionStatement",
      "start": 0,
      "end": 5,
      "expression": {
        "type": "BinaryExpression",
        "start": 0,
        "end": 5,
        "left": {
          "type": "Literal",
          "start": 0,
          "end": 1,
          "value": 1,
          "raw": "1"
        },
        "operator": "+",
        "right": {
          "type": "BinaryExpression",
          "start": 2,
          "end": 5,
          "left": {
            "type": "Literal",
            "start": 2,
            "end": 3,
            "value": 2,
            "raw": "2"
          },
          "operator": "*",
          "right": {
            "type": "Literal",
            "start": 4,
            "end": 5,
            "value": 3,
            "raw": "3"
          }
        }
      }
    }
  ],
  "sourceType": "module"
}

可以看出来, (1+2)*31+2*3 ,语法树是有差别的:

1.在确定类型为 ExpressionStatement 后,它会按照代码执行的先后顺序,将表达式 BinaryExpression 分为 Leftoperatorright 三块;

2.每块标明了类型,起止位置,值等信息;

3.操作符类型;

再来看看我们最常用的箭头函数:

const mytest = (a,b) => {
  return a+b;
}

JSON 格式如下:

{
  "type": "Program",
  "start": 0,
  "end": 42,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 41,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 6,
          "end": 41,
          "id": {
            "type": "Identifier",
            "start": 6,
            "end": 12,
            "name": "mytest"
          },
          "init": {
            "type": "ArrowFunctionExpression",
            "start": 15,
            "end": 41,
            "id": null,
            "expression": false,
            "generator": false,
            "params": [
              {
                "type": "Identifier",
                "start": 16,
                "end": 17,
                "name": "a"
              },
              {
                "type": "Identifier",
                "start": 18,
                "end": 19,
                "name": "b"
              }
            ],
            "body": {
              "type": "BlockStatement",
              "start": 24,
              "end": 41,
              "body": [
                {
                  "type": "ReturnStatement",
                  "start": 28,
                  "end": 39,
                  "argument": {
                    "type": "BinaryExpression",
                    "start": 35,
                    "end": 38,
                    "left": {
                      "type": "Identifier",
                      "start": 35,
                      "end": 36,
                      "name": "a"
                    },
                    "operator": "+",
                    "right": {
                      "type": "Identifier",
                      "start": 37,
                      "end": 38,
                      "name": "b"
                    }
                  }
                }
              ]
            }
          }
        }
      ],
      "kind": "const"
    }
  ],
  "sourceType": "module"
}

AST Tree 结构如下图:

我们注意到了,增加了几个新的字眼:

ArrowFunctionExpression
BlockStatement
ReturnStatement

到这里,其实我们已经慢慢明白了:

抽象语法树其实就是将一类标签转化成通用标识符,从而结构出的一个类似于树形结构的语法树。

四、深入原理

可视化的工具可以让我们迅速有感官认识,那么具体内部是如何实现的呢?

继续使用上文的例子:

Function getAST(){}

JSON 也很简单:

{
  "type": "Program",
  "start": 0,
  "end": 19,
  "body": [
    {
      "type": "FunctionDeclaration",
      "start": 0,
      "end": 19,
      "id": {
        "type": "Identifier",
        "start": 9,
        "end": 15,
        "name": "getAST"
      },
      "expression": false,
      "generator": false,
      "params": [],
      "body": {
        "type": "BlockStatement",
        "start": 17,
        "end": 19,
        "body": []
      }
    }
  ],
  "sourceType": "module"
}

怀着好奇的心态,我们来模拟一下用代码实现:

const esprima = require('esprima'); //解析js的语法的包
const estraverse = require('estraverse'); //遍历树的包
const escodegen = require('escodegen'); //生成新的树的包

let code = `function getAST(){}`;
//解析js的语法
let tree = esprima.parseScript(code);
//遍历树
estraverse.traverse(tree, {
  enter(node) {
    console.log('enter: ' + node.type);
  },
  leave(node) {
    console.log('leave: ' + node.type);
  }
});
//生成新的树
let r = escodegen.generate(tree);
console.log(r);

运行后,输出:

enter: Program
enter: FunctionDeclaration
enter: Identifier
leave: Identifier
enter: BlockStatement
leave: BlockStatement
leave: FunctionDeclaration
leave: Program
function getAST() {
}

我们看到了遍历语法树的过程,这里应该是深度优先遍历。

稍作修改,我们来改变函数的名字 getAST => Jartto

const esprima = require('esprima'); //解析js的语法的包
const estraverse = require('estraverse'); //遍历树的包
const escodegen = require('escodegen'); //生成新的树的包

let code = `function getAST(){}`;
//解析js的语法
let tree = esprima.parseScript(code);
//遍历树
estraverse.traverse(tree, {
enter(node) {
console.log('enter: ' + node.type);
if (node.type === 'Identifier') {
node.name = 'Jartto';
}
}
});
//生成新的树
let r = escodegen.generate(tree);
console.log(r);

运行后,输出:

enter: Program
enter: FunctionDeclaration
enter: Identifier
enter: BlockStatement
function Jartto() {
}

可以看到,在我们的干预下,输出的结果发生了变化,方法名编译后方法名变成了 Jartto

这就是抽象语法树的强大之处,本质上通过编译,我们可以去改变任何输出结果。

补充一点:关于 node 类型,全集大致如下:

(parameter) node: Identifier | SimpleLiteral | RegExpLiteral | Program | FunctionDeclaration | FunctionExpression | ArrowFunctionExpression | SwitchCase | CatchClause | VariableDeclarator | ExpressionStatement | BlockStatement | EmptyStatement | DebuggerStatement | WithStatement | ReturnStatement | LabeledStatement | BreakStatement | ContinueStatement | IfStatement | SwitchStatement | ThrowStatement | TryStatement | WhileStatement | DoWhileStatement | ForStatement | ForInStatement | ForOfStatement | VariableDeclaration | ClassDeclaration | ThisExpression | ArrayExpression | ObjectExpression | YieldExpression | UnaryExpression | UpdateExpression | BinaryExpression | AssignmentExpression | LogicalExpression | MemberExpression | ConditionalExpression | SimpleCallExpression | NewExpression | SequenceExpression | TemplateLiteral | TaggedTemplateExpression | ClassExpression | MetaProperty | AwaitExpression | Property | AssignmentProperty | Super | TemplateElement | SpreadElement | ObjectPattern | ArrayPattern | RestElement | AssignmentPattern | ClassBody | MethodDefinition | ImportDeclaration | ExportNamedDeclaration | ExportDefaultDeclaration | ExportAllDeclaration | ImportSpecifier | ImportDefaultSpecifier | ImportNamespaceSpecifier | ExportSpecifier

说到这里,聪明的你,可能想到了 Babel ,想到了 js 混淆,想到了更多背后的东西。接下来,我们要介绍介绍 Babel 是如何将 ES6 转成 ES5 的。

五、关于 Babel

由于 ES6 的兼容问题,很多情况下,我们都在使用 Babel 插件来进行编译,那么有没有想过 Babel 是如何工作的呢?先来看看:

let sum = (a, b)=>{return a+b};

AST 大概如此:

JSON 格式可能会看的清楚些:

{
  "type": "Program",
  "start": 0,
  "end": 31,
  "body": [
    {
      "type": "VariableDeclaration",
      "start": 0,
      "end": 31,
      "declarations": [
        {
          "type": "VariableDeclarator",
          "start": 4,
          "end": 30,
          "id": {
            "type": "Identifier",
            "start": 4,
            "end": 7,
            "name": "sum"
          },
          "init": {
            "type": "ArrowFunctionExpression",
            "start": 10,
            "end": 30,
            "id": null,
            "expression": false,
            "generator": false,
            "params": [
              {
                "type": "Identifier",
                "start": 11,
                "end": 12,
                "name": "a"
              },
              {
                "type": "Identifier",
                "start": 14,
                "end": 15,
                "name": "b"
              }
            ],
            "body": {
              "type": "BlockStatement",
              "start": 18,
              "end": 30,
              "body": [
                {
                  "type": "ReturnStatement",
                  "start": 19,
                  "end": 29,
                  "argument": {
                    "type": "BinaryExpression",
                    "start": 26,
                    "end": 29,
                    "left": {
                      "type": "Identifier",
                      "start": 26,
                      "end": 27,
                      "name": "a"
                    },
                    "operator": "+",
                    "right": {
                      "type": "Identifier",
                      "start": 28,
                      "end": 29,
                      "name": "b"
                    }
                  }
                }
              ]
            }
          }
        }
      ],
      "kind": "let"
    }
  ],
  "sourceType": "module"
}

结构大概如此,那我们再用代码模拟一下:

const babel = require('babel-core'); //babel核心解析库
const t = require('babel-types'); //babel类型转化库

let code = `let sum = (a, b)=>{return a+b}`;
let ArrowPlugins = {
//访问者模式
visitor: {
  //捕获匹配的API
    ArrowFunctionExpression(path) {
      let { node } = path;
      let body = node.body;
      let params = node.params;
      let r = t.functionExpression(null, params, body, false, false);
      path.replaceWith(r);
    }
  }
}
let d = babel.transform(code, {
  plugins: [
    ArrowPlugins
  ]
})
console.log(d.code);

记得安装 babel-corebabel-types 这俩插件,之后运行 babel.js ,我们看到了这样的输出:

let sum = function (a, b) {
  return a + b;
};

这里,我们完美的将箭头函数转换成了标准函数。

那么问题又来了,如果是简写呢,像这样,还能正常编译吗:

let sum = (a, b)=>a+b

Body 部分的结构发生了变化,所以,我们的 babel.js 运行就会报错了。

TypeError: unknown: Property body of FunctionExpression expected node to be of a type ["BlockStatement"] but instead got "BinaryExpression"

意思很明了,我们的 body 类型变成 BinaryExpression 不再是 BlockStatement ,所以需要做一些修改:

const babel = require('babel-core'); //babel核心解析库
const t = require('babel-types'); //babel类型转化库

let code = `let sum = (a, b)=> a+b`;
let ArrowPlugins = {
//访问者模式
  visitor: {
  //捕获匹配的API
    ArrowFunctionExpression(path) {
      let { node } = path;
      let params = node.params;
      let body = node.body;
      if(!t.isBlockStatement(body)){
        let returnStatement = t.returnStatement(body);
        body = t.blockStatement([returnStatement]);
      }
      let r = t.functionExpression(null, params, body, false, false);
      path.replaceWith(r);
    }
  }
}
let d = babel.transform(code, {
  plugins: [
    ArrowPlugins
  ]
})
console.log(d.code);

看看输出结果:

let sum = function (a, b) {
  return a + b;
};

看起来不错,堪称完美~

六、深入 Babel

当然,我们简单演示了 Babel 是如何来编译代码的,但是并非简单如此。

七、具体语法树

看到抽象语法树,我们脑海中会出现这样一个疑问:有没有具体语法树呢?

和抽象语法树相对的是具体语法树(通常称作分析树)。一般的,在源代码的翻译和编译过程中,语法分析器创建出分析树。一旦 AST 被创建出来,在后续的处理过程中,比如语义分析阶段,会添加一些信息。

语法分析器

八、参考:

分享到: