人気ブログランキング | 話題のタグを見る

Parsec 再入門 Parser と ParserCombinator

Parsec についての詳しい文書は、Parsec のホームページの Parsec documentation から pdf をダウンロードできる。

膨大な仕様に圧倒されてしまうが、アマチュアが Parsec を便利に使うために必要な要件をまとめてみたい。くわしいことはいいから、手っ取り早く使うにはどうしたらいいのかということだ。

前回の記事でも述べたように、Parsec のプログラミングで最も重要なのは、文字列のパターンを記述することだ。そのパターンを記述するには、Parsec の3つの要素を把握しておけばいい。

その3つの要素とはパーサー、パーサーコンビネータ、連接と選択だ。パーサーは文字列の先頭から検査してパターンが一致するかどうかを調べる関数。パーサーコンビネータはそのパーサーを引数にとり、複雑なパターンを作る高階関数、連接と選択は、パーサーの組み合わせを作る方法だ。

これらで、作ったパターンは単独では使用できず、parse 関数の引数として使われることで機能を発揮する。

まずは、パーサーだ。Parsec にはあらかじめ定義された多数のパーサーがある。そのうち、よく使いそうなものをピックアップしてみる。全貌は上に紹介した文書を参照してほしい。

これらのパーサーの動作は、ghci 上で確かめるので、まず準備。
Prelude> :m Text.ParserCombinators.Parsec
Prelude Text.ParserCombinators.Parsec>

1. パーサー

パーサーはパターンの基本的な単位で、文字列とマッチする基本的なパターンを表している。Parsec にはあらかじめ定義された多数のパーサーがある。そのうち、よく使いそうなものをピックアップしてみる。全貌は上に紹介した文書を参照してほしい。

char パーサー: 一文字とマッチするパーサー。日本語もOK。
Prelude Text.ParserCombinators.Parsec> parse (char 'h') "" "hello"
Right 'h'
Prelude Text.ParserCombinators.Parsec> parse (char 'お') "" "おはよう"
Right '\12362'

string パーサー: 文字列とマッチするパーサー。
Prelude Text.ParserCombinators.Parsec> parse (string "hello") "" "hello, world"
Right "hello"

onOf パーサー: 引数の文字列のうちのどれか1文字とマッチする。
Prelude Text.ParserCombinators.Parsec> parse (oneOf "abcdefg") "" "egg"
Right 'e'

noneOf パーサー: 引数の文字列のどれでもない1文字とマッチする。
Prelude Text.ParserCombinators.Parsec> parse (noneOf "abcdefg") "" "hello"
Right 'h'

anyChar パーサー: 文字列のどんな1文字にもマッチする。
Prelude Text.ParserCombinators.Parsec> parse anyChar "" "+One"
Right '+'

upper パーサー: 文字列の先頭の大文字とマッチする。
Prelude Text.ParserCombinators.Parsec> parse upper "" "Orange"
Right 'O'

lower パーサー: 文字列の先頭の小文字とマッチする。
Prelude Text.ParserCombinators.Parsec> parse lower "" "dog"
Right 'd'

letter パーサー: 数字や記号ではない文字とマッチする。
Prelude Text.ParserCombinators.Parsec> parse letter "" "hello, world"
Right 'h'
Prelude Text.ParserCombinators.Parsec> parse letter "" "123"
Left (line 1, column 1):
unexpected "1"

alphaNum パーサー: 文字と数字にマッチする。
Prelude Text.ParserCombinators.Parsec> parse alphaNum "" "hello"
Right 'h'
Prelude Text.ParserCombinators.Parsec> parse alphaNum "" "おはよう"
Right '\12362'
Prelude Text.ParserCombinators.Parsec> parse alphaNum "" "123"
Right '1'
Prelude Text.ParserCombinators.Parsec> parse alphaNum "" "+One"
Left (line 1, column 1):
unexpected "+"
expecting letter or digit

digit パーサー: 数字 [0-9] にマッチする。
Prelude Text.ParserCombinators.Parsec> parse digit "" "123"
Right '1'

hexDigit パーサー: 16進数 [0-9a-f] にマッチする。
Prelude Text.ParserCombinators.Parsec> parse hexDigit "" "ff"
Right 'f'

octDigit パーサー: 8進数 [0-7] にマッチする。
Prelude Text.ParserCombinators.Parsec> parse octDigit "" "777"
Right '7'

newline パーサー: 改行 '¥n' にマッチする。
Prelude Text.ParserCombinators.Parsec> parse newline "" "\n"
Right '\n'

tab パーサー: tab にマッチする。
Prelude Text.ParserCombinators.Parsec> parse tab "" "\t"
Right '\t'

space パーサー: 空白文字 " \v\f\t\r\n" のいずれかにマッチする。
Prelude Text.ParserCombinators.Parsec> parse space "" "\t"
Right '\t'

spaces パーサー: 複数の空白文字を消費するだけのパーサー。
Prelude Text.ParserCombinators.Parsec> parse spaces "" " hello"
Right ()

消費するという用語は Parsec でよく使われる。parse 関数の第3引数はパースされる文字列だが、プログラムには現れない状態 t というバッファにコピーされる。パーサーのマッチが起きると、バッファの先頭のマッチした部分が取り除かれ、次のパーサーに引き渡される。プログラムの表面には出てこないので注意が必要だ。

