LoginSignup
4

More than 5 years have passed since last update.

Parsecのソースちら見

Posted at

教科書的なパーサーと言えばStateT s []モナドをよく見るけど、今のParsecって全然そんな雰囲気ないんだなあ。
https://twitter.com/hiratara/status/297541496217927683

モナド本体は継続モナド×4的な構造をしている。継続となる関数を4本渡せば、結果を得ることができる。

Text-Parsec-Prim.html
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
             }

起動用に用意されている関数では、最終的にどの継続を経由して結果を得たのかわかるようにラップをしている。ラップは各2項目×2段階。

Text-Parsec-Prim.html
runParsecT :: Monad m => ParsecT s u m a -> State s u -> m (Consumed (m (Reply s u a)))
runParsecT p s = unParser p s cok cerr eok eerr
    where cok a s' err = return . Consumed . return $ Ok a s' err
          cerr err = return . Consumed . return $ Error err
          eok a s' err = return . Empty . return $ Ok a s' err
          eerr err = return . Empty . return $ Error err

ラップの1段階目。パーサが入力を消費したか否か。

Text-Parsec-Prim.html
data Consumed a  = Consumed a
                 | Empty !a

ラップの2段階目。パースが成功したか否か。これで2*2=4通りのパターンを表せた。

Text-Parsec-Prim.html
data Reply s u a = Ok a !(State s u) ParseError
                 | Error ParseError

逆にこのラップされた型からParsecT型を復元する関数も定義されている。ラップされた型を展開して、4つ渡された継続のどれをキックするか判別するだけ。

Text-Parsec-Prim.html
mkPT :: Monad m => (State s u -> m (Consumed (m (Reply s u a)))) -> ParsecT s u m a
mkPT k = ParsecT $ \s cok cerr eok eerr -> do
           cons <- k s
           case cons of
             Consumed mrep -> do
                       rep <- mrep
                       case rep of
                         Ok x s' err -> cok x s' err
                         Error err -> cerr err
             Empty mrep -> do
                       rep <- mrep
                       case rep of
                         Ok x s' err -> eok x s' err
                         Error err -> eerr err

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4