instaparse を久しぶりに触ってみる

instaparse は、Clojure 界隈ではとても有名なパーサジェネレータなので、今更解説することもないのですが、最近時折ちょっとしたパーサを書きたくなることがあったので、思い出しがてらつらつらとざっくり解説というかメモ書きして置こうと思います。

(Clojure Advent Calendar の中では、過去に 2013年 の、でりひろさんの記事 instaparse で遊ぶ で触れられているので、長ーい目で見ればネタかぶりではあります)

introduction

普通に leiningen でプロジェクトを作って、project.clj に dependency を追加します。

$ lein new instaparse-learn
$ vi project.clj

:dependencies に [instaparse "1.4.8"] を足しておきます。

そういえば、Clojure 1.9 がリリースされましたね(cognitect blog)。せっかくなので Clojure 1.9 で動作確認してみました。

ここからは、instaparse にあるチュートリアルをなぞっていきます。まずは、

core.clj

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

って書いておいて REPL を立ち上げます。

parser の定義は、文字列で定義したものを insta/parser 関数でパーサを生成することで行います。定義文字列の形式は、EBNF(Extended Backus-Naur Form)またはABNF(Augmented Backus-Naur Form)ってことらしいですが、何がどう違うのかここでは触れません。なんとなーく雰囲気で書いていきたいと思います。

(def parser1 (insta/parser "S = 'a'"))

これは、aという一文字だけ受け付ける parser となります。これを試してみます。

(insta/parse parser1 "a")
;; => [:S "a"]

解釈した結果は、デフォルトでは hiccup 形式のベクタが返ります(enlive形式にもできますが本稿では割愛します)。解釈できない文字列を与えると

(insta/parse parser1 "aa")
;; => Parse error at line 1, column 1:
aa
^
Expected:
"a" (followed by end-of-string)

(insta/parse parser1 "A")
;; => Parse error at line 1, column 1:
A
^
Expected:
"a" (followed by end-of-string)

のようにエラーとなります（定義では a １文字だけ受け付ける、でした）。
ちなみに後者は、大文字小文字の問題だけですので、parser関数に :string-ci true と指定してあげれば解消します。

(def parser2 (insta/parser "S = 'a'" :string-ci true))
(insta/parse parser2 "A")
;; => [:S "a"]

parser が返すもの

ではもう少し複雑な構文を定義してみましょう。