satisfy パーサー: 引数の条件判断関数が真になる場合にマッチするパーサー。
Prelude Text.ParserCombinators.Parsec> :m + Data.Char
Prelude Text.ParserCombinators.Parsec Data.Char> parse (satisfy isDigit) "" "123"
Right '1'

eof パーサ: EOF にマッチする。
Prelude Text.ParserCombinators.Parsec> parse eof "" ""
Right ()

2. パーサーコンビネータ

パーサーコンビネータは上に述べたパーサーを組み合わせて複雑なパターンを作る高階関数だ。

many コンビネータ: many の引数のパターンの0個以上のくりかえしにマッチする。
Prelude Text.ParserCombinators.Parsec Data.Char> parse (many (char 'o')) "" "oopse"
Right "oo"

many1 コンビネータ: many1 の引数のパターンの1個以上のくりかえしにマッチする。
Prelude Text.ParserCombinators.Parsec Data.Char> parse (many1 (string "foo")) "" "foofoobar"
Right ["foo","foo"]

skipMany コンビネータ: skipMany の引数のパターンの繰り返し部分を消費する。
Prelude Text.ParserCombinators.Parsec Data.Char> parse (skipMany (string "foo")) "" "foofoobar"
Right ()

マッチした部分は状態バッファから消費され読み捨てられる。したがって、do 構文でバッファのが次のパーサーに渡されると。読み捨てられた部分の後の文字列が次のパーサーで処理される。
Prelude Text.ParserCombinators.Parsec Data.Char> parse (do skipMany(string "foo"); string "bar") "" "foofoobar"
Right "bar"

skipMany1 コンビネータ: skipMany の引数の1回以上の繰り返しを消費する。
Prelude Text.ParserCombinators.Parsec Data.Char> parse (do skipMany(string "foo"); string "bar") "" "foofoobar"
Right "bar"

notFollowedBy コンビネータ: notFollowedBy の引数のパターンにマッチしない場合にマッチが起きる。マッチしても状態バッファの消費は起こらない。
Prelude Text.ParserCombinators.Parsec Data.Char> parse (notFollowedBy (string "foo")) "" "foobar"
Left (line 1, column 4):
unexpected "foo"
Prelude Text.ParserCombinators.Parsec Data.Char> parse (notFollowedBy (string "bar")) "" "foobar"

3. 連接と選択

パーサーコンビネータはパーサのパターンの繰り返しに関するものが多かったが、パターンの合成は連接と選択の書式で行う。

連接つまり、パターン1とパターン2が続いて起きる場合のパターンの表記は、単に do 構文のなかにパーサを続けて書くだけだ。これは、パーサーが Parser モナドの関数なので可能になっている。パーサーがモナドなので、パーサーの戻り値は、IO モナドと同じ <- 演算子で取り出すことができるので、パターンマッチが起きたときのアクションも do 構文の中で記述できる。

しかし、話が複雑になるので、ここでは単に、パターンの連結は do 構文の中に記述すると理解しておけばいい。

Prelude Text.ParserCombinators.Parsec Data.Char> parse (do string "foo"; string "bar") "" "foobarbuz"
Right "bar"

ここで注意しておかないといけないのは、parse の戻り値が最後に評価された string "bar" のものだということだ。戻り値に "foobar" を得たいときは、パターンマッチの度にパーサーの戻り値を IO モナドの要領で取り出して、最後に return 関数で返す必要がある。

Prelude Text.ParserCombinators.Parsec Data.Char> parse (do as <- string "foo"; bs <- string "bar"; return (as ++ bs )) "" "foobarbuz"
Right "foobar"

簡単なテクニックだが、パターンマッチが起きたときのアクションをプログラムするときの基本的なテクニックになる。

選択は <|> 演算子で行う。

Prelude Text.ParserCombinators.Parsec Data.Char> parse (string "foo" <|> string "bar") "" "barfoobuz"
Right "bar"

4. try

パターンの選択を使うとき、パーサーが複合パターンでできているときは、バッファの一部が消費され次のパターンマッチに支障が起きることがある。

例えば下の例では最初のパターンで 'f' がマッチするためにバッファの消費が起きる。最初のパターンマッチは char 'a' で失敗し、選択演算子 <|> で次のパターンマッチが行われるが、状態バッファの先頭が 'a' になっているために、後半のパターンマッチも失敗してしまう。

エラーメッセージでは、最初のパターンマッチの失敗しか報告されないため、バグの原因が見つけにくい。

Prelude Text.ParserCombinators.Parsec Data.Char> parse ((do char 'f'; char 'a') <|> (do char 'f'; char 'o')) "" "foobar"
Left (line 1, column 2):
unexpected "o"
expecting "a"

こういう場合は、最初の複合パターンに try 関数を適用しておくと、最初の複合パターンのマッチが失敗した場合でも、状態バッファでの消費が起きないようにできるのでこのような不都合を解消できる。

Prelude Text.ParserCombinators.Parsec Data.Char> parse (try (do char 'f'; char 'a') <|> (do char 'f'; char 'o')) "" "foobar"
Right 'o'

Parsec のパーサーのパターンの作り方は、これまでの知識で簡単なものは十分実用的に作ることができると思うが、冒頭に述べた文書にはさらに便利なコンビネータが解説されている。
by tnomura9 | 2013-01-03 10:08 | Haskell | Comments(0)
<< Parsec 再入門 Pars... Parsec 再入門 pars... >>