※この記事は自分が学習するついでに過程をまとめた記事です。間違った説明が多々あると思います。
dmajda/pegjs · GitHub https://github.com/dmajda/pegjs
pegjsはJavaScriptで実装されたLL(k), LRの再帰下降パーサです。何をするものかというと、入力された文字列を 分析(parse)して組み替えます。
自分がこのpegjsに興味を持ったのは、 coffeescriptの別実装である https://github.com/michaelficarra/CoffeeScriptRedux が、モダンなパーサコンビネータの実装としてcoffeeの作者本人であるJeremy Ashkenasに紹介されていたからでした。src/grammar.pegjs です。
大学などでコンパイラについて習った人はともかく、それ以外の人は何のことだかわからないでしょうから、なにはともあれサンプルをみながら最小コードを組み立ててみましょう。
この章の目的は、表題どおりJavaScriptのNumberを評価できるようにすることです。自分はaltjsを1つ作成することを目標としています。
サンプルを入手する
pegjsをクローンします
$ git clone git://github.com/dmajda/pegjs.git
npm install -g pegjs しても構いません。その場合、pegjsコマンドで hoge.pegjsを パーサとしてコンパイルできるようになります。
example/javascript.pegjs は JavaScriptのパーサがありますが、正直巨大すぎてなんのことだかわかりません。
手頃なものとして、json.pegjsがJSONスキーマを表現するものとして手頃な感じがしたので、以下はこいつを分解して得た知識です。
なお、自分はテスト用にこういうスクリプトを exmpample/以下に作成し、 coffee -w runner.coffee で走らせていました。
PEG = require '../lib/peg'
fs = require 'fs'
parser = PEG.buildParser fs.readFileSync('scratch.pegjs').toString()
console.log parser.parse """
target to parse
"""
Hello, World!
helloworld.pegjsを作成
start = greeding
greeding = "Hello" "," " " "World" "!"
pegjsの再帰下降パーサは、startから開始され、自分自身にマッチするパターンを探し、なければエラーを吐きます。
runner.coffeeに "Hello, World!"を評価させると、こんな結果が得られます。
[ 'Hello', ',', ' ', 'World', '!' ]
これは Hello, World! という文字列のみを受け付けるパーサで、他の文字列は受け付けません。試しにhogeを入れてみましょう
ERROR: SyntaxError: Expected "Hello" but "h" found.
pegjs以外にも再帰下降パーサ実装はあるのですが、pegjsはエラー文が親切なのが売りのようです。他の実装はjisonなどが有名です。
トークンを加工する
パース時にマッチした文字列に対して、名前をつけて加工することができます。ブロックの中はただのJavaScriptで、returnされたものが新たなトークンとなります。
start = tokens
tokens = hello:"Hello" "," " " world:"World" "!" {
return hello + world;
}
HelloWorld
HelloとWorldに名前をつけて連結したので、ほかの部分は結果から消えました。
トークンを塊で受け取る
$でパターンを囲うと最初から連結された状態になります。
start = tokens
tokens = parts:$("Hello" "," " " "World" "!") {
return parts.toUpperCase();
}
HELLO, WORLD!
整数型を表現する
さて、この章の目的はNumber型を評価することです。Number型はいろいろなかたちを取ります。
たとえば、以下のようなもの。
- 1
- 1234
- -1
- 1.1
数値を受けとる表現は [0-9] で表現出来ます。
digit = [0-9]
数値は1つだけではありません。これを無限個受け取る必要があります。
start = number
number = parts:$(digit+) {
return parts;
}
digit = [0-9]
+ は正規表現の+ と同じ意味で、1つ以上の digitを受け取ります。それを$で受け取っているのでpartsは無限個の数値列を表していることになります。
0で始まる数値を始まりを弾く
これで任意の数値列が受け取れるようになったように見えます。
しかし以下の二つのルールを無視しています。
- 整数は2桁以上の時に0で始まらない
- 負数を含む
(ここでは16進他のことは無視しています)
これに対応してみましょう。
start = number
number = parts:$(int) {
return parts;
}
int
= digit19 digits
/ digit
digit19 = [1-9]
digit = [0-9]
digits = digit+
新しい表現が出て来ました。 = A / B はA のパターンで見つからなかったときはBを検索する、という振る舞いをします。
digit19は0を受け取らないので、最初の digit19 digits が2桁、 次の digit は一桁のときを表していることになります。
正負の符号に対応する
これで整数は対応できた、気がしますが、よく考えたら負数の表示に対応していませんでした。
+ と - のシグネチャを受け取るパターンを追加します
start = number
number = parts:$(int) {
return parts;
}
int
= signe digit19 digits
/ digit19 digits
/ signe digit
/ digit
digit19 = [1-9]
digit = [0-9]
digits = digit+
signe
= "+"
/ "-"
これで任意の整数が受け取れるようになりました。
Float型を受け取る
ここまで来たらもうお分かりだと思いますが、float型は int "." digits で表現出来ますね。
number は Int もしくは Float として表現して、文字列としてのパースは最後に受け取るときに処理するようにします。
start = number:$(number) {
return parseFloat(number);
}
number
= float
/ int
float
= int frac digits
int
= signe digit19 digits
/ digit19 digits
/ signe digit
/ digit
digit19 = [1-9]
digit = [0-9]
digits = digit+
signe
= "+"
/ "-"
frac = "."
これで -111.3242 などがパースできるようになりました
タイトルでNumberと銘打ったけど、16進については面倒くさいので省略。0x のヘッダと [0-9a-z] のパターンを受け取れれば問題ないです。
数値型のパースだけでこれだけの理解が必要ですが、基本的にはどんな複雑なものも小さい単位から組み立てることができます。
(ただ、他人が組み立てた巨大な構文木をかなり読むのは難しいと思います。僕には難しかった…)
json.pegjsは基本的なパース処理を行なっているのに良いサンプルだと思うので、これを読むといいですよ。
第二回は文字列評価とJSの構文表現を予定しています。僕の理解がおいついたら書きます。早ければ今日中に書きたい。