Clojureのパーサコンビネータライブラリ fnparse を使う
前記事と似たような話。
プログラミングHaskellの第8章で紹介されているパーサコンビネータと同じようなことができるfnparseというライブラリがClojureにも存在する。パーサコンビネータと言えばScalaのライブラリ(コップ本*1 31章)にもあるが、どれも似たような感じのものだ。
- 作者: Graham Hutton,山本和彦
- 出版社/メーカー: オーム社
- 発売日: 2009/11/11
- メディア: 単行本(ソフトカバー)
- 購入: 14人 クリック: 503回
- この商品を含むブログ (115件) を見る
Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)
- 作者: Martin Odersky,Lex Spoon、Bill Venners,羽生田栄一,長尾高弘
- 出版社/メーカー: インプレスジャパン
- 発売日: 2009/08/21
- メディア: 単行本
- 購入: 18人 クリック: 687回
- この商品を含むブログ (121件) を見る
fnparseのマニュアル
https://github.com/joshua-choi/fnparse/wiki
準備
Clojure 1.2であればオリジナルのfnparseでいけるが、 Clojure 1.3 版は org.clojars.jpoplett/fnparse にある。
いつもと同じようにLeiningenのプロジェクトを作って、下記のように指定する。
(defproject hogehoge "0.0.1-SNAPSHOT" :description "parser combinator" :dependencies [[org.clojure/clojure "1.3.0"] [org.clojars.jpoplett/fnparse "2.2.8"]])
$ lein deps
ルール
fnparseは「ルール」という種類の関数と、それを組み合わせて新たなルールを作る「ルールクリエータ」という種類の関数で構成される。
- ルール
- 引数: [STATE]
- STATE: { ... :remainder <パース対象の列> }
- 戻り値: [RESULT NEW-STATE]
- RESULT: ルールが出す任意の値
- NEW-STATE: { ... :remainder <パース後の残りの列> }
- 引数: [STATE]
- ルールクリエータ
- 引数: [...] (任意)
- 戻り値: ルール
まずはシンプルなルールから。
> (use 'name.choi.joshua.fnparse) > (def simple-a (lit \a)) > (simple-a {:remainder [\a \b \c]}) [\a {:remainder (\b \c)}] > (simple-a {:remainder [\b \c \a]}) nil
このsimple-aは文字\aのみにマッチするパーサだ。litというのがルールクリエータで、第一引数にマッチするパーサを戻り値として返す関数だ。
まず、帰ってきたパーサをsimple-aにバインドする。次に、ルールsimple-aに状態(state)を与えて、戻り値としてパース結果と残りの列を含む状態を得ている。
マッチしない列を与えてやると、nilが返る。(先頭からパースするので、マッチしない。)
\aと\bと\cにマッチするパーサをそれぞれ準備し、順々に適用していけば、最後には残り(remainder)列がnilになる。
> (def simple-a (lit \a)) > (def simple-b (lit \b)) > (def simple-c (lit \c)) > (simple-a {:remainder "abc"}) ;; 文字列は勝手に文字のシーケンスに変わる。 [\a {:remainder (\b \c)}] > (simple-b (second *1)) [\b {:remainder (\c)}] > (simple-c (second *1)) [\c {:remainder nil}]
ルールクリエータはlitだけでなく、マッチの条件を示す述語をとるルールクリエータもある。下記は小文字のみにマッチするルールを作っている。
> (def lower (term #(Character/isLowerCase %))) > (lower {:remainder "abc"}) [\a {:remainder (\b \c)}]
これだと、それぞれの呼出で一文字ずつしかマッチしないが、複数の文字を連続でマッチさせる方法もある。
concはルールクリエータであり、与えられた引数を前から順にマッチさせ、それぞれの結果を順にシーケンスとして返す。
最後まで全部マッチしなければルール全体が失敗し、nilを返す。
> (def axc (conc simple-a lower simple-c)) > (axc {:remainder "abcd"}) [(\a \b \c) {:remainder (\d)}] > (axc {:remainder "auc"}) [(\a \u \c) {:remainder nil}] > (axc {:remainder "abbc"}) nil
concのような連接だけでなく、複数のルールから一つを選ぶルールクリエータも存在する。下記のaltは、引数で与えられたルールを順にチェックし、マッチしたものを返す。
> (def choose-abc (alt simple-a simple-b simple-c)) > (def abcs (conc choose-abc choose-abc choose-abc)) > (abcs {:remainder "abcdef"}) [(\a \b \c) {:remainder (\d \e \f)}] > (abcs {:remainder "cccccc"}) [(\c \c \c) {:remainder (\c \c \c)}] > (abcs {:remainder "cdcdcd"}) nil
連接(conc)、選択(alt)とくれば次は反復だが、もちろん反復も存在する。反復系のルールクリエータはいくつも存在するので、代表的な一つだけ紹介する。
下記のrep*は、指定されたルールを0以上個できるだけ多くマッチさせる(最長一致)。
> (def abc* (rep* choose-abc)) > (abc* {:remainder "abcdef"}) [[\a \b \c] {:remainder (\d \e \f)}] > (abc* {:remainder "abcacbaae"}) [[\a \b \c \a \c \b \a \a] {:remainder (\e)}] > (abc* {:remainder "dcdcd"}) [nil {:remainder "dcdcd"}]
さらにもうひとつ、最もよく使うものとしてcomplexがある。これは基本的にはconcと同じなのだが、それぞれのパース結果を加工することができる。
> (def digit (term #(Character/isDigit %))) > (def ip-port (complex [ip (rep+ (alt digit (lit \.))) _ (lit \:) port (rep+ digit)] {:ipaddr (apply str ip) :port (Integer/parseInt (apply str port))})) > (ip-port {:remainder "192.168.0.1:22"}) [{:ipaddr "192.168.0.1", :port 22} {:remainder nil}]
だいたいこれだけ覚えていれば、文脈自由文法が表現できるはず。
さらに、get-info, set-infoを使うことで、文脈依存文法も扱えるようになるのだが、説明し始めると長くなるので、公式の説明を参照。
https://github.com/joshua-choi/fnparse/wiki
最後に、特殊ルールとルールクリエータの一覧を。
ルールクリエータ
- lit a
- 要素aにマッチする。(aは文字でなくても良い。)
- term p
- (p a)が真になるようなaにマッチする。
- lit-conc-seq [a b c ...]
- (conc (lit a) (lit b) (lit c) ...) の省略形
- lit-alt-seq [a b c ...]
- (alt (lit a) (lit b) (lit c) ...) の省略形
- conc rule1 rule2 ...
- 連接
- alt rule1 rule2 ...
- 選択(まずは先に書いたルールでパースし、バックトラックが起こったら次のルールへ行く。)
- rep* rule
- 反復(0以上、最長一致)
- rep+ rule
- 反復(1以上、最長一致)
- rep= n rule, rep< n rule , rep<= n rule
- 最長一致後、長さをチェック
- factor= n rule, factor< n rule, factor<= n rule
- 最短一致(はじめは0から検査し、バックトラックが起こるたびに1ずつ増やしながら検査する。)
- except match-rule fail-rule
- match-ruleにマッチする。ただしfail-ruleにもマッチしたら失敗。
- followed-by rule
- マッチするが、remainderを消費しない。
- opt rule
- (alt rule emptiness) と同じ。
altとfactor系のルールはバックトラックが頻繁に起こるので、なるべく減らしたほうが速いパーサになるはず。
*1:ずいぶん前に買ったので、古いのしか持ってない。