JavaScript AST 抽象语法树

转自: https://www.overtaking.top/2018/07/25/20180725130233/

AST 抽象语法树简介

AST(Abstract Syntax Tree)是源代码的抽象语法结构树状表现形式,Webpack、ESLint、JSX、TypeScript 的编译和模块化规则之间的转化都是通过 AST 来实现对代码的检查、分析以及编译等操作。

JavaScript 语法的 AST 语法树

JavaScript 中想要使用 AST 进行开发,要知道抽象成语法树之后的结构是什么,里面的字段名称都代表什么含义以及遍历的规则,可以通过 http://esprima.org/demo/parse.html 来实现 JavaScript 语法的在线转换。

通过在线编译工具,可以将 function fn(a, b) {} 编译为下面的结构。

{
  "type": "Program",
  "body": [
    {
      "type": "FunctionDeclaration",
      "id": {
        "type": "Identifier",
        "name": "fn"
      },
      "params": [
        {
          "type": "Identifier",
          "name": "a"
        },
        {
          "type": "Identifier",
          "name": "b"
        }
      ],
      "body": {
        "type": "BlockStatement",
        "body": []
      },
      "generator": false,
      "expression": false,
      "async": false
    }
  ],
  "sourceType": "script"
}

将 JavaScript 语法编译成抽象语法树后,需要对它进行遍历、修该并重新编译,遍历树结构的过程为 “先序深度优先”。

esprima、estraverse 和 escodegen

esprimaestraverse 和 escodegen 模块是操作 AST 的三个重要模块,也是实现 babel 的核心依赖,下面是分别介绍三个模块的作用。

esprima 将 JS 转换成 AST

esprima 模块的用法如下:文件:esprima-test.js

const esprima = require('esprima');

let code = 'function fn() {}';

// 生成语法树
let tree = esprima.parseScript(code);

console.log(tree);

// Script {
//   type: 'Program',
//   body:
//   [ FunctionDeclaration {
//     type: 'FunctionDeclaration',
//     id: [Identifier],
//     params: [],
//     body: [BlockStatement],
//     generator: false,
//     expression: false,
//     async: false } ],
//   sourceType: 'script' }

通过上面的案例可以看出,通过 esprima 模块的 parseScript 方法将 JS 代码块转换成语法树,代码块需要转换成字符串,也可以通过 parseModule 方法转换一个模块。

estraverse 遍历和修改 AST

查看遍历过程:文件:estraverse-test.js

const esprima = require('esprima');
const estraverse = require('estraverse');

let code = 'function fn() {}';

// 遍历语法树
estraverse.traverse(esprima.parseScript(code), {
  enter(node) {
    console.log('enter', node.type);
  },
  leave() {
    console.log('leave', node.type);
  }
});

// enter Program
// enter FunctionDeclaration
// enter Identifier
// leave Identifier
// enter BlockStatement
// leave BlockStatement
// leave FunctionDeclaration
// leave Program

上面代码通过 estraverse 模块的 traverse 方法将 esprima 模块转换的 AST 进行了遍历,并打印了所有的 type 属性并打印,每含有一个 type 属性的对象被叫做一个节点,修改是获取对应的类型并修改该节点中的属性即可。

其实深度遍历 AST 就是在遍历每一层的 type 属性,所以遍历会分为两个阶段,进入阶段和离开阶段,在 estraverse 的 traverse 方法中分别用参数指定的 entry 和 leave 两个函数监听,但是我们一般只使用 entry

escodegen 将 AST 转换成 JS

下面的案例是一个段 JS 代码块被转换成 AST,并将遍历、修改后的 AST 重新转换成 JS 的全过程。文件:escodegen-test.js

const esprima = require('esprima');
const estraverse = require('estraverse');
const escodegen = require('escodegen');

let code = 'function fn() {}';

// 生成语法树
let tree = esprima.parseScript(code);

// 遍历语法树
estraverse.traverse(tree, {
  enter(node) {
    // 修改函数名
    if (node.type === 'FunctionDeclaration') {
      node.id.name = 'ast';
    }
  }
});

// 编译语法树
let result = escodegen.generate(tree);

console.log(result);

// function ast() {
// }

在遍历 AST 的过程中 params 值为数组,没有 type 属性。

实现 Babel 语法转换插件

实现语法转换插件需要借助 babel-core 和 babel-types 两个模块,其实这两个模块就是依赖 esprimaestraverse 和 escodegen 的。

使用这两个模块需要安装,命令如下:

1
npm install babel-core babel-types

plugin-transform-arrow-functions

plugin-transform-arrow-functions 是 Babel 家族成员之一,用于将箭头函数转换 ES5 语法的函数表达式。

文件:plugin-transform-arrow-functions.js

const babel = require('babel-core');
const types = require('babel-types');

// 箭头函数代码块
let sumCode = `
const sum = (a, b) => {
  return a + b;
}`;
let minusCode = `const minus = (a, b) => a - b;`;

