many パーサコンビネータ

many パーサコンビネータは、引数のバーサの０または複数回の繰り返しをパースする。

Prelude> :m Text.Parsec
Prelude Text.Parsec> identifier = do {c <- letter; cs <- many (alphaNum
 <|> char '_'); return (c:cs)} :: Parsec String () String
Prelude Text.Parsec> parseTest identifier "he_llo, world"
"he_llo"

many のソースコードは次のようになる。

many :: ParsecT s u m a -> ParsecT s u m [a]
many p
  = do xs <- manyAccum (:) p
       return (reverse xs)

manyAccum 関数

many は manyAccum 関数を使って定義されている。manyAccum 関数をテストしてみた。

Prelude Text.Parsec> parseTest (manyAccum (:) letter) "foo bar"
"oof"

foo がひっくり返っている。

manyAccum 関数の定義は次のようになる。

manyAccum :: (a -> [a] -> [a])
          -> ParsecT s u m a
          -> ParsecT s u m [a]
manyAccum acc p =
    ParsecT $ \s cok cerr eok _eerr ->
    let walk xs x s' _err =
            unParser p s'
              (seq xs $ walk $ acc x xs)  -- consumed-ok
              cerr                        -- consumed-err
              manyErr                     -- empty-ok
              (\e -> cok (acc x xs) s' e) -- empty-err
    in unParser p s (walk []) cerr manyErr (\e -> eok [] s e)

manyErr :: a
manyErr = error "Text.ParserCombinators.Parsec.Prim.many: combinator
 'many' is applied to a parser that accepts an empty string."

acc 関数

manyAccum acc p の acc は関数だ。many に利用されるときは acc = (:) なので置き換えてみる。

manyAccum (:) p =
    ParsecT $ \s cok cerr eok _eerr ->
    let walk xs x s' _err =
            unParser p s'
              (seq xs $ walk $ (:) x xs)  -- consumed-ok
              cerr                        -- consumed-err
              manyErr                     -- empty-ok
              (\e -> cok ((:) x xs) s' e) -- empty-err
    in unParser p s (walk []) cerr manyErr (\e -> eok [] s e)

置き換えてもよくわからないコードだ。

walk 関数と cok 関数

そこで、(unParser p) 関数の振る舞いを考えてみる。unParser アクセサで取り出されるパーサ p のフィールドの無名関数の動作は、ParsecT s u m a パーサの型を見れば分かる。

newtype ParsecT s u m a
   = ParsecT {unParser :: forall b .
     State s u
     -> (a -> State s u -> ParseError -> m b) -- consumed ok
     -> (ParseError -> m b) -- consumed err
     -> (a -> State s u -> ParseError -> m b) -- empty ok
     -> (ParseError -> m b) -- empty err
     -> m b
     }

State型の値を s, Char 型の値を a, ParseError 型の値を e と置くと、ParsecT パーサ p の unParser フィールドの関数は次のようになる。

(unParser p) s cok cerr eok eerr

(unParser p) による s に対するパターンマッチが成功した場合 cok a s e が実行される。manyAccum の場合

cok = (seq xs $ walk $ (:) x xs)

だ。seq は xs を正格評価するということだから実質的には、

cok = walk (x:xs) s a e

ということになる。すなわち、(unParser p) のマッチが行われ成功したときの State を s', リターン値を a', ParseError を e' とすると、cok として実行される関数は

walk xs s' a' e'

ということになり、walk 関数が再帰的に実行されることが分かる。また、再帰的な実行のたびにリスト xs にはリターン値が積み増されていく。

eerr 関数

(unParser p) 関数のパターンマッチが失敗した場合は eerr が実行される。manyAccum 関数の場合、

eerr = (\e -> cok ((:) x xs) s' e)

だ。これは cok (x:xs) s' e によって値がモナド値にラッピングされて返される。

(unParser p) のパターンマッチのときの cok と eok の違い、cerr と eerr の違いがはっきりとは理解できていないので詳しいコメントができないが、少なくとも many パーサコンビネータの再帰関数の中心部が walk 関数であることが分かる。

skipMany 関数

sikpMany p 関数はパーサ p にマッチする文字列を無視する作用があるが、これも manyAccum 関数が利用されている。

-- | @skipMany p@ applies the parser @p@ /zero/ or more times, skipping
-- its result.
--
-- >  spaces  = skipMany space

skipMany :: ParsecT s u m a -> ParsecT s u m ()
skipMany p
  = do _ <- manyAccum (\_ _ -> []) p
       return ()

manyAccum 関数に渡される acc 関数は acc = \_ _ -> [] だからパターンマッチの戻り値にかかわらず、xs = [] になる。