你如何使用applicatives链接一系列任意长的原子解析器？

Question

假设我有这个解析器类型:

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

而这个原子解析器单元:

satisfy :: ( Char -> Bool ) -> Parser Char
satisfy g = Parser $ \stream -> case stream of
    (x:xs) | g x -> Just ( x, xs )
    otherwise    -> Nothing

解析器实现这三个接口:

instance Functor Parser where
    fmap g ( Parser p ) = Parser $ \xs0 -> p xs0 >>= \(x,xs) -> return ( g x, xs )


instance Applicative Parser where
    pure a                      = Parser $ \xs0 -> Just ( a, xs0 )
    (Parser p1) <*> (Parser p2) = Parser $ \xs0 -> do
        (x1, xs1) <- p1 xs0
        (x2, xs2) <- p2 xs1
        return ( x1 x2, xs2 )

instance Alternative Parser where
    empty                        = Parser $ const Nothing
    (Parser p1) <|> (Parser p2)  = Parser $ \ss -> let ss1 = p1 ss in case ss1 of
        Nothing  -> p2 ss
        _        -> ss1

据我所知,现在我可以通过链接satisfy使用应用程序界面来弹出更高级别的抽象并构建更复杂的解析器.例如:

-- | A parser that parses the first two chars in the stream if they are upper case
uParser = satisfy isUpper
parser1 = ( (:) <$> uParser ) <*> ( (\x -> [x]) <$> uParser )
runParser parser1 "HEllo" = Just ("HE","llo")
runParser parser1 "Hello" = Nothing

这很好,现在如果我想构建一个计算,以便解析器解析流中的所有封顶字母,直到它遇到一个小写字母？使用案例:

runParser idealParser "hello"             = Nothing
runParser idealParser "HEllo"             = Just ("HE","llo")
runParser idealParser "HELLOIAMnotincaps" = Just ("HELLOIAM", "notincaps")

我如何表达这种不确定长度的概念？

Answer 1

由于您有一个Alternative实例,因此您只需使用Control.Applicative.some匹配一个或多个实例的列表即可.

> runParser (some uParser) "hello"
Nothing
> runParser (some uParser) "HEllo"
Just ("HE","llo")
> runParser (some uParser) "HELLOIAMnotincaps"
Just ("HELLOIAM","notincaps")

要手动实现它,您可以使用两个相互递归的解析器,例如

zeroOrMore = oneOrMore <|> pure []
oneOrMore  = (:) <$> uParser <*> zeroOrMore