本文主要讲述如何使用 Antlr4、如何自底向上用 babel 构建 javascript AST 。

COOL-language

COOL 语言是一门并没有广泛用于课堂教学的面向对象语言，全称是 ClassroomObjectOrientedLanguage，遗憾的是它不能进行物联网、VR、游戏和移动端 GUI 编程。幸运的是，熟练的情况下我们可以在三天内将它编译成 javascript，让它就像萝莉穿上魔法少女魔装一样，获得强大的能力（误）。

COOL 语言的代码长这样：


class Main inherits IO {
  jiayimiao(second: Int): Int {
    second + 1
  };

  main(): SELF_TYPE {
    {
      out_string((new Object).type_name().substr(4,1)).
      out_string((isvoid self).type_name().substr(1,3));
      out_string("\n");
    }
  };
};

可以看到类型标注和 flowtype、 typescript 是一个路数，花括号和分号也很 C-style。COOL 和 JS 最大的不同是，COOL 是面向表达式（expression）的语言，jiayimiao() 函数直接返回了 second + 1 的结果，main() 函数直接返回了最后一行 out_string() 的结果，而 javascript 是基于语句（statement）的，转出来大概是这样：

class Main extends IO {
  jiayimiao(second: number): number {
    return this.second + 1;
  }

  main(): void {
    return function codeBlock() {
      this.out_string(new Object().type_name().substr(4, 1)).out_string((!!this).type_name().substr(1, 3));
      return this.out_string('\n');
    }.bind(this)();
  }
}

new Main().main();

expression 和 statement 之间的鸿沟可以通过立即执行函数（IIEF）来填补，除了调用栈容易爆以外没有太大的问题。

基本思路

从语言到语言的编译称为 program-transformation，有很多系统可以帮你搞定这种工作，但我们需要稍微高一点的灵活性，我希望能得到 COOL 语言的抽象语法树（AST）并把它转换成 babel AST，这样我们能保留下尽可能多的 COOL 代码里的类型标注等信息，然后通过前端常用的 babel 插件系统，例如 flow-stripe-type、 flow-runtime、 transform-class-property 等对 AST 进行自定义的转换，最终输出我们需要的版本的 JS 代码。

如何得到 COOL AST

从源代码得到 AST 理论上说需要两步，用词法分析器（lexer）分词，得到切好的一个个词后用语法分析器（parser）。

工程上也需要两步，第二步比较简单，就是把 COOL 的源代码传入下面这个官网给的样例函数（boilerplate）里：

// parseCOOL.js
// @ts-check @flow
import antlr4, { InputStream, CommonTokenStream } from 'antlr4';
import { COOLLexer } from './antlrGenerated/COOLLexer';
import { COOLParser } from './antlrGenerated/COOLParser';

export default function parseCOOL(coolProgram: string) {
  const inputStream = new InputStream(coolProgram);
  const lexer = new COOLLexer(inputStream);
  const tokenStream = new CommonTokenStream(lexer);
  const parser = new COOLParser(tokenStream);
  parser.buildParseTrees = true;
  const coolAst = parser.program();
  return coolAst;
}

第一步稍微复杂一点，就是我们怎么得到上面的 COOLLexer 和 COOLParser 的？

Antlr4 grammar

我使用了一个现代编译器编译器 Antlr4，就是把我对 COOL 语言的语法描述，编译成一个编译器的编译器，而且它很有现代感，可以编译出 Python、typescript、javascript、Java 等常用语言的 lexer 和 parser，可以大幅提高工程效率。

为 Antlr4 写的 COOL 语言语法大概长这样：

// COOL.g4
grammar COOL;

program: programBlocks;
programBlocks
  : classDefine ';' programBlocks #classes
  | EOF #eof
  ;
classDefine: CLASS TYPEID (INHERITS TYPEID)? '{' (feature ';')* '}';

意思是 program 是一个 programBlocks 数组，其中每个 programBlocks 是 classDefine 后面接上分号，或者是 end-of-file。 而 classDefine 是类似于 class ClassName inherits SuperClass （可以没有inherits） { }; 的样子。

写这一部分的时候，参照着 COOL 语言的手册，它一般会给出这门语言 Backus-Naur 形式（BNF）的语法定义，如下图：

bnf of cool

把里面的 ::= 换成 :，再在每行的结尾加个分号一般就行了。但也要注意这些说明书里给出的排列顺序不一定靠谱，可能不会照顾实际使用情况，我在对 alrlr4 语法库的 pull request 里调整了好几处顺序。

