Subscribed unsubscribe Subscribe Subscribe

枕を欹てて聴く

香炉峰の雪は簾を撥げて看る

How to write JS code generator

f:id:Constellation:20120202003445p:image

esprimaに入りました. 次のversionからesprima.generateで利用可能です. Issue 89 - esprima - Code generator: convert AST to source code - ECMAScript parsing infrastructure for multipurpose analysis - Google Project Hosting


JSのpretty printerを作りました. ECMAScriptのparserとしてesprimaを使っていて, 自作のcode generatorがASTから綺麗なJSをprintします.
で, 現在はesprima code baseに持って行こうとしています. 将来的にesprimaで使えるようになる予定なので, 使いたい!! という方はお待ちください.

operator precedence

ASTではparenthesisの情報が落ちています. もちろん, 全て括弧で囲めば評価順序は問題ないわけですから,

((((((1 + 1) + 1) + 1) + 1) + 1) + 1)

とprintすれば, 別段問題はないわけです. しかし, これはprettyですか? いやいやご冗談を...

つまり, 端的には

(1 + 2) * 3

はこのまま残すけれども,

1 + (2 * 3)

1 + 2 * 3

としたいわけです. はたしてどうするのか?

前提, precedence

parserではこのような優先順位の異なる結合をうまく扱う方法として, operator precedence parserが存在します.

では, code generatorはこれの逆をやればいいわけです.
precedenceは結合優先度が高ければ高いexprほど高くなります. つまり, LogicalOR < LogicalAND < ... < Additive < Multiplicative < Unary < ... < Primaryという風にです.
いま, 現在のgeneratorのprecedenceというものを設定します. これは現在generatorがどのprecedenceを最低レベルとしているかというもので, generatorはこれより低いprecedenceを持つoperatorのexprを出力するには括弧で囲む必要があります.

実例1
1 + (2 * 3)

という形のASTが与えられたとします. これからpretty-printを行いましょう.
すると, まずは最低のprecedence, Sequential(コンマ区切りのもの. expr, expr, expr)をgeneratorに設定してgenerateします. このexprはAdditiveなので, Sequentialよりも高いprecedenceです. よってこのexpr全体には括弧がいりません.

次にlhsの1です. AdditiveExpressionは

AdditiveExpression + MultiplicativeExpression

ですから, こちらはAdditiveのprecedenceでgenerateします. すると1はPrimaryExpression(というかNumericLiteral)です. これは最高precendenceなので気にすることなく1を出力します(括弧なし)

rhsの(2 * 3)です. 上のBNFより, Multiplicativeのprecedenceでgenerateします. すると対象は*でMultiplicativeですから, MultiplicativeとMultiplicativeなのでより低いということはありません. よって括弧なしでgenerateします.

この結果,

1 + 2 * 3

を得ることができます.

実例2
1 * (2 + 3)

次にという形のASTが与えられたとします.
すると, まずは最低のprecedence, Sequentialをgeneratorに設定してgenerateします. このexprはMultiplicativeなので, Sequentialよりも高いprecedenceです. よってこのexpr全体には括弧がいりません.

次にlhsの1です. MultiplicativeExpressionは

MultiplicativeExpression * UnaryExpression

ですから, こちらはMultiplicativeのprecedenceでgenerateします. するとPrimaryなので, 括弧なしで1を取り出します.

問題はrhsの(2 + 3)です. 上のBNFより, Unaryのprecedenceでgenerateします. すると対象は+でAdditiveですから, Unaryよりも低いprecedenceなわけです. そこでgeneratorはすかさず括弧でこのexprを囲みます!!! (2 + 3)

この結果,

1 * (2 + 3)

を得ることができます. よかった!!

blockとelse-ifの連結

非常に簡単なことに, 基本的にはstatementをとるstatementではひとつindentを下げるというそれだけの規則でうまく行きます.

if (cond)
    print("HELLO");

のようにです. ただし, ここでたった2つだけ例外を考慮することで, 綺麗なcodeを出力できます.

blockは全体のstatementにくっつく

blockは前のstatementにくっつきます. つまり,

if (cond)
    {
        print("HELLO");
    }

という風にblock自体がstatementとしてindentが下がるのではなく, if (cond)にくっついて,

if (cond) {
    print("HELLO");
}

となります. FunctionExpressionやらdo-whileやら, blcokらしきものを所持する可能性があるstatement, expressionでこのcheckを行うことで, 綺麗なcodeを出力できます.

else-ifはくっつく

今のままでは

if (cond) {
    print("HELLO");
} else
    if (cond2) {
    }

となってしまいます. else-ifでセットになっているのではなく, あれは単にelse statementのstatementにif文を突っ込んでいるだけであるためです. このため, elseが存在するとき, そのstatementがif文であったときにはelseに吸い付くようにします. すると,

if (cond) {
    print("HELLO");
} else if (cond2) {
}

となります. 綺麗!

まとめ

pretty-printerは思いの外simpleな規則で綺麗に実装できました.