tokuhirom's Blog

Const なんとかさん関連のツール群をつかうと、簡単に EcmaScript target の言語をつくれる!

Const なんとかさん関連のツール群というのは以下のようなものです

esprimaEcmaScript から AST を生成する
escodegenAST から EcmaScript を生成する
esmangleAST を最適化したり mangling したりする

で、esprima とか関連のツール群は Mozilla の Parser API の AST 形式をサポートしています。詳細はここのへんかな。 https://developer.mozilla.org/en-US/docs/SpiderMonkey/Parser_API

で、escodegen があるということは Parser API 形式の AST をはけば、そこから JS を生成できるってことですね。しかも escodegen は source-map の生成にも対応しているので、エラーの処理もらくちんで、実行時エラーがおきても、「ああ、JSでかいておけばよかった。。」とはならない(という未来がくることになっています)

CoffeeScriptRedux というカッフィースクリプトのあたらし版をつくってるプロジェクトでは実際に

CoffeeScript code => [parser] => CoffeeScript AST (CSAST) => JS AST (Parser API AST) => [esmangle] => Compressed JS AST => [escodegen] => JS code

という処理がおこなわれています。


。。。ということをConst なんとかさんと kyo さんが話してるのをみて、CoffeeScriptRedux の存在をしった僕は、おなじようなことをためしてみようとおもったのでした。

さて、実際これをためしてみるにあたって、とりあえず lisp でも実装しよう、とおもいいたるわけですが、多機能なものをつくってもしょうがないんで、とりあえず数値の加減乗除ができるものをつくってみましょう。

スキャナをこういう風にかきまして、ソースコードをトークンにぶっかく。

/*jshint node:true, laxcomma:true, loopfunc:true */
(function () {

"use strict";

var assert = require('assert');

var TOKENS = {
     TOKEN_LPAREN: 1
   , TOKEN_RPAREN: 2
   , TOKEN_NUMBER: 3
   , TOKEN_ADD:    4
};

function Scanner(src) {
    this.src = src;
    this.lineno = 1;
    this.col    = 1;
}
Object.keys(TOKENS).forEach(function (key) {
    Scanner[key] = TOKENS[key];
});
Scanner.prototype.scan = function () {
    var tokens = [];
    while (this.src.length > 0) {
        var token = this._scan();
        if (token) {
            tokens.push(token);
        } else {
            break;
        }
    }
    return tokens;
};

Scanner.prototype._scan = function () {
    this._skipWS();
    if (this.src.length===0) { return; }

    switch (this.src[0]) {
    case '(':
    case ')':
    case '+':
    case '*':
    case '-':
    case '/':
        var c = this.src[0];
        this.src = this.src.substr(1);
        return [c, this.lineno, this.col, this.lineno, ++(this.col)];
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':
        var m = this.src.match(/^(0|[1-9][0-9]*(\.[0-9]+)?)/);
        if (m) {
            var startCol = this.col;
            this.col += m[0].length;
            this.src = this.src.substr(m[0].length);
            return [parseInt(m[0], 10), this.lineno, startCol, this.lineno, this.col];
        }
    }
    throw "Unknown token: " + JSON.stringify(this.src);
};
Scanner.prototype._skipWS = function () {
    var replaced = true;
    while (replaced) {
        replaced = false;
        this.src = this.src.replace(/^[ ]+/, (function (a) {
            replaced = true;
            this.col += a.length;
            return '';
        }).bind(this));
        this.src = this.src.replace(/^\n/, (function () {
            replaced = true;
            this.lineno++;
            this.col = 1;
            return '';
        }).bind(this));
    }
};

module.exports = Scanner;

}).call(this);

パーサをこういう風にかきまして、トークンを AST にくみたてやしょう。

/*jshint node:true, laxcomma:true */
(function () {
"use strict";

var Scanner = require('./scanner.js');
var TK_TAG = 0;

function Parser(tokens) {
    this.tokens = tokens;
}
Parser.prototype.parse = function () {
    return this.parseSexps();
};
Parser.prototype.lookToken = function () {
    return this.tokens[0];
};
Parser.prototype.getToken = function () {
    return this.tokens.shift();
};
Parser.prototype.parseSexps = function () {
    var ret = [];
    while (this.tokens.length > 0) {
        var sexp = this.parseSexp();
        ret.push(sexp);
    }
    return ret;
};
Parser.prototype.parseSexp = function () {
    var token = this.getToken();
    if (token[TK_TAG] !== '(') {
        throw 'left paren is expected';
    }

    var ret = [];
    while (this.tokens.length > 0) {
        if (this.lookToken()[TK_TAG] === ')') {
            this.getToken();
            return ret;
        } else if (this.lookToken()[TK_TAG] === '(') {
            ret.push(this.parseSexp());
        } else {
            ret.push(this.parseAtom());
        }
    }
    throw 'Unbalanced parens in S-expression.';
};
Parser.prototype.parseAtom = function () {
    return this.getToken();
};

module.exports = Parser;

}).call(this);

