Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

JavaScriptのパーサコンビネータ Parsimmonを使ってみた

(この記事はQiitaで僕が書いたものを移行した記事です。記事中のコメントはQiitaの該当記事を参照ください)

パーサコンビネータなる素敵なものを見つけたので使って検索クエリのパースをしてみました。そのとき、理解するのに時間がかかったのでメモを残しておきます(公式のサンプルのわかりづらさが原因で1時間ほど無駄にしてしまいました)。 ※追記あり

const Parsimmon = require('parsimmon');
const regex = Parsimmon.regex;
const lazy = Parsimmon.lazy;

const or = regex(/\sor\s/i).result('or');
const and = regex(/(?:\s|\sand\s)/i).result('and');
const not = regex(/\s-(?:\w+)/i).map(s => s.slice(1));
const parser = or.or(not).or(and).or(regex(/[a-z]+/i)).many();

parser.parse('apple or orange or banana yellow').value;// ->['apple','or','orange','or','banana','and','yellow'];

まず、regex()でパースする最小単位を作ります。たとえばregex(/\sor\s/i)単体だと、' or 'はパースできます。しかし、' or A'や' or or 'はパースできずエラーが出ます。なぜなら' or A'は /\sor\s/i にマッチしないからです。 そこで、many()とor()を使います。many()を使うと、そのパーサを何度も適用させることができるようになります。つまり、' or or 'はパースできるようになります。 しかし、何度/\sor\s/iを適応しても' or A'にはなりません。そこでor()が出てきます。A.or(B)はAというパーサが失敗したらBを実行するという新しいパーサを返します。これでAを/\sor\s/iにして、Bを/\w+/にすれば、' or A'をパースできます… といいたいところですが、あと一歩足りません。そう、このA.or(B)というパーサを何度も繰り返し適用しなければ' or A'はパースできません。何度も適用するのは、先ほど出てきたmany()を使います。つまりA.or(B).many()とします。これでようやく' or A'がパースできます。

上のコードはこれを元に作られています。というかまんまですね。この処理を自力で書いたもの(これ)よりはるかに簡潔な上にわかりやすい(慣れれば)。まさに完璧ですね。使いこなせれば自力でパーサ作り放題という魅力が大きいので徐々に使って慣れていきたいですね。

追記

若干手直しして、かっこに対応させました。

const lparen = string('(');
const rparen = string(')');

const or = regex(/\sor\s/i).result('or');
const and = regex(/(?:\sand\s|\s)/i).result('and');
const not = regex(/\s-(?:\w+)/i).map(s => s.slice(1));
const parser = lazy(() => alt(paren, or, not, and, regex(/[a-z]+/i)).many());
const paren = lparen.then(parser).skip(rparen);

parser.parse('apple or orange or banana yellow').value;// ->['apple','or','orange','or','banana','and','yellow'];

これでほぼ完成です。個人的にはこれがチュートリアルの方がわかりやすい気がします。どうでしょうか?