在Haskell中合并解析器 [英] Combining parsers in Haskell

问题描述

我得到了以下解析器

newtype Parser a = Parser { parse :: String -> Maybe (a,String) }

instance Functor Parser where
   fmap f p = Parser $ \s -> (\(a,c) -> (f a, c)) <$> parse p s

instance Applicative Parser where
   pure a = Parser $ \s -> Just (a,s)
   f <*> a = Parser $ \s ->
     case parse f s of
       Just (g,s') -> parse (fmap g a) s'
       Nothing -> Nothing

instance Alternative Parser where
   empty = Parser $ \s -> Nothing
   l <|> r = Parser $ \s -> parse l s <|> parse r s

 ensure :: (a -> Bool) -> Parser a -> Parser a
 ensure p parser = Parser $ \s ->
    case parse parser s of
      Nothing -> Nothing
      Just (a,s') -> if p a then Just (a,s') else Nothing

 lookahead :: Parser (Maybe Char)
 lookahead = Parser f
   where f [] = Just (Nothing,[])
         f (c:s) = Just (Just c,c:s)

 satisfy :: (Char -> Bool) -> Parser Char
 satisfy p = Parser f
   where f [] = Nothing
         f (x:xs) = if p x then Just (x,xs) else Nothing

 eof :: Parser ()
 eof = Parser $ \s -> if null s then Just ((),[]) else Nothing

 eof' :: Parser ()
 eof' = ???

我需要编写一个新的解析器eof'，其功能与eof完全相同，但是仅使用给定的解析器和 上面的Functor/Applicative/Alternative实例.由于没有解析器组合方面的经验，我一直坚持这一点.谁能帮我吗 ?

I need to write a new parser eof' that does exactly what eof does but is built only using the given parsers and the Functor/Applicative/Alternative instances above. I'm stuck on this as I don't have experience in combining parsers. Can anyone help me out ?

推荐答案

要更容易理解，我们可以使用等式伪代码编写它，同时使用Monad Comprehensions来简化和定义，以简化和定义.

To understand it easier, we can write it in an equational pseudocode, while we substitute and simplify the definitions, using Monad Comprehensions for clarity and succinctness.

Monad推导和列表推导一样，仅适用于任何MonadPlus类型，而不仅适用于[].而与do表示法非常接近，例如[ (f a, s') | (a, s') <- parse p s ] === do { (a, s') <- parse p s ; return (f a, s') }.

Monad Comprehensions are just like List Comprehensions, only working for any MonadPlus type, not just []; while corresponding closely to do notation, e.g. [ (f a, s') | (a, s') <- parse p s ] === do { (a, s') <- parse p s ; return (f a, s') }.

这使我们:

newtype Parser a = Parser { parse :: String -> Maybe (a,String) }

instance Functor Parser where
   parse (fmap f p)  s  =  [ (f a, s') | (a, s') <- parse p s ]

instance Applicative Parser where
   parse (pure a)    s  =  pure (a, s)
   parse (pf <*> pa) s  =  [ (g a, s'') | (g, s')  <- parse pf s 
                                        , (a, s'') <- parse pa s' ]

instance Alternative Parser where
   parse empty s      =  empty
   parse (l <|> r) s  =  parse l s <|> parse r s

ensure :: (a -> Bool) -> Parser a -> Parser a
parse (ensure pred p) s  =  [ (a, s') | (a, s') <- parse p s, pred a ]

lookahead :: Parser (Maybe Char)
parse lookahead []       =  pure (Nothing, [])
parse lookahead s@(c:_)  =  pure (Just c,  s )

satisfy :: (Char -> Bool) -> Parser Char
parse (satisfy p) []      =  mzero
parse (satisfy p) (x:xs)  =  [ (x, xs) | p x ]

eof :: Parser ()
parse eof s  =  [ ((), []) | null s ]  

eof' :: Parser ()
eof'  =  ???

顺便说一句，由于使用了Monad Comprehensions和更抽象的pure，empty和mzero，而不是根据Maybe类型的具体表示，该相同(伪)代码将使用其他类型，如[]代替Maybe，即. newtype Parser a = Parser { parse :: String -> [(a,String)] }.

By the way thanks to the use of Monad Comprehensions and the more abstract pure, empty and mzero instead of their concrete representations in terms of the Maybe type, this same (pseudo-)code will work with a different type, like [] in place of Maybe, viz. newtype Parser a = Parser { parse :: String -> [(a,String)] }.

所以我们有

ensure    :: (a -> Bool) -> Parser a           -> Parser a
lookahead ::                Parser (Maybe Char)

_{(satisfy在这里对我们没有好处....为什么?)}

_{(satisfy is no good for us here .... why?)}

使用它，我们可以拥有

ensure  .......  ......                        :: Parser (Maybe Char)

_{(... ensure id (pure False)做什么?...)}

，但是如果输入字符串实际上为空，我们将得到一个无用的Nothing结果，而在这种情况下，赋予使用的eof解析器将生成()作为其结果(否则它将不产生任何结果) ).

but we'll have a useless Nothing result in case the input string was in fact empty, whereas the eof parser given to use produces the () as its result in such case (and otherwise it produces nothing).

不用担心，我们也有

fmap :: (  a      ->   b )                     -> Parser a        ->  Parser b

可以将Nothing转换为().我们需要一个始终为我们做到这一点的功能，

which can transform the Nothing into () for us. We'll need a function that will always do this for us,

alwaysUnit nothing  =  ()

我们现在可以使用它来找到解决方案:

which we can use now to arrive at the solution:

eof'  =  fmap ..... (..... ..... ......)

这篇关于在Haskell中合并解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！