で、普通につくった lisp の AST を Parser AST に変換する。

(function () {
    /*
> JSON.stringify(require('esprima').parse('3+5'))
'{"type":"Program","body":[{"type":"ExpressionStatement","expression":{"type":"BinaryExpression","operator":"+","left":{"type":"Literal","value":3},"right":{"type":"Literal","value":5}}}]}'
> JSON.stringify(require('esprima').parse('3+5; 4+2'))
'{"type":"Program","body":[{"type":"ExpressionStatement","expression":{"type":"BinaryExpression","operator":"+","left":{"type":"Literal","value":3},"right":{"type":"Literal","value":5}}},{"type":"ExpressionStatement","expression":{"type":"BinaryExpression","operator":"+","left":{"type":"Literal","value":4},"right":{"type":"Literal","value":2}}}]}'
> JSON.stringify(require('esprima').parse('3+5+8'))
'{"type":"Program","body":[{"type":"ExpressionStatement","expression":{"type":"BinaryExpression","operator":"+","left":{"type":"BinaryExpression","operator":"+","left":{"type":"Literal","value":3},"right":{"type":"Literal","value":5}},"right":{"type":"Literal","value":8}}}]}'
> JSON.stringify(require('esprima').parse('[1,2,3].reduce(opPlus)'))
'{"type":"Program","body":[{"type":"ExpressionStatement","expression":{"type":"CallExpression","callee":{"type":"MemberExpression","computed":false,"object":{"type":"ArrayExpression","elements":[{"type":"Literal","value":1},{"type":"Literal","value":2},{"type":"Literal","value":3}]},"property":{"type":"Identifier","name":"reduce"}},"arguments":[{"type":"Identifier","name":"opPlus"}]}}]}'
    */

function JSASTConverter(ast) {
    this.ast = ast;
}
JSASTConverter.prototype.translate = function () {
    var body = [];
    for (var i=0, l=this.ast.length; i<l; i++) {
        body.push({
            type: 'ExpressionStatement',
            expression: this._translate(this.ast[i])
        });
    }
    return {
        'type': 'Program',
        'body': body
    };
};
JSASTConverter.prototype._translate = function (ast) {
    if (ast[0][0] === '+') {
        return this._generateOperatorAST(ast, 'TINYLISP$$opAdd');
    } else if (ast[0][0] === '-') {
        return this._generateOperatorAST(ast, 'TINYLISP$$opSub');
    } else if (ast[0][0] === '*') {
        return this._generateOperatorAST(ast, 'TINYLISP$$opMul');
    } else if (ast[0][0] === '/') {
        return this._generateOperatorAST(ast, 'TINYLISP$$opDiv');
    } else if (typeof(ast[0]) === 'number') {
        return {
            "type":"Literal",
            "loc": {
                "start": {
                    "line": ast[1],
                    "column": ast[2]
                },
                "end": {
                    "line": ast[3],
                    "column": ast[4]
                }
            },
            "value":ast[0]
        };
    } else {
        console.log(ast);
        throw "Unknown expression.";
    }
};
JSASTConverter.prototype._generateOperatorAST = function (ast, func) {
    var op = ast.shift();
    return {
        'type': 'CallExpression',
        "loc": {
            "start": {
                "line": op[1],
                "column": op[2]
            },
            "end": {
                "line": op[3],
                "column": op[4]
            }
        },
        'callee': {
            'type': 'MemberExpression',
            'computed': false,
            'object': {
                'type': 'ArrayExpression',
                'elements': ast.map((function (t) {
                    return this._translate(t);
                }).bind(this))
            },
            'property': {
                type: 'Identifier',
                name: 'reduce'
            }
        },
        'arguments': [
            {
                type: 'Identifier',
                name: func
            }
        ]
    };
};
module.exports = JSASTConverter;

}).call(this);

で、できた JS の AST を escodegen で変換します。

(function () {
var escodegen = require('escodegen'),
    esmangle = require('esmangle'),
    fs = require('fs');

var runtime = fs.readFileSync(__dirname + "/runtime.js", 'utf-8');

var passes = [
    // remove unused label
    esmangle.require('lib/pass/remove-unused-label'),

    // remove empty statement
    esmangle.require('lib/pass/remove-empty-statement'),

    // remove wasted blocks
    esmangle.require('lib/pass/remove-wasted-blocks'),

    // transform to sequence expression
    esmangle.require('lib/pass/transform-to-sequence-expression'),

    // transform branch to expression
    esmangle.require('lib/pass/transform-branch-to-expression'),

    // reduce branch jump
    esmangle.require('lib/pass/reduce-branch-jump')
];

function Generator(jsast, filename) {
    this.jsast    = jsast;
    this.filename = filename || '-e';
}
Generator.prototype.generate = function() {
    var optimized = esmangle.optimize(this.jsast, passes);
    var mangled = esmangle.mangle(optimized);
    var src = escodegen.generate(
        mangled
    );
    var srcMap =  escodegen.generate(
        mangled, {
            sourceMap: this.filename
        }
    );
    return [runtime + src, srcMap];
};

module.exports = Generator;

}).call(this);

