instaparseでCSVパーサーを書いてみる

instaparseは文脈自由文法(CFG)による構文解析ライブラリです。ほぼそのままのEBNFと正規表現を使えます。ここでは手ごろなところでCSVの解析器を作ってみます。

leiningenプロジェクト依存モジュール

何はともあれproject.clj。最低限必要なライブラリは以下の二つ。

  :dependencies [[org.clojure/clojure "1.5.1"]
                 [instaparse "1.0.1"]]

CSVのBNF

CSVはRFC4180にBNFが記述されているのでこれを拝借します。

file = [header CRLF] record *(CRLF record) [CRLF]
header = name *(COMMA name)
record = field *(COMMA field)
name = field
field = (escaped / non-escaped)
escaped = DQUOTE *(TEXTDATA / COMMA / CR / LF / 2DQUOTE) DQUOTE
non-escaped = *TEXTDATA
COMMA = %x2C
CR = %x0D
DQUOTE =  %x22
LF = %x0A
CRLF = CR LF
TEXTDATA =  %x20-21 / %x23-2B / %x2D-7E

instaparseはEBNFベースですが、RFCはABNFなので多少修正が必要です。
なるべく元の形を保ったまま修正するとこんな感じになります。

修正点は、まずABNFとEBNFの差異の手直しが

0回以上の繰り返し * の位置を前から後ろへ移動。
DQUOTEの２回繰り返し2DQUOTEを定義（EBNFはABNFのように前置数字で定数回繰り返しを表現できない）。
選択を表すパターンの区切りは / ではなく |。

そしてinstaparseの都合による修正

文字コード表現をユニコード表現に変更。\uXXXX
文字リテラルをシングルクオートで囲む*1
範囲による文字セットの指定は正規表現パターンを使う #'[xxx-yyy]'

パーサーの作成とパースの実行(instaparse.core/parser)

parser関数でパーサーオブジェクトを作り、そのオブジェクトでパースを実行します。パーサーオブジェクト(instaparse.core.Parser)はclojure.lang.IFnを実装しているcallableなオブジェクトなので、関数のように適用できます。

(ns example.instaparse1
  (:require [instaparse.core :refer [parser]]
            [clojure.pprint :refer [pprint]]))

;; gistに置いてあるBNF定義ファイルを元にパーサー作成。
(def csv-bnf "https://gist.github.com/mnzk/5426024/raw/11de5851adc5b3dd704ec4079c22aa6ff8d131df/csv-bnf-rfc4180.txt")
(def csv-parser (parser csv-bnf))

;; ローカルのcsvファイルをパース
(def data-file "/path/to/data.csv")
(def tree (csv-parser (slurp data-file)))

(pprint tree)

簡単ですね。このようにparserに与えるBNF定義は外部ファイルから読み込ませることができます*2。また外部ファイルではなくコード内に直接文字列で記述することもできます*3。

CSVデータdata.csvは、こんな感じの物を用意しました。

RFCではレコード終端の改行コードはCRLFです。LFのみは不可なのでご注意を。*4

パースの結果はこんな感じになります。

[:file
 [:record
  [:field [:non-escaped [:TEXTDATA "a"] [:TEXTDATA "a"]]]
  [:COMMA ","]
  [:field [:non-escaped [:TEXTDATA "b"] [:TEXTDATA "b"]]]]
 [:CRLF [:CR "\r"] [:LF "\n"]]
 [:record
  [:field [:non-escaped [:TEXTDATA "c"] [:TEXTDATA "c"]]]
  [:COMMA ","]
  [:field
   [:escaped
    [:DQUOTE "\""]
    [:TEXTDATA "d"]
    [:TEXTDATA "d"]
    [:COMMA ","]
    [:TEXTDATA "e"]
    [:TEXTDATA "e"]
    [:2DQUOTE [:DQUOTE "\""] [:DQUOTE "\""]]
    [:TEXTDATA "F"]
    [:2DQUOTE [:DQUOTE "\""] [:DQUOTE "\""]]
    [:DQUOTE "\""]]]]
 [:CRLF [:CR "\r"] [:LF "\n"]]
 [:record
  [:field
   [:escaped
    [:DQUOTE "\""]
    [:TEXTDATA "g"]
    [:TEXTDATA "g"]
    [:CR "\r"]
    [:LF "\n"]
    [:TEXTDATA "h"]
    [:TEXTDATA "h"]
    [:DQUOTE "\""]]]]
 [:CRLF [:CR "\r"] [:LF "\n"]]]

BNFをそのまま適用できるということは公開されているBNFを利用して手軽にパーサーが作れるということになります。便利ですね。

パースの次はどうするの？ (instaparse.core/transform)

