Babel AST 生成之路

时间:2021-2-20 作者:admin

上一篇文章分析 Babel 编译流程的时候,提到 Babel 会将 JS 代码转换成 AST(抽象语法树)。这种行为是一种通用的行为,无论什么编程语言都会将源代码解析成 AST,AST 不是 Babel 特有的,更不是 JS 特有的

为什么要这么做呢?原始的 JS 文件是计算机是无法理解的,计算机也很难直接修改 JS 代码,但是转换成 AST 后,由于 AST 本质上是一组表示程序结构的对象,我们可以通过修改这个对象,间接的实现修改代码的目的。chrome V8 引擎也是这么做的,比起 Bable 更进一步的是,V8 引擎会编译 AST 生成字节码。

Javascript AST 规范

AST 本质上是一组表示程序结构的对象,那这个对象长什么样子是谁规定的呢?JavaScript 最初的 AST 其实是用在 JS 之父 Brendan Eich 设计了第一代 JS 引擎 SpiderMonkey 中的,后交给了 Mozilla 维护,之后将其开源形成 Parser_API。慢慢的,这种格式成为操纵 JavaScript 源代码的工具的通用语言。

与此同时,JavaScript 也在不断发展。一些大佬创建了项目ESTree 用于更新 AST 规则,以跟上 JavaScript 语言的发展,目前已成为社区标准。Babel 中使用的 AST 就是基于 ESTree 做的,当然,Babel 也做了一些修改。

举例看看 AST 大概是什么样的,一个简单的变量申明,会生成如下AST(出于简化的目的移除了某些属性)。

const a = 1;
{
  "type": "Program",
  "comments": [],
  "sourceType": "module",
  "body": [
    {
      "type": "VariableDeclaration",
      "declarations": [
        {
          "type": "VariableDeclarator",
          "id": {
            "type": "Identifier",
            "name": "a"
          },
          "init": {
            "type": "Literal",
            "value": 1,
          }
        }
      ],
      "kind": "const"
    }
  ]
}

在这样一个 JSON 树中,每一层都有相似的结构,叫做节点(Node),一个 AST 可以由单一的节点或是成百上千个节点构成。

interface Node {
  type: string;
}

只要是节点,就会有 type 字段,表示节点的类型(如: “FunctionDeclaration”,”Identifier”,或 “BinaryExpression”)。 每一种类型的节点定义了一些附加属性用来进一步描述该节点类型。Babel 还为每个节点额外生成了一些属性,例如 location,start,end 等。用于描述该节点在原始代码中的位置。

我们现在开始分析一个 AST 是如何生成的。

词法分析

通常,编译器编译代码首选会进行词法分析。@babel/parser 提供的就是词法分析 + 语法分析的功能。先看词法分析,正确理解文章的前提是认识每个单词,程序也是一样,所以程序需要能正确的分割代码,得到一个个的单词,称之为 ‘Token’。比如对于下列代码,正确的分词是分成 [‘a’, ‘>=’, ‘1’] 三个词。

a >= 1;

词法分析可以简单的理解为分词,对于自然语言来讲,分词是非常复杂的一项工程,但是对于一门编程语言来说,由于编程规则的存在,我们可以利用规则来简化这个过程,区分不同的 Token。我们看下 Babel 中的分词代码。每个 case 就是一条分词规则,由于代码量较大,如下代码只列出一部分规则。

packages/babel-parser/src/tokenizer/index.js

getTokenFromCode(code: number): void {
  switch (code) {
    // '.' 点
    case charCodes.dot:
      this.readToken_dot();
      return;

    // '(' 左括号
    case charCodes.leftParenthesis:
      ++this.state.pos;
      this.finishToken(tt.parenL);
      return;

    // 数字
    case charCodes.digit1:
    case charCodes.digit2:
    case charCodes.digit3:
    case charCodes.digit4:
    case charCodes.digit5:
    case charCodes.digit6:
    case charCodes.digit7:
    case charCodes.digit8:
    case charCodes.digit9:
      this.readNumber(false);
      return;

    // "" | '' 单引号或双引号
    case charCodes.quotationMark:
    case charCodes.apostrophe:
      this.readString(code);
      return;

    // 以上都没匹配,可能是标识符
    default:
      if (isIdentifierStart(code)) {
        this.readWord();
        return;
      }
  }
}

从代码中可以看出,词法分析的本质就是对于一些规则的程序化,比如我们需要识别 101 这样的数字。当程序扫描到一个数字字符的时候,就开始把它看做数字,直到遇到非数字的字符。再比如我们需要识别 “abc” 这样的字符串,那我们扫描到双引号或者单引号的时候,就把它看做字符串,知道遇到另一个双引号或者单引号。

