如何实现parsec的try方法？

Question

我想实现与parsec的try方法相同的方法。但是我没有使用解析转换器，而是使用了一个保存状态的Parser对象：

try :: Parser String -> Parser String
try p = P $ s -> case doParse p s of
[] -> [("", s)]
[(a, s')] -> [(a, s')]

我很确定我的努力在这里远远超出了目标。因此，任何帮助将不胜感激。

newtype Parser a = P (String -> [(a, String)])
instance Functor Parser where
fmap = liftA
instance Applicative Parser where
pure x    = P (cs -> [ (x,cs) ])
p1 <*> p2 = P (cs -> do (f, cs')  <- doParse p1 cs
(x, cs'') <- doParse p2 cs'
return (f x, cs''))
instance Monad Parser where
return = pure
p1 >>= f = P (cs -> let [(a, s)] = doParse p1 cs
in doParse (f a) s)
instance Alternative Parser where
-- the parser that always fails
empty     = P $ const []
-- | Combine two parsers together in parallel, but only use the
-- first result. This means that the second parser is used only
-- if the first parser completely fails.
p1 <|> p2 = P $ cs -> case doParse (p1 `choose` p2) cs of
[]   -> []
x:_ -> [x]
doParse :: Parser a -> String -> [(a, String)]
doParse (P p) = p

编辑：

我想解析的示例：

<!-- This is a random 
HTML
Comment -->

通过运行：

doParse simpleComment excomment

simpleComment摘自Parsec网站，以及许多Till：

simpleComment   = do{ string "<!--"
; manyTill anyChar (try (string "-->"))
}
manyTill p end      = scan
where
scan  = do{ _ <- end; return [] }
<|>
do{ x <- p; xs <- scan; return (x:xs) }

Answer 1

你的解析器不需要try。 或者，如果你真的想要一个，你可以简单地将其定义为：

try :: Parser a -> Parser a
try = id

Parsec区分了消耗某些输入后失败和不使用任何输入失败。 例如，如果您查看 Parsec(<|>)的文档，您会发现一段重要的强调文本：

解析器p <|> q首先应用p。如果成功，则返回p的值。如果在不消耗任何输入的情况下p失败，则会尝试解析器q。

未说明的事实是，如果在消耗部分输入后p失败，则整个事情都会失败，并且永远不会尝试q。 这意味着在 Parsec 中，解析器：

broken :: Parser String
broken = string "hello" <|> string "hi"

不行。 它可以解析"hello"，但它不能解析"hi"，因为第一个解析器string "hello"在发现其余部分不匹配之前消耗"h"，所以它从不尝试string "hi"解析器：

> parseTest broken "hello"
"hello"
> parseTest broken "hi"
parse error at (line 1, column 1):
unexpected "i"
expecting "hello"

要解决此问题，您必须使用try，它允许您覆盖此规则：

okay :: Parser String
okay = try (string "hello") <|> string "hi"

给：

> parseTest okay "hello"
"hello"
> parseTest okay "hi"
"hi"

您的解析器是不同的。 即使你没有给出choose的定义，我也可以从你的Parser类型中看出，它没有明智的方法来表示"消耗输入后失败"与"不消耗输入失败"，所以你的实现p <|> q无疑会在p失败时尝试q，即使它在处理了一点输入后失败。

因此，你的解析器就像每个术语都被try包围一样，所以try函数将是多余的。