[Clojure]instaparseでパーサを作成

instaparseとは

今、Clojure使いの間では大きな話題となっている、パーサ(構文解析プログラム)作成用ライブラリです。
正規表現を使うのと同じくらい簡単にパーサが作成できるとのことです。
Clojure作者である、Rich Hickeyも大興奮(ソース:twitter)らしいです。

では簡単にinstaparseの特徴を解説します。
githubに機能一覧があるのですが、そこから代表的ないくつかの特徴を抜粋。

• 入力として文字列を受け取り、EBNF記法を用いて構文解析ツリーを生成する
• 出力フォーマットは、Clojureで人気の形式（hiccupとenlive）の両方をサポート
• 解析エラーの詳細なレポートを出してくれる

文字列をEBNF記法でうけとってパーサが簡単に書けるというみたいです。
Githubのチュートリアルを参考に、instaparseを動かしてみましょう。

環境構築方法

今回使用した動作環境は以下のとおりです。

• OS : MacOS X 10.7.5
• Clojure : 1.5.1
• Leiningen : 2.1.2

instaparseを使ってみる

まずはleiningenでプロジェクトを作成します。

% lein new insta

　

次に依存するライブラリをinsta/project.cljに記述しましょう。下記のように、instaparseを依存ライブラリに追加してください。

(defproject insta "HEAD"
  :dependencies [[org.clojure/clojure "1.5.1"]
                 [instaparse "1.0.1"]]
  :main insta.main)

project.cljを記述したらlein depsで依存ライブラリを取得しておきます。

% lein deps

では、src/insta/main.cljを下記のように記述しましょう。

(ns insta.main
(:require [instaparse.core :as insta]))

(def as-and-bs
  (insta/parser
    "S = AB*
     AB = A B
     A = 'a'+
     B = 'b'+"))

(defn -main [& args]
  (as-and-bs "aaabbaabbb"))

parser関数で渡している文字列が、構文解析ルールです。(BNFの詳細については割愛)
上記ルールにしたがって「aaabbaabbb」を解析させると、次のようになります。

% lein run 
[:S [:AB [:A "a" "a" "a"] [:B "b" "b"]] [:AB [:A "a" "a"] [:B "b" "b" "b"]]]

先ほどは出力形式がhiccup形式でしたが、enlive形式にすることもできます。
次のようにparserの引数として渡すか、set-default-output-format!関数を使用して:enliveをセットします。

;関数でセットするか
(insta/set-default-output-format! :enlive)

;もしくはparserの引数で渡す
(def as-and-bs
  (insta/parser
    "S = AB*
     AB = A B
     A = 'a'+
     B = 'b'+" :output-format :enlive))

これで実行すると、enlive形式でパース結果が出力されます。

% lein run
{:tag :S, :content ({:tag :AB, :content ({:tag :A, :content ("a" "a" "a")} {:tag :B, :content ("b" "b")})} {:tag :AB, :content ({:tag :A, :content ("a" "a")} {:tag :B, :content ("b" "b" "b")})})}

さて、次は構築されたツリーを変換する例をみてみましょう。
次の関数はスペース区切りの文章をアルファベット(:word)と数値(:number)にパースします。

(def words-and-numbers-one-character-at-a-time
  (insta/parser
    "sentence = token (<whitespace> token)*
     <token> = word | number
     whitespace = #'\\s+'
     word = letter+
     number = digit+
     <letter> = #'[a-zA-Z]'
     <digit> = #'[0-9]'"))

;呼び出し.main関数の中に記述してください
(words-and-numbers-one-character-at-a-time "abc 123 def")

実行すると、次のようにパースされますが、１文字ずつの文字として分割されているので、使いやすいとはいえません。

% lein run 
[:sentence [:word "a" "b" "c"] [:number "1" "2" "3"] [:word "d" "e" "f"]]

そういったケースにtransform関数を使用すると、パースされた結果の値に対して関数を適用した結果を取得できます。
次の記述では、:wordの結果は文字列として連結を、:numberの結果は、文字列連結した後、数値に変換しています。

;transformで変換.main関数の中に記述してください
(insta/transform
     {:word str,
      :number (comp read-string str)}
     (words-and-numbers-one-character-at-a-time "abc 123 def"))

実行してみましょう。結果が使いやすくなりました。

% lein run     
[:sentence "abc" 123 "def"]

;なお、enlive形式だとこうなる
;{:tag :sentence, :content ("abc" 123 "def")}

まとめ

さて、今回はClojureのパーサ作成ライブラリを紹介しました。
私はBNFやパーサについては詳しくないのですが、その私でも簡単なサンプルなら動かすことができたので、
かなりすごいライブラリなのではないでしょうか。

参考サイトなど

• Github: https://github.com/Engelberg/instaparse