对于示例代码,由于首个字符是 ‘c’,不是数字也不是符号,会进入判断是否是标识符(Identifier)的流程。isIdentifierStart 方法用于判断一个标识符的首字符是否合法,这段代码表示了这样的一个规则:一个标识符可以是以 $ 或 _ 或字母开头。

export function isIdentifierStart(code: number): boolean {
  // $ 合法
  if (code < charCodes.uppercaseA) return code === charCodes.dollarSign;
  // A - Z 合法
  if (code <= charCodes.uppercaseZ) return true;
  // _ 下划线合法
  if (code < charCodes.lowercaseA) return code === charCodes.underscore;
  // a - z 合法
  if (code <= charCodes.lowercaseZ) return true;
  if (code <= 0xffff) {
    return (
      // 非 ASCII 字符
      code >= 0xaa && nonASCIIidentifierStart.test(String.fromCharCode(code))
    );
  }
  // > 0xffff 也可能是合法的
  return isInAstralSet(code, astralIdentifierStartCodes);
}

readWord 方法中会从当前的起点开始,向后读字符,依次判断每个字符是否是满足标识符约束(isIdentifierChar 方法),很显然,’o’, ‘n’, ‘s’, ‘t’ 都满足,直到空格,此时将 const 作为一个完整的标识符。

export function isIdentifierChar(code: number): boolean {
  // $ 合法
  if (code < charCodes.digit0) return code === charCodes.dollarSign;
  // 1 - 9 合法
  if (code < charCodes.colon) return true;
  // 后续的判断 isIdentifierStart 基本一致
  ...
}

接下来判断 const 是否是关键字,Babel 中定义了 35 个关键词,比如常见的 if、else、switch 等都是关键词。根据关键字获得这个 token 的 type,每个 type 都对应的是不同的规则。不仅如此,词法分析还会同时记录这个 ‘token’ 的位置信息以及一些上下文信息。

const type = keywordTypes.get(word) || tt.name;
export const types: { [name: string]: TokenType } = {
  ...
  // Keywords
  // Don't forget to update packages/babel-helper-validator-identifier/src/keyword.js
  // when new keywords are added
  _break: createKeyword("break"),
  _case: createKeyword("case", { beforeExpr }),
  _catch: createKeyword("catch"),
  _continue: createKeyword("continue"),
  _debugger: createKeyword("debugger"),
  _default: createKeyword("default", { beforeExpr }),
  _do: createKeyword("do", { isLoop, beforeExpr }),
  _else: createKeyword("else", { beforeExpr }),
  _finally: createKeyword("finally"),
  _for: createKeyword("for", { isLoop }),
  _function: createKeyword("function", { startsExpr }),
 ...
};

我们通过 switch case 实现的分词的规则,其实是实现了一个“有限状态自动机(FSM)”。有限状态自动机拥有有限数量的状态,每个状态可以迁移到零个或多个状态。比如我们需要区 11 和 abc 这两种状态,那我就可以构建如下的 FSM

它有 3 个状态,状态 0 表示初始状态,状态 1 表示字符串,状态 2 表示 数字。输入一个字符串,进入初始状态 0 ,初始状态是不稳定的状态,图上表示为一个圈,通过判断首字符是字母还是数字,进入状态 1 或者 状态 2,这两个状态是稳定的状态,用两个圈表示。状态 2 的后续如果还是数字,就保留在状态 2。

FSA 非常适合词法分析,配合正则表达式,我们可以更加快速的实现分词。在回过头来看 getTokenFromCode 方法,每个 case 就代表一种状态,每种状态又会延续出新的状态,最终会停留在一个稳定的状态上,此时也就得到了 ‘Token’。

语法分析

要做到语法分析,其实要做的就是对于语言要进行建模与抽象,比如我们需要支持表达式语句,那就需要定义加减乘除与或非等运规则,同时还要兼顾运算间的优先级与结合性等等。语法分析整个工程是有一套完备的理论支持与实践参考,还有一些诸如 Antrl 开源工具可以帮助我们快速的实现这些规则。JS 的语法规则可以在ECMA官网查看。

语法分析的结果就是 AST,这个过程比较复杂,会涉及到一系列的编译原理的概念,我尽量以比较纯粹的编程的角度看待语法分析的一些问题。

以 const a = 1 为例。这是一个变量声明语句,它的规则是这样的,以 var 或者 let 或者 const 开头,后面跟标识符,然后有可选的初始化部分,也就是一个等号和一个表达式,最后再加分号

具体代码如下,词法分析中获得了 const 这样一个 token,并判断这是一个关键字,根据这个 token 的类型,判断这是一个变量声明语句。执行 parseVarStatement 方法。

packages/babel-parser/src/parser/statement.js

