搞一门编译到JS语言

本文主要讲述如何使用 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;
}

第一步稍微复杂一点,就是我们怎么得到上面的 COOLLexerCOOLParser 的?

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 里调整了好几处顺序。

除了语法,我们还需要定义语法里用到的 CLASSTYPEID 是什么,这叫词法定义,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-typebabel-preset-stage-2babel-preset-es2015 之类的 preset 过一下。

结语

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

参考

项目地址:github