で、これらをまとめるやつをぶっこむ。

/*jshint evil:true, node: true */
"use strict";

var fs = require('fs');

var Scanner        = require('./src/scanner.js');
var Parser         = require('./src/parser.js');
var JSASTConverter = require('./src/js-ast-converter.js');
var Generator      = require('./src/generator.js');

function evaluate(src, filename) {
    var scanner = new Scanner(src);
    var tokens = scanner.scan();
    var parser = new Parser(tokens);
    var ast = parser.parse();
    var converter = new JSASTConverter(ast);
    var jsast = converter.translate();
    var generator = new Generator(jsast, filename);
    var jssrc = generator.generate();
    return eval(jssrc[0]);
}

function loadFile(filename) {
    var src = fs.readFileSync(filename, 'utf-8');
    return evaluate(src, filename);
}

module.exports = {
    Scanner: Scanner,
    Parser: Parser,
    JSASTConverter: JSASTConverter,
    Generator: Generator,
    loadFile: loadFile,
    evaluate: evaluate
};

とまあ。こういうかんじですね。


たとえば、以下のようなコードは

(+ 1 2 3)

スキャナにかけると以下のようになりましょう。トークンのはじまりとおわりを記録しているのがポイントです。これやっておくことによって source map がつくれるという算段ですね。

[ [ '(', 1, 1, 1, 2 ],
  [ '+', 1, 2, 1, 3 ],
  [ 1, 1, 4, 1, 5 ],
  [ 2, 1, 6, 1, 7 ],
  [ 3, 1, 8, 1, 9 ],
  [ ')', 1, 9, 1, 10 ] ]

で、これをパーサでやっつける。

[ [ [ '+', 1, 2, 1, 3 ],
    [ 1, 1, 4, 1, 5 ],
    [ 2, 1, 6, 1, 7 ],
    [ 3, 1, 8, 1, 9 ] ] ]

で、これを JS の AST 形式に変換します。

{
 "type": "Program",
 "body": [
  {
   "type": "ExpressionStatement",
   "expression": {
    "type": "CallExpression",
    "loc": {
     "start": {
      "line": 1,
      "column": 2
     },
     "end": {
      "line": 1,
      "column": 3
     }
    },
    "callee": {
     "type": "MemberExpression",
     "computed": false,
     "object": {
      "type": "ArrayExpression",
      "elements": [
       {
        "type": "Literal",
        "loc": {
         "start": {
          "line": 1,
          "column": 4
         },
         "end": {
          "line": 1,
          "column": 5
         }
        },
        "value": 1
       },
       {
        "type": "Literal",
        "loc": {
         "start": {
          "line": 1,
          "column": 6
         },
         "end": {
          "line": 1,
          "column": 7
         }
        },
        "value": 2
       },
       {
        "type": "Literal",
        "loc": {
         "start": {
          "line": 1,
          "column": 8
         },
         "end": {
          "line": 1,
          "column": 9
         }
        },
        "value": 3
       }
      ]
     },
     "property": {
      "type": "Identifier",
      "name": "reduce"
     }
    },
    "arguments": [
     {
      "type": "Identifier",
      "name": "TINYLISP$$opAdd"
     }
    ]
   }
  }
 ]
}

で、これを escodegen にかけると

function TINYLISP$$opAdd(a,b) {
    return a+b;
}
function TINYLISP$$opSub(a,b) {
    return a-b;
}
function TINYLISP$$opMul(a,b) {
    return a*b;
}
function TINYLISP$$opDiv(a,b) {
    return a/b;
}
[
    1,
    2,
    3
].reduce(TINYLISP$$opAdd);

となる。要は S 式の還元は、単純な式では Array.prototype.reduce で処理できるんでそういう風にいたしております。


で、やってみた感想としては、JS を文字列で生成してくれた方が楽は楽ですな。Parser API AST の生成はなかなかに面倒だ。

ただ、ソースマップの生成までふくめると escodegen つかった方が楽かもしれぬ。ソースマップの生成は面倒ですからな。
また、JS の Parser API AST にしておくと、esmangle とかつかって最適化したりというようなこともできるというメリットがある。