为什么在解析器的一部分成功并且其余部分失败时，Parsec不会回溯？ [英] Why doesn't Parsec backtrack when one part of the parser succeeds and the rest fails?

问题描述

我有这个parsec分析器：

  a = optionMaybe $ do {try $ spaceornull *>字符串hello;字符串否} 
  

其中 spaceornull 是（（：[]）< $>尝试空间）< |>字符串

当我使用输入进行测试时，我得到：

左边（第1行，第2列）：

意外结束输入

期望hello

我不明白这点， spaceornull *>字符串hello应该失败，因为没有hello，然后用 try parsec backtracks，现在没有消费输入，但是 try 无论如何失败，所以解析器传递给 optionMaybe （> ）完全失败，它不应该尝试消耗更多的输入，所以我们最终得到一个失败的解析器而不消耗任何输入，所以我应该得到 Right Nothing 。



但是错误信息表明它是空的，所以 try 并没有真正回溯，< c $ c> try 当解析器的一部分成功时不会回溯？以及如何使它与上面的回溯？

解决方案

try has与失败是否允许无关。它只是使得可以在失败的情况下回溯^†，但是为了开始回溯，您需要提供一个替代解析器来开始这一点。通常的做法是使用 < |> 运营商：

  a = optionMaybe $（try $ spaceornull *> stringhello）< |>字符串否
  

OTOH，您的代码相当于

  a = optionMaybe $（try $ spaceornull *> stringhello）>>字符串否
  

其中monadic chaining operator >> （与 *> ）在parsec的情况下检查LHS是否成功，然后继续并运行RHS解析器。所以它一定是，因为你也可以写：

  a = optionMaybe $ do 
s<  -  try $ spaceornull * GT;字符串hello
字符串$否++ s 
  

第一个解析器的结果（你简单地扔掉了，而不是< - - 将它匹配到任何变量）决定第二个应该寻找。这显然是唯一可能的，第一个实际上是成功的！

---

^† _{基本上， < |> 仅适用于LHS 立即在第一个字符处失败，或者如果您使用<$ c设置回溯点$ C>尝试。这是必需的原因是，如果parsec需要在每个替代品之前留下一个回溯点，那么效率会非常低下。}

I have this parsec parser :

a = optionMaybe $ do {try $ spaceornull *> string "hello";string "No"}                        

Where spaceornull is ((:[]) <$> try space) <|> string ""

When I test a with input " " I get :

Left (line 1, column 2):
unexpected end of input
expecting "hello"

I don't understand this, spaceornull *> string "hello" should fail because there is no "hello", then with try parsec backtracks and now there is no consumed input but try fails anyway so the parser passed to optionMaybe (the one inside do) fails altogether, it shouldn't try to consume farther input, so we end up with a failed parser without consuming any input so I should get Right Nothing.

But the error message says it, the space is consumed so try didn't really backtrack, does try not backtrack when part of parser succeeds ? and how to make it backtrack with the above ?

解决方案

try has nothing to do with whether failure is allowed or not. It merely makes it possible to backtrack in case of failure^†, but to commence the backtracking you need to provide an alternative parser to start at that point. The usual way to do that is with the <|> operator:

a = optionMaybe $ (try $ spaceornull *> string "hello") <|> string "No"

OTOH, your code is equivalent to

a = optionMaybe $ (try $ spaceornull *> string "hello") >> string "No"

where the monadic chaining operator >> (same as *>) will in the case of parsec check if the LHS succeeds, then go on and also run the RHS parser. So it must be, because you could also write:

a = optionMaybe $ do
       s <- try $ spaceornull *> string "hello"
       string $ "No"++s

Here I've used the result of the first parser (which you simply threw away, by not <--matching it to any variable) in deciding what the second one should look for. This clearly is only possible of the first actually succeeded!

---

^†_{Basically, <|> only works if either the LHS immediately fails right at the first character, or if you set a backtracking point with try. The reason this is required is that it would be very inefficient if parsec would need to leave a backtracking point before each and every alternative that needs to be ckecked.}

这篇关于为什么在解析器的一部分成功并且其余部分失败时，Parsec不会回溯？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！