在 Haskell 中组合解析器

Question

我得到了以下解析器

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 例以上。我一直坚持这一点，因为我没有组合解析器的经验。谁能帮我吗？

Answer 1

为了更容易理解，我们可以用等式伪代码编写它，同时我们使用 Monad Comprehensions 替换和简化定义，以求清晰和简洁。

Monad Comprehensions 就像 List Comprehensions 一样，只适用于任何 MonadPlus 类型，而不仅仅是 []；同时与 do 符号紧密对应，例如[ (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 (<b>fmap f p</b>)  s  =  [ (f a, s') | (a, s') <- parse p s ]

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

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

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

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

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

eof :: Parser ()
parse <b>eof</b> s  =  [ ((), []) | null s ]  

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

顺便说一句，多亏了 Monad Comprehensions 的使用和更抽象的 pure、empty 和 mzero 而不是它们在 Maybe 方面的具体表示类型，这个相同的（伪）代码将适用于不同的类型，比如 [] 代替 Maybe，即。 newtype Parser a = Parser { parse :: String -> [(a,String)] }.

所以我们有

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

_{（satisfy在这里对我们没有好处....为什么？）}

利用它，我们可以

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

_{(... ensure id (pure False) 有什么作用？...)}

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

不怕，我们也有

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

可以帮我们把Nothing变成()。我们需要一个始终为我们执行此操作的函数，

alwaysUnit nothing  =  ()

我们现在可以使用它来得出解决方案：

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

在 Haskell 中组合解析器

Combining parsers in Haskell

parsing

haskell

applicative