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 网站，连同 manyTill:

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 (<|>) 的文档，您会发现一段重要的强调文本：

The parser p <|> q first applies p. If it succeeds, the value of p is returned. If p fails without consuming any input, parser q is tried.

未说明的事实是，如果 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 类型中看出它没有明智的方式来表示 "failure after consuming input" 与 "failure without consuming input"，所以你的实现p <|> q 无疑会在 p 失败时尝试 q，即使它在处理了一些输入后失败了。

因此，您的解析器就像每个词项都被 try 包围一样，因此 try 函数将是多余的。

parsec的try方法如何实现？

How to implement parsec's try method?

monads

parsing

haskell