パースされたデータはhiccup形式のtree構造になっています。このtree構造をトラバースしながら関数適用するために、transformという関数が用意されています。
transformの第一引数はキーワードと適用関数のマッピング情報。第二引数は処理対象のtree構造データです。

(ns example.instaparse2
  (:require [instaparse.core :refer [transform]]))

(def row [:record
          [:field [:non-escaped [:TEXTDATA "a"] [:TEXTDATA "a"]]]
          [:COMMA ","]
          [:field [:non-escaped [:TEXTDATA "b"] [:TEXTDATA "b"]]]])

(->> row
     (transform {:TEXTDATA #(str "@-" % "-@")}))
;;=> [:record
;;    [:field [:non-escaped "@-a-@" "@-a-@"]]
;;    [:COMMA ","]
;;    [:field [:non-escaped "@-b-@" "@-b-@"]]]

(->> row
     (transform {:TEXTDATA identity
                 :record #(take-nth 2 %&)}))
;;=> ([:field [:non-escaped "a" "a"]]
;;    [:field [:non-escaped "b" "b"]])

(->> row
     (transform {:TEXTDATA identity
                 :record #(take-nth 2 %&)
                 :non-escaped str
                 :field identity}))
;;=> ("aa" "bb")

つまり、

(def dat [:HOGE "A" "B" "C"])

というデータに対して

(transform {:HOGE func} dat)

とすると

[:HOGE "A" "B" "C"]
   ↓
(func "A" "B" "C")

という風にS式に変換され、そのS式を評価した結果に置き換えられます。この変換が木構造のすべてのノードに対して再帰的に行われるイメージです。*5
funcは引数を「固定数引数で受け取る」ことも「可変長引数で受け取る」こともできます。すべて可変長引数とみなしてもよいですが、引数が１つだけと決まっている場合には可変長にしないほうがシンプルに書けるので無理に可変長引数に統一しない方がよいと思います。
なお、リーダーマクロ #(...) によるクロージャでは可変長引数は %& でシーケンスとして受け取ることができます。

最後に、data.csvのデータ全体をtransformしてみます。折角 hiccup形式なので、hiccupモジュールを使ってHTMLに変換できるような形にしてみます。

hiccupモジュールを使いますので project.clj の依存モジュールに追加が必要です。

いくつかの問題点

instaparseとRFC4180によるCSV処理をしてみましたがこのままでは問題があります。
RFCの問題として

日本語が受理されない。
行終端がCRLFに限定されると不便。せめてLF単独も許可したい。
headerとrecordが区別できない。

最初の２つはBNFを手直しすればすぐに対応可能です。
3つ目のheaderの問題は、headerを識別するための仕様をどこかに追加する必要があります。「一行目を必ずheaderとする」とか「一行目一文字目が#ならばそれ以降をheaderとする」とか。仕様を決めれば実装は簡単です。

しかしもうひとつ気になる点があります。

instaparseで作ったパーサーは、パース対象が「文字列」に限定されている。

パーサーを作るためのBNF定義情報は外部ファイルやweb上リソースなど自由度が与えられているのですが、パーサーオブジェクトが適用できる対象データは文字列として与えなけらばならないようです。clojureなのですから文字列のchunkなどをlazy-sequenceにしたものを扱いたいと思ってもそれはできません。パーサーに渡す前に全体を文字列にしてから渡さなければなりません。
これは、対象データが例えば100万行あるCSVデータであるような場合には致命的な問題になると思います。instaparseのAPI仕様の問題ですので簡単には解決できないでしょう。

おわりに

今回はclojure界隈で話題になっていたinstaparseを試してみました。「BNFがそのまま利用できる」というのは思っていた以上に便利に感じました。特に既に精査され公開されているBNFを利用できるのは魅力的です。反面自分で複雑なBNFを定義して開発やメンテする場合を考えると、ほかのパーサコンビネータと比べて有利ということはないかな……と思いました。でも transformは便利かも。

*1:ダブルクオートでも可能です。

*2:外部のリソースを指定した場合、slurpで定義情報を取り込みます。したがってslurpがサポートする、ローカルファイル、web上リソースなどを指定可能です

*3:直接コード内に記述する場合、BNF内のダブルクォートをエスケープしなければならない点に注意が必要です。このモジュールの作者は「なぜclojureにはpythonのような三連クォートがないのか」と嘆いています。確かに欲しいかも

*4:gistに置いてみましたが、gits, githubでは改行コードがLFになってしまうのでそのまま読み込みこんでパースすることは出来ません。上記でdata.csvをローカルファイルとしているのはそのためです。

*5:多分深さ優先で深いところから評価されるのだと思います。

Code Aquarium

minazoko's blog -- 水底のブログ --