babel源码分析之一：AST生成

[laughing-pic-zhu]

前言

babel是javaScript编译器,主要用于将ECMAScript2015+版本的代码转化为具有兼容性的较低版本，从而让代码适用于各种环境。
它的早期代码从acorn项目中fork出来，后续提供了acorn不具备的一整套的代码解析，转换，生成的功能。

现在的babel有着抽象的工程实现很难直接啃源码。笔者打算通过一系列早期功能点的实现来慢慢揭开其内部机制。babel代码转换第一步是将源码转化成AST(Abstract Syntax Tree)。
本文将借助babel/acorn初期的源码,详细讲解其生成AST的工程细节。

阅读本文前，希望您对AST的概念如Statement,Expression有一些了解。ESTree 规范文档传送门

功能分析

示例

先举个代码转为ast的例子:

/*
  测试whileStatement
*/
while(b !== 0){
  if (a > b){
   a = a - b;
  }else{
   b = b - a;
  }
}
console.log(a)

转化后的ast结构

实现思路

上图的整个树的生成都是由一次次词法，语法解析中递归出来的。

一个通用完整的statement递归函数逻辑：

• 去除注释,空格,换行。
• 词法分析: 将源码中的字符转化为单词。即解析token，如while(b !== 0){将被识别为的[while,(,b,!==,0,),{]这7个单词。
• 语法分析：通过词法解析出来的单词token来获取statement节点的类型并解析，然后对其中可能含有的expression进行相应的语法解析。解析出其开始的start，结束的end，值value以及值的类型label。
• 索引移到下一位，开启新一轮的递归。以此循环直到将文件字符串读取完毕。

  ...
  while (tokType !== _eof) {
        const statement = parseStatement();
        if (first) {
            first = false;
            if (isUseStrict(statement)) {
                setStrict(true);
            }
        }
        node.body.push(statement);
    }
 ...   

部分Statement, Experssion内部也有自己的递归逻辑：

Statement内部递归

VariableDeclaration

以逗号分隔的递归如var a,b,c。

FunctionDeclaration

参数内部以逗号分隔的行参递归,大括号内部的以分号分割的statement递归，如function a(b,c,d){e;f;g;}。

BlockStatement

大括号内部的以分号分割的statement递归,直到到遇到大括号结束符，如{e;f;g}。

IfStatement

以else关键字的递归，如if(a){}else if(b){}else{}。

SwitchStatement

以 case以及default关键字的递归，如switch(a){case a:xxx;caseb :xxx; default: xxx;}。

ForStatement,ForInStatement，WhileStatement,DoWhileStatement,TryStatement，LabeledStatement

都是大括号内部的以分号分割的statement递归，大括号结束符，如

for(;;){e;f;g;} 
for (var a in b){e;f;g} 
while(a){e;f;g} 
do{e;f;g;}while(a) 
try{e;f;g}catch(a){e;f;g}finally{e;f;g;}

Experssion内部递归

ObjectExpression

以逗号分隔分割的递归，直到遇到大括号结束符。如{a,b,c,}

ArrayExpression

以逗号分隔分割的递归，直到遇到中括号结束符。如[a,b,c,]

FunctionExpression

和FunctionDeclaration一样，参数内部以逗号分隔的行参递归,大括号内部的以分号分割的statement递归，如var a=function (b,c,d){e;f;g;}。

功能实现

单个通用的递归函数的实现的功能如下

去除注释,空格,换行

注释分两种:

/* */,或者 / ** */的多行注释以及//的单行注释。

空格分为' ' \t \n \r \f

function skipSpace() {
    while (tokenPos < inputLen) {
        const ch = input.charAt(tokenPos);
        if (ch === '/') {
            if (input.charAt(tokenPos + 1) === '/') {
                tokenPos += 2;
                while (tokenPos < inputLen && !newline.test(input.charAt(tokenPos))) {
                    tokenPos++;
                }
            } else if (input.charAt(tokenPos + 1) === '*') {
                const i = input.indexOf('*/', tokenPos + 2);
                if (i < 0) {
                    raise(tokenPos - 2, 'Unterminated comment');
                }
                tokenPos = i + 2;
            } else {
                ++tokenPos;
            }
        } else if (ch === '\n' || ch === '\t' || ch === " " || ch === "\r" || ch === "\f") {
            ++tokenPos;
        } else {
            break;
        }
    }
}

解析token

具体token有非常多，但是按类型分的话，可以分为以下6种：

• string字符串类型。以' " 开头，且以' "结尾。
• regexp正则类型。以/开头，不在[]内且上一个字符不是转译符\的情况下以/结尾。
• word单词类型。关键字如break case catch continue debugger。保留关键字如implements interface let package private以及普通的变量名称。
• number数字类型。类型有：二进制，八进制，十进制和十六进制。其中0x或者0X开头的是十六进制。
• punctuation标点符号类型。如[ { ( , ; ? 等符号。
• operator运算符类型。如+ - * % | & = 等符号。对于不同符号在一起解析的时候，会有不同的解析优先级。
  • 优先级最高为10: - * % ／
  • 优先级为9:+ -
  • 优先级为8: >> >>> << <<<
  • 优先级为7: > >= < <=
  • 优先级为6: === == !== !===
  • 优先级为5: &
  • 优先级为4: ^
  • 优先级为3: |
  • 优先级为2: &&
  • 优先级为1: ||

function readToken() {
    lastStart = tokStart;
    lastEnd = tokEnd;
    tokStart = tokenPos;
    const ch = input.charAt(tokenPos);
    if (tokenPos >= inputLen) {
        return finishToken(_eof);
    }
    if (ch === '\'' || ch === '"') {
        readString(ch);
    } else if (indentifierReg.test(ch)) {
        readWord();
    } else if (digest.test(ch)) {
        readNumber();
    } else if (puncChars.test(ch)) {
        tokenPos++;
        finishToken(puncTypes[ch]);
    } else if (operatorChar.test(ch)) {
        readOperator(ch)
    }
}

解析节点Statements

除了BlockStatement,其他statement是以;或者换行符结束。
每种statement都由自己不同的解析方式以及名称。一个statement可能含有0个或者多个expression。

如while类型的statement解析函数如下

function parseWhile() {
    const node = startNode();
    next();
    node.test = parseParenExpression();
    node.body = parseBlock();
    return finishNode(node, 'WhileStatement');
}

解析后的简单的json类型为

{
      "type": "WhileStatement",
      "test": {
        "type": "AssignmentExpression",
        "operator": "=",
        "left": {
          "type": "Identifier",
          "name": "a"
        },
        "right": {
          "type": "Identifier",
          "name": "b"
        }
      },
      "body": {
        "type": "BlockStatement",
        "body": []
      }
    }

解析expression

这个模块个人认为是最核心的模块，对不同表达式进行解析。

最基本的表达式如：Identifier,Literal,FunctionExpression,ObjectExpression,ArrayExpression,NewExpression。

建立在基本表达式之上的如：a.b的MemberExpression,a()的CallExpression。
++a,a--之类的UpdateExpression。
!a，!!a之类的UnaryExpression。
a||b,a&&b的LogicalExpression，a-b之类的BinaryExpression。
a=b之类的AssignmentExpression。
a?b:c之类的ConditionalExpression。

上面这些复杂类型的解析执行顺序如下:

举个复杂的例子:

var a=!b++?c+1:d.e(f,g);

解析之后的json格式如下

{
      "type": "VariableDeclaration",
      "declarations": [
        {
          "type": "VariableDeclarator",
          "id": {
            "type": "Identifier",
            "name": "a"
          },
          "init": {
            "type": "ConditionalExpression",
            "test": {
              "type": "UnaryExpression",
              "operator": "!",
              "prefix": true,
              "argument": {
                "type": "UpdateExpression",
                "operator": "++",
                "prefix": false,
                "argument": {
                  "type": "Identifier",
                  "name": "b"
                }
              }
            },
            "consequent": {
              "type": "BinaryExpression",
              "left": {
                "type": "Identifier",
                "name": "c"
              },
              "operator": "+",
              "right": {
                "type": "Literal",
                "value": 1,
                "raw": "1"
              }
            },
            "alternate": {
              "type": "CallExpression",
              "callee": {
                "type": "MemberExpression",
                "object": {
                  "type": "Identifier",
                  "name": "d"
                },
                "property": {
                  "type": "Identifier",
                  "name": "e"
                },
                "computed": false
              },
              "arguments": [
                {
                  "type": "Identifier",
                  "name": "f"
                },
                {
                  "type": "Identifier",
                  "name": "g"
                }
              ]
            }
          }
        }
      ],
      "kind": "var"
    }

代码实现

本人的简易版babel实现simple-babel

后话

实现了AST之后，后续也可以拓展很多有趣的功能如代码转换，代码风格检测，代码自动格式化，代码压缩。目前我还不是太明白，以后可以尝试实现一下。

(完)