この記事はJavaScript Advent Calender 2014の10日目の記事です。
altjs作りたいやろ
半年前にこんなLTをやった。未完成で放置するのは気持ち悪いので、この機会に完成させようと思った…んだけど、advent当日の時点でまだ完成してない。すまんな。ただ知見は多少溜まったので、基本的なaltjsの作り方と合わせて紹介しようと思う。
altjsってどうやって作んの？
方法は様々だけど、
- 文法をPEG(pegjs)で記述する
- ソースコードを、Parser APIで定義されるASTに変換するロジックを書く
- 変換されたASTを、escodegenでJavaScriptのコードにさらに変換する
というのが今ならやりやすいと思う。結局ある構文をjsに変換するだけで、変換は既存のツールを使えるので、実はそんなに広い知識を要求せず、0から王道のコンパイラを作るみたいな壮大な話にはならない。
まずはASTを知る
ASTとはパースされたコードを木として表したもの。抽象構文木(Abstract Syntax Tree)。
JavaScriptにおいてはMozillaが提唱するParser APIによる定義が有名で、Parser APIに従うと、例えば次のコードは、
var hoge = 1;
このようなオブジェクトとして表される。一般的にjsのオブジェクトとして扱うことが多いので、この記事ではjsonで示す。
{
"type": "Program",
"body": [
{
"type": "VariableDeclaration",
"declarations": [
{
"type": "VariableDeclarator",
"id": {
"type": "Identifier",
"name": "hoge"
},
"init": {
"type": "Literal",
"value": 1,
"raw": "1"
}
}
],
"kind": "var"
}
]
}
jsのコードをこのASTに変換できるということは、その逆も可能と言うことだ。つまりaltjsを作りたければ、自分が望む文法のコードをパースして、validなASTを生成する仕組みを作ればいい。今回はそれを作るという話。なお、jsをASTに変換するツールの代表がesprimaで、ASTをjsに変換する対になるツールがescodegenである。
参考: JavaScript AST Walker - JavaScript ASTを見て回る
PEGを書く
PEGとは、ある構文を解析する規則を記述するための形式化されたルール、と言えばいいのだろうか。自分でも何を言ってるのかよく分からない。なので次の例を見て欲しい。
hoge = "foo" " " [0-9]+ " " "bar"
PEGはこのように、規則名 = 規則として表される。このようなPEGがある場合、この規則hogeは、foo、空白、1つ以上の任意の数字、空白、barの順で並んだ文字列が入力されることを期待している。つまり、foo 123 barという文字列の入力は先のPEGに対してvalidである。foo x01 fugaはinvalidである。
BNFを知っているなら、まあ多少堅めのBNFだと理解すればいいと思う。この定義は階層化できるので、言語を作るとするなら、最終的には例えば以下のような定義ができあがる（以下はpegjsのexamplesのjavascriptパーサから引用して簡略化したもの。__は空白を示している）。
IfStatement
= IfToken __ "(" __ Expression __ ")" __
Statement __
ElseToken __
Statement
PEG(pegjs)の具体的な文法については、こちらを参照して欲しい。
PEGでマッチしたコードをASTに変換するロジックを書く
欲しいASTを把握し、文法をPEGで定義できたら、次はそのASTを吐く仕組みを作る。js -> ASTがesprimaで、AST -> jsがescodegenだと言ったが、altjsのコード -> ASTを担当するのがpegjsである（あくまでaltjs作りにおいては）。pegjsはPEGにより構文解析を行いつつ、マッチしたときに任意の値を出力するコードを書くことができる。それを利用してASTを生成する。
では例えば、
a equals b
というaltjsが、
a == b
というjsに変換されてほしいとする。この場合、次のようなpegjsコードを書けば良い。
start = left:[a-z]+ " " "equals" " " right:[a-z]+ {
return {
"type": "ExpressionStatement",
"expression": {
"type": "BinaryExpression",
"operator": "==",
"left": {
"type": "Identifier",
"name": left.join('')
},
"right": {
"type": "Identifier",
"name": right.join('')
}
}
}
}
この{}で囲まれたブロックをpegjsではactionと呼び、任意のjsを書くことができる。そして、ここでreturnしたものがパースの出力となり、より上位の定義へ渡されていき、最終的なpegjsの出力となる。
今回はベタ書きしたが、initializerと呼ばれるどこの定義からでも呼べるjsのコンテキスト領域があり、そこにAST構築のためのヘルパー的なメソッドを定義して、actionからそのヘルパーを呼んでASTを返すというのが一般的なやり方のようだ。
詳しくは、pegjsのexamplesを読んで欲しい。
成果物: basic.js
なるべくミニマムかつ明示された仕様で、他の人がやってないものやりてえな〜？と思って探してみて、Minimal BASICという仕様が見つかったのでそれをaltjs化した。
とはいえ変数代入とGOTOとIFができた程度で、まだ全然仕様を網羅していない。失敗したのは、BASICが行数単位でコンテキストが変わっていくという、まあモダンな言語では採用されていない仕組みだったこと。これをjsで実現するために、行に対応したfunctionを逐一生成して番号を振り、それを若い順から実行するみたいなメタな仕組みを導入している。
Minimalとは言えかなり時間掛かっているので、とりあえずpegやってみようみたいな人は、やっぱり王道のLisp実装とかから始めるのが良さそうに思う。機能拡張も少しづつ段階的にできそうだし。
知見
まずesprimaにコードを突っ込むじゃろ？
僕たちが最終的に欲しいのはjsのコードで、まずはそのコードがどういうASTで表されるかというのを知る必要がある。でも、Parser APIの仕様を熟読して自分でASTを書くなんてのは現実的じゃない。そこで、まずは欲しいjsを↑で説明したesprimaというjsからASTに変換するツールに突っ込んで、ASTを吐かせる。
esprimaのページにオンラインパーサがあるので、僕はそれを使ってる。
BNFをそのまま写経すると失敗する場合がある
言語の仕様を読むと、構文はBNF（の派生）で定義されていることが多い。BNFとPEGは共通点が多いので、とりあえずBNFっぽくPEGを書いてみるというところから始めることができる。
ただ、部分的にはPEGに合わせて書き直す必要がある。例えばPEGは左側からマッチを試みて、一度マッチしたら確定してしまう。ので、例えば次のようなPEGに"abc"を食わせた場合、"abc"はマッチしない（"ab"がマッチする）。
hoge = "a" "b" / "a" "b" "c"
PEGで"ab"と"abc"の両方を認識させたければ、例えば次のようにする必要がある。
hoge = "a" "b" "c" / "a" "b"
BNFによる構文の記述は、ここらへんは考慮されない（する必要がないはず）ので、惰性でBNFからPEGに書き直しているとハマることがある。あと左再帰で無限ループとかにも注意。
参考: http://ponjbogri.github.io/cll-ja/ PEGについての簡単な説明
TypeError: Cannot read property 'type' of null
pegjsを書き始めると頻出すると思うんだけど、これはあるべき所にStatement、Expression、Identifierが無いときに発生する。なぜかというと、typeというプロパティがParser APIの定義上殆どの場合付属するものだから。なので、PEGのパースは成功しているんだけど、AST的にinvalidな構造を作ってしまっているという時にこのエラーが出る事が多い。
esvalidで大まかな問題箇所を把握する
しかし、Cannot read property 'type'が出たとして、escodegenはPEGのどこに問題があるかを教えてはくれない。それはそうだ。ASTには対応するPEGの情報が含まれてないのだから。
そこで、esvalidを使ってより詳細な情報を手に入れる。僕はこういうコードをinitializerに書いている（coffeeですまん）。
unless esvalid.isValid ast
_.each (esvalid.errors ast), (error) ->
console.error "error: ".red + error.message
console.error "error: ".red + prettyjson.render(error.node)
console.error "\r"
詳しくはesvalidのREADMEを読んで欲しい。補足すると、prettyjsonはjsonを綺麗に表示してくれるライブラリ。
そうすると、こんな感じで表示してくれる。
ただし必ずしも問題箇所の特定に役に立つわけじゃないので、そういう時はまあ地道にテスト用のaltjsを書いたりするしかない…
initializerからコードを分離する
1枚のモノリシックなpegjsのコードだけで何かを作ろうとすると、エラーが補足し辛いしテストも書きにくい。我々がロジックを書くのはaction内か、全ての規則とコンテキストがつながったinitializerと呼ばれる領域である。
幸いinitializerの中ではrequireが使えるので、僕はASTを作るためのコードを普通のjsとして分離している（クライアントサイドで使う時はどうすりゃいいんだろうか。browserifyが使えるかどうかとか、試してないのでわからん）。