Clojureのパーサコンビネータライブラリ fnparse を使う

前記事と似たような話。

プログラミングHaskellの第8章で紹介されているパーサコンビネータと同じようなことができるfnparseというライブラリがClojureにも存在する。パーサコンビネータと言えばScalaのライブラリ(コップ本*1 31章)にもあるが、どれも似たような感じのものだ。

プログラミングHaskell

Scalaスケーラブルプログラミング[コンセプト&コーディング] (Programming in Scala)

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 <パース後の残りの列> }
• ルールクリエータ
  • 引数: [...] (任意)
  • 戻り値: ルール

まずはシンプルなルールから。

> (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

最後に、特殊ルールとルールクリエータの一覧を。

特殊ルール

これはルールクリエータではなく、単なるルールだということに注意。

• anything
  • 一つだけ何にでもマッチする
• emptiness
  • 空の列にマッチし、結果としてnilを返す

ルールクリエータ

• 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:ずいぶん前に買ったので、古いのしか持ってない。