除了语法，我们还需要定义语法里用到的 CLASS、TYPEID 是什么，这叫词法定义，COOL 的词法大概长这样：

// COOL.g4
// skip spaces, tabs, newlines, note that \v is not suppoted in antlr
WHITESPACE: [ \t\r\n\f]+ -> skip;

// comments
OPEN_COMMENT: '(*';
CLOSE_COMMENT: '*)';
COMMENT: OPEN_COMMENT (COMMENT|.)*? CLOSE_COMMENT -> channel(HIDDEN);
ONE_LINE_COMMENT: '--' .*? '\n' -> channel(HIDDEN);

// key words
CLASS: C L A S S;
ELSE: E L S E ;
FALSE: 'f' A L S E ;

fragment A: [aA];
fragment C: [cC];
fragment D: [dD];
fragment E: [eE];
fragment F: [fF];

用到的是前端常用的正则表达式，以及表示直接扔掉空格的 -> skip，还有将注释引流到别处以待它用的 -> channel(HIDDEN)。

fragment 则是我提交PR时评审者提出的改进建议，可以提升大小写不敏感关键字的可读性。

做 Antlr4 的语法描述基本不需要学习（当然你首先要会正则和 BNF），参照着语法库 里其他语言的定义就可以写出来。

不参考其他语言语法的话，字符串转义的部分可能会比较难写：