// 转化 ES5 插件
const ArrowPlugin = {
  // 访问者(访问者模式)
  visitor: {
    // path 是树的路径
    ArrowFunctionExpression(path) {
      // 获取树节点
      let node = path.node;

      // 获取参数和函数体
      let params = node.params;
      let body = node.body;

      // 判断函数体是否是代码块,不是代码块则添加 return 和 {}
      if (!types.isBlockStatement(body)) {
        let returnStatement = types.returnStatement(body);
        body = types.blockStatement([returnStatement]);
      }

      // 生成一个函数表达式树结构
      let func = types.functionExpression(null, params, body, false, false);

      // 用新的树结构替换掉旧的树结构
      path.replaceWith(func);
    }
  }
};

// 生成转换后的代码块
let sumResult = babel.transform(sumCode, {
  plugins: [ArrowPlugin]
});

let minusResult = babel.transform(minusCode, {
  plugins: [ArrowPlugin]
});

console.log(sumResult.code);
console.log(minusResult.code);

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

我们主要使用 babel-core 的 transform 方法将 AST 转化成代码块,第一个参数为转换前的代码块(字符串),第二个参数为配置项,其中 plugins 值为数组,存储修改 babal-core 转换的 AST 的插件(对象),使用 transform 方法将旧的 AST 处理成新的代码块后,返回值为一个对象,对象的 code 属性为转换后的代码块(字符串)。

内部修改通过 babel-types 模块提供的方法实现,API 可以到 https://github.com/babel/babel/tree/6.x/packages/babel-types 中查看。

ArrowPlugin 就是传入 transform 方法的插件,必须含有 visitor 属性(固定),值同为对象,用于存储修改语法树的方法,方法名要严格按照 API,对应的方法会修改 AST 对应的节点。

在 types.functionExpression 方法中参数分别代表,函数名(匿名函数为 null)、函数参数(必填)、函数体(必填)、是否为 generator 函数(默认 false)、是否为 async 函数(默认 false),返回值为修改后的 AST,path.replaceWith 方法用于替换 AST,参数为新的 AST。

plugin-transform-classes

plugin-transform-classes 也是 Babel 家族中的成员之一,用于将 ES6 的 class 类转换成 ES5 的构造函数。

文件:plugin-transform-classes.js

const babel = require('babel-core');
const types = require('babel-types');

// 类
let code = `
class Person {
  constructor(name) {
    this.name = name;
  }
  getName () {
    return this.name;
  }
}`;

// 将类转化 ES5 构造函数插件
const ClassPlugin = {
  visitor: {
    ClassDeclaration(path) {
      let node = path.node;
      let classList = node.body.body;

      // 将取到的类名转换成标识符 { type: 'Identifier', name: 'Person' }
      let className = types.identifier(node.id.name);
      let body = types.blockStatement([]);
      let func = types.functionDeclaration(
        className,
        [],
        body,
        false,
        false
      );
      path.replaceWith(func);

      // 用于存储多个原型方法
      let es5Func = [];

      // 获取 class 中的代码体
      classList.forEach((item, index) => {
        // 函数的代码体
        let body = classList[index].body;

        // 获取参数
        let params = item.params.length ?
          item.params.map(val => val.name) :
          [];

        // 转化参数为标识符
        params = types.identifier(params);

        // 判断是否是 constructor,如果构造函数那就生成新的函数替换
        if (item.kind === 'constructor') {
          // 生成一个构造函数树结构
          func = types.functionDeclaration(
            className,
            [params],
            body,
            false,
            false
          );
        } else {
          // 其他情况是原型方法
          let proto = types.memberExpression(
            className,
            types.identifier('prototype')
          );

          // 左侧层层定义标识符 Person.prototype.getName
          let left = types.memberExpression(
            proto,
            types.identifier(item.key.name)
          );

          // 右侧定义匿名函数
          let right = types.functionExpression(
            null,
            [params],
            body,
            false,
            false
          );

          // 将左侧和右侧进行合并并存入数组
          es5Func.push(types.assignmentExpression('=', left, right));
        }
      });

      // 如果没有原型方法,直接替换
      if (es5Func.length === 0) {
        path.replaceWith(func);
      } else {
        es5Func.push(func);
        // 替换 n 个节点
        path.replaceWithMultiple(es5Func);
      }
    }
  }
};

// 生成转换后的代码块
result = babel.transform(code, {
  plugins: [ClassPlugin]
});

console.log(result.code);

// Person.prototype.getName = function() {
//     return this.name;
// }
// function Person(name) {
//     this.name = name;
// }

上面这个插件的实现要比 plugin-transform-arrow-functions 复杂一些,归根结底还是将要互相转换的 ES6 和 ES5 语法树做对比,找到他们的不同,并使用 babel-types 提供的 API 对语法树对应的节点属性进行修改并替换语法树,值得注意的是 path.replaceWithMultiple 与 path.replaceWith 不同,参数为一个数组,数组支持多个语法树结构,可根据具体修改语法树的场景选择使用,也可根据不同情况使用不同的替换方法。

