Text.Parsec.Combinator

Text.Parsec のソースコード探索も Text.Parsec.Combinator モジュールを調べたら、その心臓部の解析は終わりだ。このモジュールには、たくさんのコンビネータが定義されているが、その殆どは do 記法によるモナドプログラミングだ。したがって、格段に解読が楽になる。ソースコードの解読が楽なので、コンビネータの動作を確認するには文書を読むよりソースコードを読んだほうが良いという逆転現象がおきている。

choice コンビネータ

choice :: (Stream s m t) => [ParsecT s u m a] -> ParsecT s u m a
choice ps = foldr (<|>) mzero ps

choice コンビネータはパーサのリスト ps を引数にとり、先頭からマッチングを行ってマッチングが成功した時点でマッチングの結果を返すパーサを作る。foldr を <|> 演算子に適用しているので、パターンマッチがリストの左端から順に行われる。

Prelude Text.Parsec> parseTest (choice [letter, digit]) "123"
'1'
Prelude Text.Parsec> parseTest (choice [string "foo", string "bar"]) "bar"
"bar"

option コンビネータ

option :: (Stream s m t) => a -> ParsecT s u m a -> ParsecT s u m a
option x p = p <|> return x

option コンビネータは option x p でパーサ p のパターンマッチが失敗したときにデフォールト値 x を返すパーサを作る。

Prelude Text.Parsec> parseTest (option "hello" (string "foo")) "bar"
"hello"

optionMaybe コンビネータ

optionMaybe :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m (Maybe a)
optionMaybe p = option Nothing (liftM Just p)

optionMaybe コンビネータは optionMaybe p でパターンマッチの戻り値を Maybe モナドにラッピングして返す。

Prelude Text.Parsec> parseTest (optionMaybe letter) "123"
Nothing
Prelude Text.Parsec> parseTest (optionMaybe letter) "foo"
Just 'f'

optional コンビネータ

optional :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m ()
optional p = do{ _ <- p; return ()} <|> return ()

optional コンビネータは optional p でパーサ p がパターンマッチを成功してもしなくても () を返すパーサを作る。

Prelude Text.Parsec> parseTest (optional letter) "foo"
()
Prelude Text.Parsec> parseTest (optional letter) "123"
()

パターンマッチが消費を伴う場合消費のみを行うことになる。

Prelude Text.Parsec> parseTest (optional letter *> getInput) "foo"
"oo"

between コンビネータ

between :: (Stream s m t) => ParsecT s u m open -> ParsecT s u m close
            -> ParsecT s u m a -> ParsecT s u m a
between open close p
                    = do{ _ <- open; x <- p; _ <- close; return x }

between コンビネータは between open close p で open パターンと close パターンに挟まれた部分が p パターンにマッチした場合にそれを取り出すパーサを作る。言葉で説明するより、ソースコードを読んだほうが分かりやすい。

Prelude Text.Parsec> parseTest (between (char '{') (char '}') (many letter))
 "{foo}"
"foo"

skipMany1 コンビネータ

skipMany1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m ()
skipMany1 p         = do{ _ <- p; skipMany p }

skipMany1 コンビネータは skipMany1 p でパーサ p にマッチする部分を１回以上の繰り返しで読み飛ばすパーサを作る。最初に p パーサのパターンマッチを行った後、skipMany コンビネータでパターン p の０回以上の繰り返しにマッチするパーサを作る。

Prelude Text.Parsec> parseTest (skipMany (char 'a') *> getInput) "aaaaaabc"
"bc"

many1 コンビネータ

many1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m [a]
many1 p = do{ x <- p; xs <- many p; return (x:xs) }

many1 コンビネータは many1 p でパターン p の１回以上の繰り返しにマッチするパーサを作る。

Prelude Text.Parsec> parseTest (many1 (char 'a')) "aaaaaabc"
"aaaaaa"

sepBy コンビネータ

sepBy :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m sep -> ParsecT
 s u m [a]
sepBy p sep = sepBy1 p sep <|> return []

sepBy コンビネータは sepBy p sep でセパレータ sep で区切られた０個以上の p パターンのリストを返すパーサを作る。内部的に sepBy1 コンビネータを利用している。

