みどりねこ日記

よくわからないけど、頑張りますよ。

パーサの連接とか

前回までに出てきた基本的なパーサをくっつけることで複雑なパーサが書けるわけですが、 今回はそのような連接とかを手助けしてくれるパーサコンビネータを紹介?します。

Kern のパーサコンビネータはシーケンス化、反復、選択、それと括弧の対応とかの面倒を見てくれるみたいです。

例のごとく kern をロード。

(use 'blancas.kern.core)

skip-ws は入力のはじめにあるすべての空白をスキップ。

doc.core> (run (skip-ws letter) "\t \n x")
\x
nil

<|> はあたえられたパーサを成功するまで試す。すべてのパーサが失敗するか、入力を消費するパーサが失敗すると全体として失敗する。

doc.core> (run (<|> digit letter) "x")
\x
nil
doc.core> (run (<|> digit letter) "9")
\9
nil
doc.core> (run (<|> digit letter tab) "?")
line 1 column 1
unexpected \?
expecting digit, letter or tab
nil

で、 >> は1つ以上のパーサを適用する。最後のパーサの結果だけを返す。

doc.core> (run (>> digit digit letter) "91x")
\x
nil

<< は1つ以上のパーサを適用する。最初のパーサの結果だけを返す。

doc.core> (run (<< upper (sym* \-) digit digit) "F-16")
\F
nil

<$> は与えられたパーサを入力に適用して、そのあとパースした結果に対して与えられた関数を適用、その結果を返す。

doc.core> (run (<$> #(* % %) dec-num) "12")
144
nil

<*> は2つ以上のパーサを適用して、それらの結果をベクタにして返す。

doc.core> (run (<*> dec-num tab oct-num tab hex-num) "737\t747\tA340")
[737 \tab 487 \tab 41792]
nil

<:> はバックトラックするパーサらしい。もし失敗しても消費した入力は回復。

doc.core> (:input (parse (<:> float-num) "5005.a"))
(\5 \0 \0 \5 \. \a)

many は入力に対しパーサを0回以上、失敗するまで適用。many1 は1回以上で、最低1回生功しないと失敗。

doc.core> (run (many letter) "123")
[]
nil
doc.core> (run (many letter) "xyz")
[\x \y \z]
nil
doc.core> (run (many1 letter) "xyz")
[\x \y \z]
nil
doc.core> (run (many1 letter) "123")
line 1 column 1
unexpected \1
expecting letter
nil

optional はパーサが成功するか消費を行わかなった場合に全体として成功する。

doc.core> (run (<+> (optional (sym* \-)) dec-num) "-45")
"-45"
nil
doc.core> (run (<+> (optional (sym* \-)) dec-num) "45") 
"45"
nil
doc.core> (run (<+> (optional float-num) letter) "45.A")
line 1 column 4
unexpected \A
expecting digit
nil

option は与えられたパーサを適用する。もし入力を消費せずに失敗したら、与えられた値を結果として返すっぽい。

doc.core> (run (option 3.1416 float-num) "foo")
3.1416
nil

skip は1つ以上のパーサを取ってそれらの結果をすべて飛ばす。結果として nil を返す。

doc.core> (run (skip letter digit letter digit) "A5E8") 
nil
nil

skip-many はパーサを0回以上適用し結果を飛ばす。nil を返す。skip-many は1回以上。

doc.core> (run (skip-many letter) "xyz")
nil
nil
doc.core> (run (skip-many1 letter) "xyz") 
nil
nil
doc.core> (run (skip-many1 letter) "123")
line 1 column 1
unexpected \1
expecting letter
nil

sep-by は与えられたパーサによって分けたものに対して別のパーサを0回以上適用する。sep-by1 は1回以上。

doc.core> (run (sep-by (sym* \&) (many1 letter)) "a&bb&ccc&ddd")
[[\a] [\b \b] [\c \c \c] [\d \d \d]]
nil

end-by は与えられたパーサによって別れる/終わるものに対して別のパーサを0回以上適用する。end-by1 は1回以上。

doc.core> (run (end-by (sym* \&) (many1 letter)) "a&bb&ccc&")
[[\a] [\b \b] [\c \c \c]]
nil

between は1,2つ目のパーサの間のちに対して3つ目のパーサを適用する。

doc.core> (run (between (sym \() (sym \)) dec-num) "(1984)")
1984
nil

<+> はひとつ以上のパーサをとる。で、結果を潰してくっつけて、文字列にする。

doc.core> (run (<+> letter (many alpha-num)) "a177")
"a177"
nil

数字のパース

kern にはいくつか数値のパーサが用意されてて、これらは結果として文字列ではなく適切な数値型を返します。これらのパーサは名前空間 lexer 内のそれらに比べてサポートする数値型は少ないし、空白とかコメントとかもスキップしません。つまるところ、大きなパーサの低レベルの部分で使うべき関数みたいですね。

使用にあたって Kern の名前空間 core をロードします。

(use 'blancas.kern.core)

value はパーサを走らせてそのパース結果を返す関数です。引数としてパーサと文字列を受け取って、オプションとして文字列が何であるか(例えばファイルネームだとか)を示すことができます。

dec-num は十進数の正数をパースして結果として long 型を返します。

doc.core> (value dec-num "8086")
8086

oct-num は8進数の正数をパースして結果として long 型を返します。

doc.core> (value hex-num "747")
487

hex-num は16進数をパースして結果として long 型を返します。 0x が先頭につくものは許されません。

doc.core> (value hex-num "FEED")
65261

float-num は浮動小数点数をパースして結果として double 型を返します。指数表現はサポートされていません。 lexer 内の float-lit ではサポートされてます。

doc.core> (value float-num "3.1415927")
3.1415927

Kern のプリミティブパーサ

Kern にもプリミティブなパーサがあって、これらを組み合わせていくことで大きなパーサを作るというのが関数型らしいパーサの作り方なわけですが。 それらをちょっと見ていきます。 Kern けっこうかわいいわあ。

(use 'blancas.kern.core)

return は常に成功し、与えられた値を返す。

doc.core> (run (return "foo") "xyz")
"foo"
nil

fail は与えられたエラーメッセージとともに失敗する。

doc.core> (:ok (parse (fail "foo") "xyz"))
false
doc.core> (run (fail "this is bad") "xyz")
line 1 column 1
this is bad
nil

satisfy は与えられた述語を入力の最初の文字に適用し、それによって成功か失敗かが決まる。

doc.core> (run (satisfy #(= \x %)) "xyz")
\x
nil

any-char は入力された文字を返す。

doc.core> (run any-char "x")
\x
nil

letter は大文字小文字のどちらも成功する。

doc.core> (run letter "z")
\z
nil

lower, upper はそのまんま。

doc.core> (run lower "a")
\a
nil
doc.core> (run upper "M")
\M
nil

white-space は空白文字を受け付ける。

doc.core> (run white-space "\t")
\tab
nil

space はスペースだけ。 tab もまあそんなかんじ。

doc.core> (run space " ")
\space
nil

digit は \0 から \9 までの数字を受け付ける。 hex-digit はそれに加えて \A から \F まで。 oct-digit は \0 から \7 まで。

doc.core> (run digit "9")
\9
nil

alpha-num は英数字。

doc.core> (run (many alpha-num) "9A")
[\9 \A]
nil

sym* は特定の文字だけ。 sym- は大文字小文字関係なく。ただし結果として得る文字は sym- に渡された文字。

doc.core> (run (sym* \x) "x")
\x
nil

token* は Haskell でいう string パーサ。複数のシーケンスが渡された場合、どれかが成功するまで試され続ける。 token- は大文字小文字関係なく。

doc.core> (run (token* "foo" "bar" "baz") "bazaar")
"baz"
nil

word は token と同じようなものだけれど、許可しない終端を設定できる。 word- は大文字小文字関係なく。

doc.core> (run (word* (one-of* "|-/") "foobar"))
"foobar"
nil
doc.core> (run (word* (one-of* "|-/") "football" "foobar") "foobar*")
"foobar"
nil
doc.core> (run (word* (one-of* "|-/") "foobar") "foobar/")
line 1 column 8
unexpected /
expecting end of foobar
nil

one-of は与えられた文字列のどれかの文字であれば受け付ける。 none-of はその逆。

doc.core> (run (one-of* "xyz") "zap")
\z
nil

new-line* は \n を受け付ける。 eof はもし入力が空なら成功する。

field* は与えられた文字列で区切られる文字列をパースする。

doc.core> (run (field ",;") "California,")
"California"
nil

split-on は空白か与えられた文字列で区切られる文字列を分割する。

doc.core> (run (split-on ",./") "Now, is the time")
["Now" "is the time"]
nil

split は空白で区切られたテキストを分割する。

doc.core> (run split "Now is the time")
["Now" "is" "the" "time"]

Clojure の パーサコンビネータライブラリ Kern

Clojure でパースするとき、みんなどうしてるんだろう。 Parsec のようなものがあればいいのに〜、と思って探してみたところ、この Kern が一番よさげだった。

特徴

  • 状態モナドベースのコンビネータ
  • C, Java, Haskell, Shell の構文をサポート
  • パースと式の評価をサポート
  • 正確で詳しいエラーメッセージ
  • エラーメッセージは簡単に多言語化可能
  • パーサの内部状態にクライアントコードからアクセス可能
  • サンプルあり

セットアップ

leiningen がインストールされているなら、 project.clj の :dependencies に

[org.blancas/kern "0.6.1"]

で、コード中に

(use 'blancas.kern.core)

Haskell の Parsec っぽい

HaskellのParsecですねという感じ。というか記号とかもそのまんま。 ただちょいちょい違うところがあるかなあという印象。

例えば数字のパース。

doc.core> (run digit "123")
\1
nil
doc.core> (run (many digit) "123")
[\1 \2 \3]
nil

run はパース結果を印字する。パースしてない残りの入力はそのまま。パーサの状態は run* で見れる。

doc.core> (run* digit "123")
{:input (\2 \3),
 :pos {:src "", :line 1, :col 2},
 :value \1,
 :ok true,
 :empty false,
 :user nil,
 :error nil}
nil

文字列以外にも入力としてファイルとかも受け付ける。 runf は パーサとファイル名、文字コードを受け取ってパースする。

コンビネータ <*> は与えられたパーサを順に実行し結果をベクタにして返す。

doc.core> (run (<*> letter letter digit) "os8")
[\o \s \8]
nil

parse は run みたいな動作をするけれどパーサの状態を返すという点で異なる。 :ok フィールドをチェックすればパースに成功したかどうか分かる。 :value セレクタを用いればパーサの結果が得られる。

doc.core> (let [st (parse (token* "abc") "abc")]
        (when (:ok st) (str "got " (:value st))))
"got abc"

どういったときに IORef を使うべきか

どういったときに IORef を使うべきか、という疑問が湧いてきたので、ぐぐってみると stackoverflow に同じ質問してる人がいたのでそれを訳してみる(2009年のものだから情報古いかも)。



"いつ IORef を使うべきか混乱しています。 IORef を使うべきか否かを判断するとき、従うべきガイドラインはありますか? どのような状況なら、IORef でなくて State モナドを用いるべきなのでしょうか。"



以下がこの質問に対しての返答です。



" State やそれに関連した ST は、どれもユニットとしてのモノリシックな状態を持つ計算を生成します。これらは、ふつう書き換え可能な状態を一時的なデータとして扱います。つまり、結果を得るために必要なものですが、使ったあとは気にする必要がない(というよりすべき得ない)ということです。

一方で、 IORef に入れるモノは"計算"ではありません。 IORef は IO 内で自由に使える値を保持できるただの箱に過ぎません。この箱はデータ構造も入れられますし、( IO 部分の)プログラムの中で自由に渡せます。保持する値の中身を自由に改変することだってできますし、関数で覆い隠すこともできます。実際、C言語の変数やポインタといった、かなりごちゃごちゃした性質も IORef でモデリングすることもできます。

変数がコードのブロック内に存在するのに、インタラクションと他を完全に分けることは、極めて奇妙、または率直に言ってありえなく見えてしまいます。状態を渡したい時や、データ構造の中に入れたい時もあるかもしれません。そういったときには、”箱”を用意するというアプローチ以外に道はないかもしれません。 Write Yourself a Scheme in 48 hours の”変数と代入”のチャプターが例を示しています。リンク先では、何故 State または ST ではなく、 IORef を用いて Scheme の環境をモデリングすることが最適化がうまく示されています。

簡単に言うと、( Scheme での)環境は任意のネストを構成し、ユーザーインタラクションによるインスタンスを保持したり( (define x 1) と Scheme REPL に入力されたら、 x と入力した際に1が返ってくることを期待しますよね)、 Scheme の関数からの参照を受ける働きなどがあります(Schemeでは関数は環境を捕捉します)。

まとめると、したいことが向いているならば State を用いると綺麗に仕上がる傾向があります。もし複数の状態が必要ならば、 ST を用いるとよいでしょう。しかしもし、状態を計算として扱うのが不便に感じるのであれば、可変のものとして扱うといいでしょう。そのとき IORef は最適解となります。"

実はこのコメントの最後に STM とか TVar を勧めていたんですけれど、一体どうなんでしょう…(^_^;)

構文メモ

関数型言語

<ラムダ式> ::= <変数> | <ラムダ式> <ラムダ式> | λ <変数> . <ラムダ式> | ( <ラムダ式> )
<関数定義> ::= ( <関数名> <ラムダ式> )

論理型言語

<論理式> ::= <リテラル> | <論理式> -> <論理式> | <論理式> ∧ <論理式> | <論理式> ∨ <論理式> | ∀ <変数> <論理式> | ∃ <変数> <論理式>
<リテラル> ::= <述語> | ¬ <述語>
<述語> ::= <述語名> ( <項> {, <項> }* )
<項> ::= <定数> | <変数名> | <関数名> ( <項> {, <項> }* )
<節> ::= { ∀ <変数名> }* <リテラル> { ∀ <リテラル> }*

命令型言語

<文> ::= <代入文> | <制御文> | <名前> : <文> | begin <文>* end
<制御文> ::= <条件文> | <繰り返し文> | <ジャンプ文>

<if 文> ::= if <式> <文>
<if-else 文> ::= if-else <式> <文> <文>
<while 文> ::= while <式> <文>
<for 文> ::= for ( <式> ; <式> ; <式> ) <文>

Parsec を使って Apache のログファイルをパースしてみる2

さて、ログの行をパースすることができるようになったので、これをコマンドラインツールにしましょう。今回は IO と do 記法を用いて作業します。ですので、少なくとも基本は知っていることが望ましいです。もし不安なら、Learn You a Haskell を読みましょう。

ユースケースを見ると、圧縮されていないログファイル一つがあるとして、そのログファイルは複数行のログを保持していると推測できます。私たちのパーサは一行をパースします。なので、どうすればいいかを書いてみましょう。

  1. ファイルを読み込む
  2. 行ごとに切り離す
  3. 各行をパースする
  4. 結果を表示する

最初の操作は Prelude にある readFile を使います。つまり、標準でインポートされるということです。 readFile は IO String 型を持ちます。これは、 IO の文脈を壊せないことを表しています。もしこのことで混乱したならば、上のリンクのチャプターを読んでみてください。

main = do
	file <- readFile "logfile.txt"

main 関数、またはアクションは、すべての Haskell プログラムのスタート地点です。 readFile "logfile.txt" の結果を file という名に束縛するところから始めます。今、 file の型は String です。 String 型ということは、 Prelude の関数 lines に渡せるということですね!しかし、 readFile は IO モナドのなかに包んで渡してくるので、そのままでは lines に渡せません。ですので、 <- ではなく let による束縛を使いましょう。

main = do
	file <- readFile "logfile.txt"
	let logLines = lines file

良い感じですね!もしこれをコンパイルしようとすると、エラーを吐かれます。なぜなら、 do 記法の最後は let による束縛で終わらせることはできないからです。直しましょう。しかしその前に、 Parsec の parse を見てみましょう。ここでは parse の型を書きませんが、 ghci で

 :t parse

とすると見ることができます。さっぱりわかりませんね!
しかし幸運にも、この関数 parse は使いやすいです。基本的には以下のように使います:

parse line "(test)" testLine

つまり、なにか一つ Parser をとり、パーサ名 String をとり、パース対象の String を受け取る関数です。このコードは Either ParserError String を返します。しかし、私たちのパース対象は [String] なので(lines による分割)、 mapM (map のモナド版)を用いてログファイル全体をパースしましょう。

main = do
	file <- readFile "logfile.txt"
	let logLines = lines file
	result <- mapM (parse line "(test)") logLines

result の方は [Either ParseError String] です。これを展開するために、 Prelude の either を用いましょう。 either は2つ関数を取り、 Left の場合は最初の関数を適用、 Right の場合は2つ目の関数を適用する関数です。取り扱うものが Either のリストなので、 either もマッピングする必要があります。 ParseError は Show クラスのインスタンスなので、どちらのケースでも単純に関数 print を使って印字することにしましょう。

main = do
	file <- readFile "logfile.txt"
	let logLines = lines file
	result <- mapM (parse line "(test)") logLines
	mapM_ (either print print) result

できました!このスクリプトはパーサの各結果、エラーまたはデータ型 LogLine を印字します。

あまり努力してもいないのにもかかわらず、他言語ではなかなか難しいことを、このスクリプトは少ないメモリで実現します!遅延評価のマジックの恩恵により、各行は読まれ、パースされ、印字され、ガベージコレクションされます。とは言っても、これはあまり効率のいい実装ではないので、もっと最適化してみましょう。