总结

通过本节我们了解了什么是 AST 抽象语法树、抽象语法树在 JavaScript 中的体现以及在 NodeJS 中用于生成、遍历和修改 AST 抽象语法树的核心依赖,并通过使用 babel-core 和 babel-types 两个模块简易模拟了 ES6 新特性转换为 ES5 语法的过程,希望可以为后面自己实现一些编译插件提供了思路。

AST – 抽象语法树

转自: http://blog.chinaunix.net/uid-26750235-id-3139100.html

抽象语法树简介

()简介

抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上的每个节点都表示源代码中的一种结构,这所以说是抽象的,是因为抽象语法树并不会表示出真实语法出现的每一个细节,比如说,嵌套括号被隐含在树的结构中,并没有以节点的形式呈现。抽象语法树并不依赖于源语言的语法,也就是说语法分析阶段所采用的上下文无文文法,因为在写文法时,经常会对文法进行等价的转换(消除左递归,回溯,二义性等),这样会给文法分析引入一些多余的成分,对后续阶段造成不利影响,甚至会使合个阶段变得混乱。因些,很多编译器经常要独立地构造语法分析树,为前端,后端建立一个清晰的接口。

抽象语法树在很多领域有广泛的应用,比如浏览器,智能编辑器,编译器。

()抽象语法树实例

(1)四则运算表达式

表达式: 1+3*(4-1)+2

抽象语法树为:

(2)xml

代码2.1

  1. <letter>
  2.   <address>
  3.     <city>ShiChuang</city>
  4.   </address>
  5.   <people>
  6.     <id>12478</id>
  7.     <name>Nosic</name>
  8.   </people>
  9. </letter>

抽象语法树

(3)程序1

代码2.2

  1. while b != 0
  2. {
  3.     if a > b
  4.         a = a-b
  5.     else
  6.         b = b-a
  7. }
  8. return a

抽象语法树

(4)程序2

代码2.3

  1. sum=0
  2. for i in range(0,100)
  3.     sum=sum+i
  4. end

抽象语法树

()为什么需要抽象语法树

当在源程序语法分析工作时,是在相应程序设计语言的语法规则指导下进行的。语法规则描述了该语言的各种语法成分的组成结构,通常可以用所谓的前后文无关文法或与之等价的Backus-Naur范式(BNF)将一个程序设计语言的语法规则确切的描述出来。前后文无关文法有分为这么几类:LL(1),LR(0),LR(1), LR(k) ,LALR(1)等。每一种文法都有不同的要求,如LL(1)要求文法无二义性和不存在左递归。当把一个文法改为LL(1)文法时,需要引入一些隔外的文法符号与产生式。

例如,四则运算表达式的文法为:

文法1.1

  1. E->T|EAT
  2. T->F|TMF
  3. F->(E)|i
  4. A->+|-
  5. M->*|/

改为LL(1)后为:

文法1.2

  1. E->TE’
  2. E’->ATE’|e_symbol
  3. T->FT’
  4. T’->MFT’|e_symbol
  5. F->(E)|i
  6. A->+|-
  7. M->*|/

例如,当在开发语言时,可能在开始的时候,选择LL(1)文法来描述语言的语法规则,编译器前端生成LL(1)语法树,编译器后端对LL(1)语法树进行处理,生成字节码或者是汇编代码。但是随着工程的开发,在语言中加入了更多的特性,用LL(1)文法描述时,感觉限制很大,并且编写文法时很吃力,所以这个时候决定采用LR(1)文法来描述语言的语法规则,把编译器前端改生成LR(1)语法树,但在这个时候,你会发现很糟糕,因为以前编译器后端是对LL(1)语树进行处理,不得不同时也修改后端的代码。

抽象语法树的第一个特点为:不依赖于具体的文法。无论是LL(1)文法,还是LR(1),或者还是其它的方法,都要求在语法分析时候,构造出相同的语法树,这样可以给编译器后端提供了清晰,统一的接口。即使是前端采用了不同的文法,都只需要改变前端代码,而不用连累到后端。即减少了工作量,也提高的编译器的可维护性。

抽象语法树的第二个特点为:不依赖于语言的细节。在编译器家族中,大名鼎鼎的gcc算得上是一个老大哥了,它可以编译多种语言,例如c,c++,java,ADA,Object C, FORTRAN, PASCAL,COBOL等等。在前端gcc对不同的语言进行词法,语法分析和语义分析后,产生抽象语法树形成中间代码作为输出,供后端处理。要做到这一点,就必须在构造语法树时,不依赖于语言的细节,例如在不同的语言中,类似于if-condition-then这样的语句有不同的表示方法

在c中为:

  1. if(condition)
  2. {
  3.     do_something();
  4. }

     在fortran中为:

  1. If condition then
  2.     do_somthing()
  3. end if

在构造if-condition-then语句的抽象语法树时,只需要用两个分支节点来表于,一个为condition,一个为if_body。如下图:

在源程序中出现的括号,或者是关键字,都会被丢掉。