// COOL.g4
STRING: '"' (ESC | ~ ["\\])* '"';
fragment ESC: '\\' (["\\/bfnrt] | UNICODE);
fragment UNICODE: 'u' HEX HEX HEX HEX;
fragment HEX: [0-9a-fA-F];

语法部分和词法部分都一起放在 COOL.g4 里，文件名和文件第一行 grammar COOL; 是大小写一致的。

我写的完整定义提交在这里。

生成 JS 写的 Lexer 和 Parser

接着就可以用刚写的 COOL.g4 来生成我们要调用的 Lexer 和 Parser 了。

我使用 gulp 来做这事，先删掉生成文件夹，然后运行 antlr4，设置目标语言为 js，生成到 ./src/antlrGenerated 里，使用 COOL.g4 作为输入。

// gulpfile.js
gulp.task('build-compiler', async function() {
  await del('./src/antlrGenerated');
  execSync('java org.antlr.v4.Tool -Dlanguage=JavaScript -o ./src/antlrGenerated ./src/COOL.g4');
});

然后就可以做第二步了，得到函数 parseCOOL = (coolProgram: string) => AST，第三步就是用起来：

// index.js
import { flow } from 'lodash';
import { ParseTreeWalker } from 'antlr4/tree';

import GenerateJSListener from './GenerateJSListener'; // 遍历 AST 生成 JS 的类
import parseCOOL from './parseCOOL'; // 第二步得到的 parseCOOL = (coolProgram: string) => AST

export default function transformCOOL(cool: string) {
  return flow(
    parseCOOL,
    visitCOOL,
    generateJS
  )(cool);
}

function visitCOOL(ast) {
  const generateJSListener = new GenerateJSListener();
  const walker = new ParseTreeWalker();
  walker.walk(generateJSListener, ast);
  return generateJSListener;
}

function generateJS(generateJSListener) {
  return generateJSListener.generateJS();
}

遍历 AST

visitCOOL() 是关键的一步，我们使用 ParseTreeWalker() 遍历 COOL AST ，并在进入和离开每个 AST 节点时通知 GenerateJSListener，然后 GenerateJSListener 就能根据经过的 COOL AST 的信息创建出 JS AST。

这个类里我们写了三种函数：

// GenerateJSListener.js
export default class GenerateJSListener extends COOLListener {
  jsAST: JSASTBuilder = new JSASTBuilder();

  // 1
  @override
  exitFalse(context: COOLParser.FalseContext): void {
    this.jsAST.False();
  }

  @override
  exitTrue(context: COOLParser.TrueContext): void {
    this.jsAST.True();
  }

  // 2
  @override
  exitString(context: COOLParser.StringContext): void {
    this.jsAST.String(context.STRING().symbol.text);
  }

  // 3
  @override
  exitMethodCall(context: COOLParser.MethodCallContext): void {
    // shorthand for self.<id>(<expr>, ...)
    const functionName: string = context.OBJECTID().symbol.text;
    // console.log(context.TYPEID())
    const superClassName: ?string = context.TYPEID() ? context.TYPEID().symbol.text : null;
    const argumentLength: number = context.expression().length - 1; // there are one expression is the callee Object
    this.jsAST.MethodCall(functionName, argumentLength, superClassName);
  }

  generateJS(): string {
    const output: GeneratedOutput = generate(this.jsAST.jsProgramAST, {
      quotes: 'single',
      auxiliaryCommentBefore: ' @flow @ts-check ',
    });
    return output.code;
  }
}

它们调用了 JSASTBuilder 里的函数，JSASTBuilder 里包含一个栈（来自 ASTStack）和一些创建 IIEF 之类的 js 模板的函数（来自 ASTBuilder）。

// JSASTBuilder.js
class ASTStack {}
class ASTBuilder extends ASTStack {}
export default class JSASTBuilder extends ASTBuilder {}

创建 JS AST

上面遍历 COOL AST 时调用的创建 JS AST 的函数，第一种是直接创建 JS AST 节点，像这样：

// JSASTBuilder.js
  False(): void {
    // booleanLiteral, stringLiteral, and identifier are Expression
    this.push(t.booleanLiteral(false));
  }

  True(): void {
    this.push(t.booleanLiteral(true));
  }

第二种是用 COOL AST 中的信息来创建 JS AST：

// JSASTBuilder.js
  String(content: string): void {
    // use JSON.parse() to remove "" double quote
    this.push(t.stringLiteral(JSON.parse(content)));
  }

第三种是根据 COOL AST 中子节点的个数，拿出相应个数的 JS AST 子节点，拼在一个 JS AST 节点里：

// JSASTBuilder.js
  MethodCall(functionName: string, argumentLength: number, superClassName: ?string): void {
    // Invoke someObject.method()
    // superClassName currently unavailable
    const functionArguments = [...this.pop(argumentLength, true)];
    const calleeObject = this.pop(1);
    // if callee is something like (new A()) them it don't need this. , else do
    const buildMethodCall = t.isIdentifier(calleeObject)
      ? template(`this.CALLEE.FUNCTION()`)
      : template(`CALLEE.FUNCTION()`);

    const methodCall = buildMethodCall({
      CALLEE: calleeObject,
      FUNCTION: t.identifier(functionName)
    }).expression;

    methodCall.arguments = functionArguments;
    this.push(methodCall);
  }

当我们调用一个类函数时，我们要做到类似于填写模板字符串 this.${CALLEE}.${FUNCTION}()，其中 FUNCTION 可以看到是离开当前 COOL AST 节点时获取的，而 CALLEE 是我们之前放在栈里的。

使用栈保存 AST 子树、子节点

上文提到的 this.push() 意思便是将一个 JS AST 放入栈中，this.pop(1) 则是将一个子节点弹出栈。

pushpop

先一层层地把 true、false、if 语句、类函数通过 jsASTStack 创建起来，最终当我们遍历到 COOL AST 的根部时，我们将大功告成的 JS AST 放进jsProgramAST里，就可以用它生成 js 代码了。

// JSASTBuilder.js
class ASTStack {
  // We use stack to temporarly store subtree of AST, then you can use popFor() to load subtree in the stack into a container tree node
  jsASTStack: Array<JSASTNode> = [];
  // root of AST, last to finish
  jsProgramAST: JSASTNode = t.file(t.program([]));

  push(subAST: JSASTNode): void {
    this.jsASTStack.push(subAST);
  }

  pop(quentity: number, returnArray: boolean = false): JSASTNode | Array<JSASTNode> {
    if (this.jsASTStack.length < quentity) {
      throw new Error(
        `Poping too many sub-AST from JSASTStack, poping ${quentity} but stack with length ${
          this.jsASTStack.length
        } is:`,
        this.jsASTStack
      );
    }
    if (quentity !== 1) {
      const nodes = takeRight(this.jsASTStack, quentity);
      this.jsASTStack = dropRight(this.jsASTStack, quentity);
      return nodes;
    }
    return returnArray ? [this.jsASTStack.pop()] : this.jsASTStack.pop();
  }
}

除了使用栈自底向上地构建以外，还有从 AST 根部开始自顶向下地构建，我本以为使用 babel-traverse 可以做到这一点，并一开始采用了这个方案，但它明显只考虑到了做 AST 变换的用途，所以不会递归地给出 parentPath （babel 用于遍历 AST 的一个双向链表），只给出有限的几层，非常难用，又难读，所以我最终采用了栈的方案。

用 babel types 创建 JS AST

创建 JS AST 的四种写法（。）分别是

  1. 手写 POJO 的 AST，写到地老天荒，最终还得自己遍历 AST 生成代码，导致只有 10% 的精力集中在业务上
  2. 使用 EStree 来构建，这是 Acorn 所用的 AST 类，然而我怀疑它不但不支持 flowtype，恐怕 ES6 都支持不全（偏见）
  3. 使用 babel-types，它提供了从类型标注到 JSX 的各种各样的 AST 节点，供你手工创建现代 JS 的 AST
  4. 使用 babel-template，模板填充，对于创建 IIEF 这种多层的 AST 很方便，减少手工，提升可读性

因此我同时使用 babel-types 和 babel-template，先用 babel-template 创建出大坨的 AST，再用 babel-types 创建节点，插入大坨中。

例如这个创建 IIEF 的过程，就是先创建出一个空白的 IIEF，再用子 AST 替换掉 null：

// JSASTBuilder.js
import * as t from 'babel-types';
import template from 'babel-template';

class ASTBuilder extends ASTStack {
  // ...
  static iief(ast: any, functionName: string, statementInsertBefore: ?Array<JSASTNode>): JSASTNode {
    // 1. if it is a expression, which in JS is a IIEF, or it's a function call
    const buildIIEF = template(`
      (function ${functionName}() {return null}.bind(this)())
    `);
    const IIEF = buildIIEF({}).expression;

    // ...

    if (t.isExpression(ast)) {
      // 3.1 set return value
      IIEF.callee.callee.object.body.body[0].argument = ast;
    } else {
      // 3.2 if it is a statement
      IIEF.callee.callee.object.body.body = [ast];
    }

    if (statementInsertBefore) {
      IIEF.callee.callee.object.body.body = [...statementInsertBefore, ...IIEF.callee.callee.object.body.body];
    }
    return IIEF;
  }
}

FlowType 中类型标注是 foo: Type 的形式，其中的冒号是 t.typeAnnotation()，而冒号后的类型才是 t.xxxTypeAnnotation()，实践表明不加冒号的话，构建出的 AST 也能生成 JS 代码，而且会看起来不明觉厉。以下是加冒号的过程：

// JSASTBuilder.js
class ASTBuilder extends ASTStack {
  // ...
  static typeAnnotation(typeName: string): JSASTNode {
    switch (typeName) {
      case 'Int':
        return t.typeAnnotation(t.numberTypeAnnotation());
      case 'Bool':
        return t.typeAnnotation(t.booleanTypeAnnotation());
      case 'String':
        return t.typeAnnotation(t.stringTypeAnnotation());
      default:
        return t.typeAnnotation(t.identifier(typeName));
    }
  }
}

从 AST 生成 JS 代码

最后我们使用 babel-generator 来生成代码，作为生产级的工具，它有极高的速度。

// JSASTBuilder.js
class GenerateJSListener extends COOLListener {
  // ...
  generateJS(): string {
    const output: GeneratedOutput = generate(this.jsAST.jsProgramAST, {
      quotes: 'single',
      auxiliaryCommentBefore: ' @flow @ts-check ',
    });
    return output.code;
  }
}

配置里，我们使用单引号，quotes: 'single'，不过这个无所谓，毕竟样式如何还不就是一句 eslint --fix 的事情嘛。

还有为了代码的可读性，我们在生成的代码的顶端加上 @flow @ts-check，以便编辑器提供 FlowType 或 Typescript 的 Intellisense。

runtime lib

为了让生成的代码可运行，我们还有几件事要做，第一是要提供 COOL 语言内置的功能，我通过在生成代码顶端加入相应类的形式提供它们：

// JSASTBuilder.js Program()

// 1. put runtime on the front
const runtimeBuilder = template(
  `
  class IO {
    out_string(content: ?string): void {
      return content ? console.log(content) : console.log();
    }
  }
`,
  {
    plugins: ['flow'],
  }
);
this.jsProgramAST.program.body.unshift(runtimeBuilder({}));

当 COOL 支持多文件 import 了，我们就必须学习 babel-plugin-transform-runtime ，将 runtime 合并起来，而每个文件上方只保留对它们的引用。

运行代码

由于我们使用了 flowtype，运行生成的文件就必须用：

node -r \"./node_modules/babel-core/register\" -r \"./node_modules/babel-polyfill/lib/index.js\" ./src/index.js

要不就是在生成之前用 babel-plugin-flow-stripe-type 和 babel-preset-stage-2、babel-preset-es2015 之类的 preset 过一下。

结语

将 COOL 转换为 JS 的过程很有趣，这是我第一次尝试从底层用 babel，而不是仅仅用 webpack loader 调用它。

参考

项目地址：github