俺のaltjsがこんなに簡単にpegjsで作れるわけがない #JavaScript

この記事は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が使えるかどうかとか、試してないのでわからん）。

俺のaltjsがこんなに簡単にpegjsで作れるわけがない