仓库源文，站点原文

layout: post title: '搞一门编译到JS语言' date: 2017-05-26 16:37:19 +0800 image: 'blog-author.jpg' description: '简述快速实现将外语编译到JS的一种思路' main-class: 'frontend' color: '#66CCFF' tags:

• babel
• AST
• flowtype
• compiler categories: Journal twitter_text: introduction: '将一门语言解析为 AST，遍历它自底向上构建 JS 的 AST，并生成 flowtyped ES6'

本文主要讲述如何使用 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）的语法定义，如下图：

把里面的 ::= 换成 :，再在每行的结尾加个分号一般就行了。但也要注意这些说明书里给出的排列顺序不一定靠谱，可能不会照顾实际使用情况，我在对 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) 则是将一个子节点弹出栈。

先一层层地把 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 调用它。

• JS 能操作自己的 AST，并不意味着它能做方便的元编程，毕竟含有 eval() 的函数是没法被优化的（存疑）。
• Antlr4 快速而简约的体验，让它有机会成为一个常用的工具，搞 GraphQL 转 OpenCypher、Evernote 转 itonnote 都可以考虑它。
• 看待数据格式可以更加民主，毕竟不管格式设计者的世界观如何，只要格式能用上下文无关文法描述，我都能提取出我想要的数据。
• 希望有人开发出更方便的工具，我初学到完工花了 5 人天，但其中设计方案、一个个适配语法等重复劳动（可能和开源社区别人的劳动重复）就花掉了 4 人天，如果有小白工具能一天搞定就好了。
• babel 是友好的，虽然我个人在后端项目中会选用 Typescript，但当我想做编译到 JS （带类型标注）时，只有 babel 站了出来……

参考

• songfu
• antlr-ts 使用经验（过时的）
• antlr4 使用经验
• antlr4 小教程
• JSON.g4 example
• 剖析 Babel——Babel 总览
• babel-types at npm
• babel-types usage at its test
• babel-template at npm
• Babel Plugin Handbook
• Understanding ASTs by Building Your Own Babel Plugin（illustrating ES AST）
• COOL manual
• AST explorer(learn how AST form, expecally flowtype)

项目地址：github