parseVarStatement(
    node: N.VariableDeclaration,
    kind: "var" | "let" | "const",
  ): N.VariableDeclaration {
    // 获得下一个 token,也就是 a
    this.next();
    // 构建 declarations,解析标识符 a 以及它的初值
    this.parseVar(node, false, kind);
    // 使用分号 ; 作为结尾
    this.semicolon();
    // 这是一个变量声明节点,VariableDeclaration
    return this.finishNode(node, "VariableDeclaration");
}

如下就是一个表示变量声明的 AST 节点(出于简化的目的移除了某些属性)。type 是每个节点都有的属性,根据 type 的不同节点还有一些特殊的属性。在 VariableDeclaration 节点中,declarations 就表示这个变量的具体信息,它是一个数组,表示我们一个可以申明多个变量。id 就是变量的名称,init 表示这个变量被初始化的值。我们的目的就是要转化为这样的一个 AST。

{
  "type": "VariableDeclaration",
  "declarations": [
    {
      "type": "VariableDeclarator",
      "id": {
        "type": "Identifier",
        "name": "a"
      },
      "init": {
        "type": "Literal",
        "value": 1,
      }
    }
  ],
  "kind": "const"
}

parseVarStatement 首先会分析后续的 token 来构造 declarations 节点, this.next() 就是获得下一个 token,也就是获得标识符 a,而 parseVar 方法用于解析具体的函数申明。

