はじめに
TerrarioというTypeScript製のパーサコンビネータを書いたので紹介します。
ソースもGitHubで公開してます。
https://github.com/marihachi/terrario
作成の経緯
これまでJavaScriptやTypeScriptでパーサーを作成する時はPEG.jsを使っていました。
PEG.jsはササッとパーサーを書けるのでパーサーの試作としては便利なライブラリですが、
少し複雑な仕様を盛り込んだパーサーを書こうとすると力不足に感じていました。
こんな時
例えば、以下のように括弧をネストできる文法を考えた場合、
1+(2+(3+4))
素直に実装すると、括弧の中身は関数呼び出しとして表現されます(再帰下降パーサーの場合)。
あまりにも多く括弧が含まれているとスタックオーバーフローの原因になるため、ネストできる回数は制限したくなります。
このような要求をPEG.jsやその他知っているライブラリでは実現が難しそうでした。できたとしても、トリッキーな方法になると思います...。
複雑な仕様に対応したい
そこで、条件を使ったパース処理の分岐をサポートしたパーサジェネレータやパーサコンビネータを探しましたが、それらしいものが見つからなかったので作ってみました。
コンセプト
- 状態を使ってパース処理を分岐できる。
- 例: ネスト回数をカウントしてパース結果を変えるなど。
- パーサーコンビネータとして作成する。
- 小さい関数の組み合わせになるため、JavaScriptエンジンの最適化が効きやすいです。
- APIをシンプルにする。
- 各コンビネータの名前や構成はParsimmonというライブラリを参考にしました。
基本的なパーサーの例
hello worldという文字列を受け入れるパーサーです。
import * as T from 'terrario';
// build a parser
const parser = T.alt([
T.str('hello'),
T.str('world'),
T.str(' '),
]).many(0);
// parse the input string
const input = 'hello world';
const result = parser.parse(input);
console.log(result);
// => { success: true, value: [ 'hello', ' ', 'world' ], index: 11 }
-
T.alt: いずれかにマッチ。優先度付き選択。 -
T.str: 文字列か正規表現で入力文字列にマッチ&消費。 -
parser.many(0): 0回以上の繰り返し。
JSONパーサーの作成例
JSONパーサーは100行程度で書けます。
おわりに
JavaScriptやTypeScriptでパーサーを作成する時は、Terrarioをぜひ試してみてください！