AST 抽象语法树

栏目: JavaScript · 发布时间: 6年前

内容简介:提起 AST 抽象语法树,大家可能并不感冒。但是提到它的使用场景,也许会让你大吃一惊。原来它一直在你左右与你相伴,而你却不知。在计算机科学中,抽象语法树(之所以说语法是「抽象」的,是因为这里的语法并不会表示出真实语法中出现的每个细节。

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

一、什么是抽象语法树

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

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

二、使用场景

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

三、AST Explorer

AST 抽象语法树 我们来看一个 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"
}

而它的语法树大概如此:

AST 抽象语法树

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

(1+2)*3

AST Tree:

AST 抽象语法树

我们删掉括号,看看规则是如何变化的? 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 结构如下图:

AST 抽象语法树

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

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"
}

AST 抽象语法树

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

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 大概如此:

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

AST 抽象语法树

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 被创建出来,在后续的处理过程中,比如语义分析阶段,会添加一些信息。

语法分析器

八、参考:


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Fluent Python

Fluent Python

Luciano Ramalho / O'Reilly Media / 2015-8-20 / USD 39.99

Learn how to write idiomatic, effective Python code by leveraging its best features. Python's simplicity quickly lets you become productive with it, but this often means you aren’t using everything th......一起来看看 《Fluent Python》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

html转js在线工具
html转js在线工具

html转js在线工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试