(def parser3 (insta/parser "S = expr
    expr = term (('+' | '-') term)*
    term = fact (('*' | '/') fact)*
    fact = ws* '(' ws* expr ws* ')' ws* | ws* ('+' | '-') ws* fact ws* | ws* number ws*
    number = #'[0-9]+'
    ws = (' ' | '\t'))

よくありがちな簡単な数式パーサです。これに簡単な数式を食わせてみます。

;;; (clojure.pprint/pprint (insta/parse parser3 "10+ 20 * (30 - 40 / 5)"))
[:S
 [:expr
  [:term [:fact [:number "10"]]]
  "+"
  [:term
   [:fact [:ws " "] [:number "20"] [:ws " "]]
   "*"
   [:fact
    [:ws " "]
    "("
    [:expr
     [:term [:fact [:number "30"] [:ws " "]]]
     "-"
     [:term
      [:fact [:ws " "] [:number "40"] [:ws " "]]
      "/"
      [:fact [:ws " "] [:number "5"]]]]
    ")"]]]]

ちゃんと解釈できましたが、少し冗長です。

• whitespace は単にスキップしたいだけなので、解釈した結果からは捨てたい。
• "(" ")" は無くても構造的に問題はないので省略したい。
• 数字が [:number "5"]等となっているが単純に "5" だけあればよい。

これらの「省略したい」という場合には、instaparse では構文要素を '<' '>' でくくってあげれば対応できます。そこで parser3 を少し書き換えてみます。

(def parser4 (insta/parser "S = expr
    expr = term (('+' | '-') term)*
    term = fact (('*' | '/') fact)*
    fact = ws* <'('> ws* expr ws* <')'> ws* | ws* ('+' | '-') ws* fact ws* | ws* number ws*
    <number> = #'[0-9]+'
    whitespace = (' ' | '\t')
    <ws> = <whitespace>"))

少しわかりにくいですが、'(' ')' と、左辺の 'number'、そして ws、whitespace を「省略」してみました。これで同じ数式を食わせてみます。

;;; (clojure.pprint/pprint (insta/parse parser4 "10+ 20 * (30 - 40 / 5)"))
[:S
 [:expr
  [:term [:fact "10"]]
  "+"
  [:term
   [:fact "20"]
   "*"
   [:fact
    [:expr
     [:term [:fact "30"]]
     "-"
     [:term [:fact "40"] "/" [:fact "5"]]]]]]]

だいぶスッキリしましたね。

ずいぶん遠回りしましたが、parser が返すもの、は、parser が解釈した結果を hiccup 形式で表現したもの、となります。

ちなみに、今回１行の文字列しか与えていないのですが、解釈された要素それぞれに、元のテキストの位置情報がわかるようメタデータが付与されています。

;;; 構造全体だとわかりづらいので、一部構造を切り取ってみる
(nth (second (insta/parse parser4 "10+ 20 * (30 - 40 / 5)")) 3)
;; => [:term [:fact "20"] "*" [:fact [:expr [:term [:fact "30"]] "-" [:term [:fact "40"] "/" [:fact "5"]]]]]

(meta (nth (second (insta/parse parser4 "10+ 20 * (30 - 40 / 5)")) 3))
;; => #:instaparse.gll{:start-index 3, :end-index 22}

(subs "10+ 20 * (30 - 40 / 5)" 3 22)
;; => " 20 * (30 - 40 / 5)"

再帰と Epsilon

これまでのパーサでは意識しませんでしたが、再帰構文を表現するときに、再帰を止めるため「文字列がもう無い」ことを表現する場合があります。instaparse では Epsilon と表現します。次のパーサは、'a'が繰り返されることを表現するパーサです。

;; 右再帰
((insta/parser "S = 'a' S | Epsilon") "aaaa")
;; => [:S "a" [:S "a" [:S "a" [:S "a" [:S]]]]]

;; 左再帰
((insta/parser "S = S 'a' | Epsilon") "aaaa")
;; => [:S [:S [:S [:S [:S] "a"] "a"] "a"] "a"]

右再帰と左再帰で結果の値が異なっていることに注意。

（ただ単に同じものの繰り返しなら + で事足ります。）

(def parser5 (insta/parser "S = 'a'+"))
(insta/parse parser5 "aaaa")
;; => [:S "a" "a" "a" "a"]

これはこれで結果が変わりますが...。いずれにせよ Epsilon の出番はもっと他のケースだと思うのですが、うまい例題が思い浮かびませんでした（のでチュートリアルそのまんま、です）。

式の変換(transform)

instaparse では、パーサで得られた結果のデータ構造を簡単に「変換」する仕組みが用意されています。それが insta/transform 関数です。insta/parserの結果の hiccup 形式のベクターの、最初のキーワードに対応した関数を定義してあげます。

例えば先程の単純なパーサ parser5 について考えます。parser5 は :S という要素しか解析しません。:S は複数の "a" が続くだけですので、これを結合する関数を考えます。

(insta/transform {:S (fn [& xs] (apply str xs))}
    (insta/parse parser5 "aaaa"))
;; => "aaaa"

transform に渡されるキーワードに紐付く関数は、もちろん定義した構文それぞれに合う形で考える必要があります。

もう少し具体例を考えるため、もう一度 parser4 の定義を思い出してみます。

;; 再掲
(def parser4 (insta/parser "S = expr
    expr = term (('+' | '-') term)*
    term = fact (('*' | '/') fact)*
    fact = ws* <'('> ws* expr ws* <')'> ws* | ws* ('+' | '-') ws* fact ws* | ws* number ws*
    <number> = #'[0-9]+'
    whitespace = (' ' | '\t')
    <ws> = <whitespace>"))

parser4 では expr、term、fact、の３つの要素の構文を定義しています。今回は数式を lisp っぽく 前置形式 に変換することにします。

:fact は常に引数１つ（数字の文字列、または ( ) で囲われた数式(expr)の結果）です。ここでは、文字列の場合 Integer に変換、そうでなければそのまま返します。

(defn transform-fact [x]
  (if (string? x) (Integer/parseInt x) x))

:term は fact 単体、もしくは fact に対する剰余算の連続、と定義しています。これを、剰余算のオペレータを前置にしたリストに変換してみます。

(defn transform-term [x & xs]
  (if xs
    (let [[op & rest] xs
          rest (transform-term rest)]
      `(~op ~x ~@rest))
    x))

:expr は、:term とほぼ同じ感じで今度は加減算になります。関数の見た目はまったく同じになりました。

(defn transform-expr [x & xs]
  (if xs
    (let [[op & rest] xs
          rest (transform-expr rest)]
      `(~op ~x ~@rest))
    x))

これを map にして insta/transform に指定して試してみます。

(insta/transform {:fact transform-fact :term transform-term :expr transform-expr} 
    (insta/parse parser4 "10+ 20 * (30 - 40 / 5)"))
;; => [:S ("+" 10 ("*" 20 ("-" 30 ("/" 40 5))))]

オペレータが文字列 "+" になってしまっているので、そこをついでに書き換えてあげればなお良いでしょう。

parser 定義のリソース化と defparser

構文が複雑になると、普通に Clojure の「文字列」として定義するのが辛くなってくるでしょう。普通に外部ファイルに記述して slurp するのがよいと思います。

ところで instaparse 自体は ClojureScript もサポートしています。ClojureScript の場合には、 Clojure のように slurp が使えないので外部リソース化がめんどくさそうです。そこで、instaparse に用意されている insta/defparser を使います。

;; Clojure
(:require [instaparse.core :as insta :refer [defparser]])
;; ClojureScript
(:require [instaparse.core :as insta :refer-macros [defparser]])

(defparser parser6 "https://somewhere/path-to-grammer-text")
;; 以下とだいたい同じ
;; (def parser6 (insta/parser (slurp "https://somewhere/path-to-grammer-text")))

defparser を使うと、URLでリソースを指定してパーサを定義できます。またコンパイル時に定義まで行われるので、実行時にオーバーヘッドがかかることがなく、ClojureScript の場合に積極的に使うべきかと思います。

visualize

instaparse には、構文を visualize する機能があります。insta/visualize 関数なのですが、デフォルトでは使えず project.clj に dependency を追加してあげる必要があります。

[rhizome "0.2.9"]

(ソースはここ) これで visualize を使えるようになります。

(insta/visualize
 (insta/parse parser4 "10+ 20 * (30 - 40 / 5)")
 :output-file "out.png")

もちろん transform 後の様子も visualize できます。

(insta/visualize
 (insta/transform {:fact transform-fact :term transform-term :expr transform-expr}
                  (insta/parse parser4 "10+ 20 * (30 - 40 / 5)"))
 :output-file "out2.png")

規模が大きくなったらつらいかも、ですが、視覚的にわかりやすいのはありがたいです。

おわりに

ざっくり紹介のつもりでしたが、長々と書いてしまいました。v1.0 リリースが 2013/04/11 と登場からずいぶん立っており、利用されている方も多いと思います。ちょっとしたものをさくっと作るにはすごく楽で、REPL での開発とも相性が良く Clojure 製ライブラリの中でのお気に入りの一つです。

ところで、今年の流行語大賞に「インスタ映え」が入りましたね。関係ないけど（といいつつアドベントカレンダーのテーマをこれにしたのは、インスタつながりが理由だったという...）。

お後がよろしいようで。