Prelude Text.Parsec> parseTest (sepBy (many letter) (char ',')) "foo,bar"
["foo","bar"]

sepBy1 コンビネータ

sepBy1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m sep -> ParsecT
 s u m [a]
sepBy1 p sep        = do{ x <- p
                        ; xs <- many (sep >> p)
                        ; return (x:xs)
                        }

sepBy1 コンビネータは sepBy1 p sep でセパレータ sep で区切られた１個以上のパターン p にマッチするものリストを作る。パーサを作る。do 記法で定義されており、最初にパターンマッチを行い、続いて many (sep >> p) でパターンマッチを繰り返している。

Prelude Text.Parsec> parseTest (sepBy1 (many letter) (char ',')) "foo,bar"
["foo","bar"]

sepEndBy1 コンビネータ

sepEndBy1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m sep -> ParsecT
 s u m [a]
sepEndBy1 p sep     = do{ x <- p
                        ; do{ _ <- sep
                            ; xs <- sepEndBy p sep
                            ; return (x:xs)
                            }
                          <|> return [x]
                        }

sepEndBy1 コンビネータは sepEndby1 p sep でパターン p をパターンに続くのセパレータできりわけパターンのリストにして返すパーサを作る。sepEndBy1 コンビネータのプログラムは do 記法で記述されている。最初に p のパターンマッチを行い、その後にセパレータ sp のパターンマッチを行っている。最初のパターンマッチのリターン値 x は sepEndBy1 の recursive case の戻り値 xs と (x:xs) で連結されて return 関数で返される。base case がないが、パターンマッチエラー時の return [x] がその役割を果たしている。

Prelude Text.Parsec> parseTest (sepEndBy1 (many letter) (char ';')) "foo;bar;"
["foo","bar",""]
Prelude Text.Parsec> parseTest (sepEndBy1 (many letter) (char ';')) "foo;bar"
["foo","bar"]

sepEndBy コンビネータ

sepEndBy :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m sep -> ParsecT
 s u m [a]
sepEndBy p sep = sepEndBy1 p sep <|> return []

sepEndBy コンビネータは、sepEndBy p sep で最初からパターンマッチが失敗した場合も [] を返すパーサを作る。

Prelude Text.Parsec> parseTest (sepEndBy (many letter) (char ';')) "123"
[""]

endBy1 コンビネータ

endBy1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m sep -> ParsecT
 s u m [a]
endBy1 p sep        = many1 (do{ x <- p; _ <- sep; return x })

endBy1 コンビネータは endBy1 p sep で末尾を sep で区切られたパターン p を取り出して、配列にして返すパーサを作る。

Prelude Text.Parsec> parseTest (endB1y (many letter) (char ';')) "foo;bar;"
["foo","bar"]

endBy コンビネータ

endBy :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m sep -> ParsecT s
 u m [a]
endBy p sep         = many (do{ x <- p; _ <- sep; return x })

endBy コンビネータは、パターンマッチが１回も起きなかった場合も動作する。

Prelude Text.Parsec> parseTest (endBy (many letter) (char ';')) "123"
[]

count コンビネータ

count :: (Stream s m t) => Int -> ParsecT s u m a -> ParsecT s u m [a]
count n p           | n <= 0    = return []
                    | otherwise = sequence (replicate n p)

count コンビネータは count n p でパターン p の n 回の繰り返しにマッチする。ソースコードではパーサ p の n 個の配列を作り、sequence で実行している。

Prelude Text.Parsec> parseTest (count 2 (string "foo")) "foofoobar"
["foo","foo"]

replicate 関数、sequence 関数の動作は次のようになる。

Prelude Text.Parsec> sequence (replicate 3 (putStrLn "hello"))
hello
hello
hello
[(),(),()]

chainl1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m (a -> a -> a) ->
 ParsecT s u m a
chainl1 p op        = do{ x <- p; rest x }
                    where
                      rest x    = do{ f <- op
                                    ; y <- p
                                    ; rest (f x y)
                                    }
                                <|> return x