packages/babel-parser/src/parser/statement.js(出如简化的目的省略了部分代码

parseVar(
    node: N.VariableDeclaration,
    isFor: boolean,
    kind: "var" | "let" | "const",
  ): N.VariableDeclaration {
    // node 上增加 declarations,默认是个数组
    const declarations = (node.declarations = []);

    // const
    node.kind = kind;
    for (;;) {
      // 构造一个节点
      const decl = this.startNode();

      // 构造节点的 id,'a' 会被认为是一个 Identifier(标识符)
      this.parseVarId(decl, kind);

      // 判断有没有等号 = 
      if (this.eat(tt.eq)) {

        // 有等号,意味着变量申明存在初始值,需要解析这个值作为节点的 init 属性
        decl.init = isFor
          ? this.parseMaybeAssignDisallowIn()
          : this.parseMaybeAssignAllowIn();
      }

      // decl 是一个类型是 VariableDeclarator,有 id 属性节点,可能有 init 属性节点的节点
      declarations.push(this.finishNode(decl, "VariableDeclarator"));

      // 判断多个申明之间的逗号。
      if (!this.eat(tt.comma)) break;
    }
    return node;
  }

简单的翻译一下上述代码,parseVar 建立了 declarations 节点,该节点的类型也是 VariableDeclarator。解析第一个 token 作为变量名称,类型是 Identifier。如果有等号,意味着变量申明存在初始值,解析这个值作为节点的 init 属性。整段代码在 for 循环中,一次解析多个变量申明。

变量的初值不仅可以是一个字面量,也可以是一个表达式,我们对之前的代码做如下修改。

const a = 1 + 2 * 3; 

由于表达式存在优先级的,同一优先级满足左结合性,括号可以改变优先级,构建一个合适的表达式模型还是很有难度的。

如下是该表达式生成的 AST 节点,type 为 BinaryExpression,意思是二元运算,BinaryExpression 中有 left,operator,right 三个属性,operator 是操作符,left 和 right 是个嵌套的结构,里面还可以有 BinaryExpression,这种嵌套的设计方式考虑到了运算的优先级,永远是内层的先计算。

"init": {
  "type": "BinaryExpression",
  "left": {
    "type": "Literal",
    "value": 1,
  },
  "operator": "+",
  "right": {
    "type": "BinaryExpression",
    "left": {
      "type": "Literal",
      "value": 2,
    },
    "operator": "*",
    "right": {
      "type": "Literal",
      "value": 3,
    }
  }
}

由此我们以可以想到,在一个运算节点中,外层的节点表示的是低优先级的计算,而内层的节点表示的是高优先级的计算。这也是解析表达式最基本的思路,定义运算的基本规则,根据优先级的关系递归调用,在执行的过程中,程序可以根据这些规则和递归关系推导出结果。

MDN上有一份完整的运算符优先级表,这份表就是我们就是我们编写运算表达式的依据。根据优先级规则,我们会优先尝试匹配高优先级的运算表达式,然后是低优先级。为了实现这个效果,代码是这样设计的,计算机会优先调用生成低优先级,也就是外层节点的代码,这这些代码中会首先调用比他高的优先级的代码,这样一层一层向上,直到匹配。

我们看 parseMaybeAssign 方法(省略部分代码),该方法是解析表达式的入口,从名字可以看出,Babel 解析一个表达式,首先会认为这是一个赋值(Assign)表达式,原因是赋值表达式优先级很低,一定是外层节点。进入方法后,尝试匹配条件表达式,然后判断这是不是赋值表达式,是的话,重新构造一个 AST 节点,type 类型为 AssignmentExpression。

parseMaybeAssign(
    refExpressionErrors?: ?ExpressionErrors,
    afterLeftParse?: Function,
    refNeedsArrowPos?: ?Pos,
  ): N.Expression {
    // 省略 yield 的一些判断
    // yield 优先级低于赋值,由于语法特征非常明显,且位于表达式头部,可以直接判断

    // 尝试匹配条件表达式
    let left = this.parseMaybeConditional(
      refExpressionErrors,
      refNeedsArrowPos,
    );

    // 是赋值表达式,例如 a += 1
    if (this.state.type.isAssign) {
      const node = this.startNodeAt(startPos, startLoc);
      const operator = this.state.value;
      node.operator = operator;

      // left 在前面已经解析完毕,是 a
      node.left = left;

      ...

      // 解析赋值符号右侧的值,也就是 1
      this.next();
      node.right = this.parseMaybeAssign();

      // type 是 AssignmentExpression,表示赋值表达式
      return this.finishNode(node, "AssignmentExpression");
    } 

    return left;
  }

条件运算符的优先级高于赋值,所以在 parseMaybeAssign 中,调用了 parseMaybeConditional,而逻辑运算的优先级又高于条件运算符,所以在 parseMaybeConditional 中, 会先调用 parseExprOps 进行匹配。

parseMaybeConditional(
  refExpressionErrors: ExpressionErrors,
  refNeedsArrowPos?: ?Pos,
): N.Expression {
  const startPos = this.state.start;
  const startLoc = this.state.startLoc;
  const potentialArrowAt = this.state.potentialArrowAt;
  // 尝试匹配逻辑运算符
  const expr = this.parseExprOps(refExpressionErrors);

  // 箭头函数的话,退出表达式解析
  if (this.shouldExitDescending(expr, potentialArrowAt)) {
    return expr;
  }

  // 判断三元条件(?:)运算符,相当于 if else 的变种
  return this.parseConditional(expr, startPos, startLoc, refNeedsArrowPos);
}

parseConditional 判断三元条件(?:)运算符,该方法在一个表达式解析完毕后执行,判断这个表达式后面的一个 token 是否是问号,如果是,那之前的表达式就是一个条件语句,放到 test 属性上,后续会递归调用 parseMaybeAssign 方法,解析后面的两个表达式。

简单来说就是表达了这样一个规则:… ? … : …

parseConditional(
  expr: N.Expression,
  startPos: number,
  startLoc: Position,
  // FIXME: Disabling this for now since can't seem to get it to play nicely
  // eslint-disable-next-line no-unused-vars
  refNeedsArrowPos?: ?Pos,
): N.Expression {
  if (this.eat(tt.question)) {
    const node = this.startNodeAt(startPos, startLoc);
    node.test = expr;
    node.consequent = this.parseMaybeAssignAllowIn();
    this.expect(tt.colon);
    node.alternate = this.parseMaybeAssign();
    return this.finishNode(node, "ConditionalExpression");
  }
  return expr;
}

parseExprOps 的思路和上述是一致的,就不做详细的分析了。

从代码的角度看,语法分析就是一系列的规则的匹配与嵌套,优先级低的规则嵌套优先级高的规则(这样才能保证优先级高的先执行),我们发现,这些规则代码写的都很“干净”,保证 AST 结构的推导不会受到调用上下文的影响,如果了解编译原理,会发现,这其实就是上线文无关文法的代码实现。

总结

  1. @babel/parser 对原始代码进行词法分析 + 语法分析,生成 AST。AST 本质上是一组表示程序结构的对象,我们可以通过修改这个对象,间接修改代码。现代前端技术,比如 sass,less 以及 ES6+ 都是利用了这个能力实现语法上的突破。

  2. 词法分析被抽象为了一个“有限状态自动机”,在某个状态下,满足一些条件后,会进行状态转移,转移到新的状态,从代码层面看,是一系列的 switch case 语句。经过词法分析后,代码被准确的切割,每个被切分的词叫做 token。

  3. 语法分析的复杂性在于规则的嵌套,匹配以及需要考虑一些结合性的问题。使用低优先级的规则嵌套高优先级规则,保证高优先级的规则优先执行。语法分析需要注意的细节很多,建议了解上下文无关文法, LL 算法等基础后再慢慢分析。

Babel 编译的核心就是操作 AST 对象,后续我们会分析 Babel 插件是如何操作 AST 的

如果您觉得有所收获,就请点个赞吧!

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。