Parsec 入門


Parsec 連接と選択

Text.Parsec.Char に記述されていたような要素的なパーサは、組み合わせることで様々な複雑なパーサを組み立てることができる。

パーサがモナドなので、レゴブロックを組み立てるような感じで複雑なパーサを作り出すことができるが、Parsec を学ぶ上でそのような組み立てかたのパターンを知っていると便利だ。パターンには色々あるが、連接、選択、繰り返し、再帰などに分類すると分かりやすい。今回はそのうちの連接と選択について見てみる。

連接

連接というのはパーサAのあとにパーサBと言うようにパーサを直列に並べて新しいパターンを作ることだ。これは、パーサがモナドなので do 記法の中に並べるだけでいい。たとえば、char 'a' と char 'b' というパターンに対応するパーサを作りたいとする。このとき、do char 'a'; char 'b' のようにする。

Prelude Text.Parsec> parseTest (do char 'a'; char 'b') "abc"
'b'

パターンマッチの結果が 'b' になっているが、連接の場合は最後のバーサの値が戻されるからだ。"ab" を返したいときは do 記法の性質を利用して do x <- char 'a'; y <- char 'b'; return (x:y:[]) の様にすれば良い。

Prelude Text.Parsec> parseTest (do x <- char 'a'; y <- char 'b'; 
return (x:y:[])) "abc"
"ab"

このような、do 記法のモナドプログラムは新しいパターンとして定義できる。

Prelude Text.Parsec> ab = do x <- char 'a'; y <- char 'b'; 
(return ([x]++[y])) :: Parsec String () String
Prelude Text.Parsec> parseTest ab "abc"
"ab"

ab の定義の最後の (return .. ) の型指定の Parsec String () String だが、Parsec モナドの型シグネチャーだ。Parsec s u a の本体は ParsecT s u m a で Parsec3 の Parsec モナドは複合モナド化されている。ParsecT のそれぞれの型パラメータの意味は、次のようになる。

ParsecT s u m a s : stream type (String, ByteString, Text のどれか) u : user state type (ユーザが使用できる状態の型、状態を使わないときは () を指定する) m : underlying monad (StateT 複合モナドの内部のモナド、型指定に Parsec s u a を使うときは Identity モナドに指定されている) a : return type (return 関数で戻されるデータの型)

ユーザが使用できる状態があるので、パターンマッチのときのアクションで状態を利用できる。また、StateT が複合モナド化されているので、パーサのなかで、liftIO $ print a の様に print デバッグができそう。型の定義が複雑になった分使い勝手がよさそうだ。

連接は1文字のパーサだけでなく、String のパーサや、ユーザ定義のパーサにも使える。

Prelude Text.Parsec> parseTest (do ab; string "foo") 
"abfoo"
"foo"

選択

<|> で連結されたパーサは、どちらかのパーサがマッチしたときにマッチと判断される。

Prelude Text.Parsec> parseTest (string "foo" <|> string "bar") "foo buz" "foo"

これも新しいパーサとして定義できる。

Prelude Text.Parsec> foobar = string "foo" <|> (string 
"bar") :: Parsec String () String
Prelude Text.Parsec> parseTest foobar "foo buz"
"foo"

パーサの連接と選択が使えるようになればパースできる文の範囲が広がる。次の add パーサは数式を計算してその値を返す。

Prelude Text.Parsec> add = do x <- many digit; 
char '+'; y <- many digit; (return ((read x :: Int) + (read y :: Int)))
:: Parsec String () Int
Prelude Text.Parsec> parseTest add "12+34"
46

many digit の many はパターンマッチの繰り返しを記述するパーサコンビネータ(パーサを引数とする関数)だが、それについては次回に述べる。