chainl1 p op 関数は連続する左結合の２項演算 (1 + 2 + 3 など）の演算をパターンマッチで行うパーサを記述する。chainl1 のパーサ p のリターン値は数値を、op パーサのリターン値は２項演算にする必要がある。演算の繰り返しは rest が再帰関数なので実現できる。

Prelude Text.Parsec> parseTest (chainl1 (do x <- many1 digit; return ((read ::
 String -> Int) x)) (do char '+'; return (+))) "1+2+3"
6

chainr1 コンビネータ

chainr1 コンビネータは連続する右結合の２項演算 (1^2^3) などの演算をパターンマッチで行うパーサを記述する。chainr1 p op の引数の意味は chainrl のものと同じだが、再帰関数 scan の定義の仕方が異なる。

chainr1 :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m (a -> a -> a) ->
 ParsecT s u m a
chainr1 p op        = scan
                    where
                      scan      = do{ x <- p; rest x }

                      rest x    = do{ f <- op
                                    ; y <- scan
                                    ; return (f x y)
                                    }
                                <|> return x

chainl コンビネータ

chainl :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m (a -> a -> a) ->
 a -> ParsecT s u m a
chainl p op x       = chainl1 p op <|> return x

chainl コンビネータは chainl1 コンビネータと同じように連続する２項演算の値を計算するが、２項演算がない場合はデフォールト値の x を返す。

Prelude Text.Parsec> parseTest (chainl (do x <- many1 digit; return ((read ::
 String -> Int) x)) (do char '+'; return (+)) 0) "foo"
0

chainr コンビネータ

chainr :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m (a -> a -> a) -> a
 -> ParsecT s u m a
chainr p op x       = chainr1 p op <|> return x

chainr コンビネータは連続する左結合の２項演算に対応しているが、２項演算がないときデフォールト値の x を返す。

anyToken パーサ

anyToken :: (Stream s m t, Show t) => ParsecT s u m t
anyToken            = tokenPrim show (\pos _tok _toks -> pos) Just

anyToken パーサはトークン（文字など）がない状態にマッチする。notFollwedBy コンビネータに利用されている。

Prelude Text.Parsec> parseTest anyToken "hello"
'h'

eof パーサ

eof :: (Stream s m t, Show t) => ParsecT s u m ()
eof                 = notFollowedBy anyToken <?> "end of input"

eof は input の終了にマッチする。

Prelude Text.Parsec> parseTest eof ""
()

notFollowedBy コンビネータ

notFollowedBy :: (Stream s m t, Show a) => ParsecT s u m a -> ParsecT s u m ()
notFollowedBy p     = try (do{ c <- try p; unexpected (show c) }
                           <|> return ()

notoFollowedBy コンビネータは次の input を空読みして、それがパターン p でなければパターンマッチと判断するパーサを作る。

Prelude Text.Parsec> parseTest (notFollowedBy digit) "123"
parse error at (line 1, column 2):
unexpected '1'
Prelude Text.Parsec> parseTest (notFollowedBy letter) "123"
()

manyTill コンビネータ

manyTill :: (Stream s m t) => ParsecT s u m a -> ParsecT s u m end ->
 ParsecT s u m [a]
manyTill p end      = scan
                    where
                      scan  = do{ _ <- end; return [] }
                            <|>
                              do{ x <- p; xs <- scan; return (x:xs) }

manyTill p コンビネータは manyTill p end で end パターンが来るまでパターン p のマッチングを行うパーサを作る。

Prelude Text.Parsec> parseTest (manyTill letter (char 'Z')) "abcdefZhijk"
"abcdef"

parsarTreace コンビネータ

デバッグ関係の関数で Debug.Trace モジュールの知識がないとわからないので省略。（宿題）

parserTraced コンビネータ

同上

Text.Parsec.Combinator モジュールのコンビネータのソースコードを一通り見てみた。モナドプログラミングで書かれているのでコンビネータの動作を知るためには、Hackage のソースコードを参照するのが一番はやいようだ。

Text.Parsec モジュールを活用するためのソースコード解読はこれで一旦終了とする。何も知らない状態からの解読との同時進行的な記事だったので整理されていないが、力尽きたのでこれでやめる。