Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

この記事はJavaScript Advent Calender 2014の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による定義が有名で、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

https://github.com/hdemon/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が使えるかどうかとか、試してないのでわからん)。

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした