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

この記事は[JavaScript Advent Calender 2014](http://qiita.com/advent-calendar/2014/javascript)の10日目の記事です。

## altjs作りたいやろ

https://speakerdeck.com/hdemon/basic-dot-jswozuo-routositeruhua

半年前にこんなLTをやった。未完成で放置するのは気持ち悪いので、この機会に完成させようと思った…んだけど、advent当日の時点でまだ完成してない。すまんな。ただ知見は多少溜まったので、基本的なaltjsの作り方と合わせて紹介しようと思う。

## altjsってどうやって作んの？

方法は様々だけど、

* 文法をPEG(pegjs)で記述する
* ソースコードを、Parser APIで定義されるASTに変換するロジックを書く
* 変換されたASTを、escodegenでJavaScriptのコードにさらに変換する

というのが今ならやりやすいと思う。結局ある構文をjsに変換するだけで、変換は既存のツールを使えるので、実はそんなに広い知識を要求せず、0から王道のコンパイラを作るみたいな壮大な話にはならない。

### まずはASTを知る

ASTとはパースされたコードを木として表したもの。抽象構文木(Abstract Syntax Tree)。
JavaScriptにおいてはMozillaが提唱する[Parser API](https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Parser_API#Expressions)による定義が有名で、Parser APIに従うと、例えば次のコードは、

```js
var hoge = 1;
```

このようなオブジェクトとして表される。一般的にjsのオブジェクトとして扱うことが多いので、この記事ではjsonで示す。

```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](http://esprima.org/)で、ASTをjsに変換する対になるツールが[escodegen](https://github.com/estools/escodegen)である。

参考: [JavaScript AST Walker - JavaScript ASTを見て回る](http://azu.github.io/slide/tkbjs/js-ast-walker.html)

### 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)の具体的な文法については、[こちら](http://pegjs.majda.cz/documentation#grammar-syntax-and-semantics)を参照して欲しい。

### 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コードを書けば良い。

```js

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](https://github.com/pegjs/pegjs/tree/master/examples)を読んで欲しい。

## 成果物: basic.js

https://github.com/hdemon/basic.js

なるべくミニマムかつ明示された仕様で、他の人がやってないものやりてえな〜？と思って探してみて、[Minimal BASIC](http://sourceforge.net/p/buraphakit/MinimalBASIC/ci/default/tree/ECMA-55.TXT)という仕様が見つかったのでそれをaltjs化した。

とはいえ変数代入とGOTOとIFができた程度で、まだ全然仕様を網羅していない。失敗したのは、BASICが行数単位でコンテキストが変わっていくという、まあモダンな言語では採用されていない仕組みだったこと。これをjsで実現するために、行に対応したfunctionを逐一生成して番号を振り、それを若い順から実行するみたいなメタな仕組みを導入している。

Minimalとは言えかなり時間掛かっているので、とりあえずpegやってみようみたいな人は、やっぱり王道のLisp実装とかから始めるのが良さそうに思う。機能拡張も少しづつ段階的にできそうだし。

## 知見

### まずesprimaにコードを突っ込むじゃろ？

僕たちが最終的に欲しいのはjsのコードで、まずはそのコードがどういうASTで表されるかというのを知る必要がある。でも、Parser APIの仕様を熟読して自分でASTを書くなんてのは現実的じゃない。そこで、まずは欲しいjsを↑で説明したesprimaというjsからASTに変換するツールに突っ込んで、ASTを吐かせる。

esprimaのページに[オンラインパーサ](http://esprima.org/demo/parse.html
)があるので、僕はそれを使ってる。

### 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](https://github.com/estools/esvalid)を使ってより詳細な情報を手に入れる。僕はこういうコードをinitializerに書いている（coffeeですまん）。

```coffeescript
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を綺麗に表示してくれるライブラリ。

そうすると、こんな感じで表示してくれる。

![](http://i.gyazo.com/0a19c6e79b7d272a9980c8449dc492ec.png)

ただし必ずしも問題箇所の特定に役に立つわけじゃないので、そういう時はまあ地道にテスト用のaltjsを書いたりするしかない…


### initializerからコードを分離する

1枚のモノリシックなpegjsのコードだけで何かを作ろうとすると、エラーが補足し辛いしテストも書きにくい。我々がロジックを書くのはaction内か、全ての規則とコンテキストがつながったinitializerと呼ばれる領域である。

幸いinitializerの中ではrequireが使えるので、僕はASTを作るためのコードを普通のjsとして分離している（クライアントサイドで使う時はどうすりゃいいんだろうか。browserifyが使えるかどうかとか、試してないのでわからん）。


### その他参考になった記事とか

- [PEG基礎文法最速マスター
](http://kmizu.hatenablog.com/entry/20100203/1265183754)
- [PegjsでAltjsを作る 第一回 Number型の表現
](http://qiita.com/mizchi/items/d948eb667a0ef67b97bc)
- [PEG 文法について
](http://ponjbogri.github.io/cll-ja/peg/peg_summary.txt)