はじめに

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をぜひ試してみてください！