如果回溯，为什么 attoparsec 需要 manyTill？

Question

考虑这些不同的解析器组合器的用法。

import Control.Applicative.Combinators
import Text.Regex.Applicative
 
main :: IO ()
main = do
  let parser1 = sym '"' *> manyTill anySym (sym '"')
  print $ match parser1 "\"abc\""
  let parser2 = sym '"' *> many anySym <* sym '"'
  print $ match parser2 "\"abc\""

import Control.Applicative.Combinators            
import Text.ParserCombinators.ReadP hiding(many, manyTill)
 
main :: IO ()
main = do
  let parser1 = char '"' *> manyTill get (char '"')
  print $ readP_to_S parser1 "\"abc\""
  let parser2 = char '"' *> many get <* char '"'
  print $ readP_to_S parser2 "\"abc\""

{-# LANGUAGE OverloadedStrings #-}
 
import Control.Applicative.Combinators
import Data.Attoparsec.Text hiding(manyTill)
 
main :: IO ()
main = do
  let parser1 = char '"' *> manyTill anyChar (char '"')
  print $ parseOnly parser1 "\"abc\""
  let parser2 = char '"' *> many anyChar <* char '"'
  print $ parseOnly parser2 "\"abc\""

import Control.Applicative.Combinators
import Text.Megaparsec hiding(many, manyTill)
import Data.Void

main :: IO ()
main = do
  let parser1 = single '"' *> manyTill anySingle (single '"') :: Parsec Void String String
  print $ parseMaybe parser1 "\"abc\""
  let parser2 = single '"' *> many anySingle <* single '"' :: Parsec Void String String
  print $ parseMaybe parser2 "\"abc\""

对于所有四个，manyTill 解析器成功匹配 abc，因为这不依赖于回溯。对于 regex-applicative 和 ReadP，many 解析器也成功匹配 abc，因为它们都默认回溯。对于 megaparsec，many 解析器无法匹配，因为默认情况下它不会回溯。到目前为止，一切都说得通。然而，对于 attoparsec，many 解析器无法匹配，即使它确实回溯：its documentation 表示“attoparsec 解析器总是在失败时回溯”和“如果您将增量输入提供给 a解析器，它将需要与您提供的输入量成比例的内存。（这是支持任意回溯所必需的。）”。为什么是这样？这不就是回溯吗？

Answer 1

Attoparsec 文档中“回溯”的含义与其他回溯解析器的回溯含义不同。

它有助于复习在将 try 用于秒差距或百万秒差距解析器时“回溯”的含义。这些解析器有一个概念，即在使用输入后失败（“consume err”= cerr）与在不使用任何东西后失败（“empty err”= eerr）。对于这些解析器，p <|> q 替代运算符以不同方式处理 p 的失败，如果它是 cerr（立即使整个 p <|> q 失败）和 eerr（尝试替代 q）。 try 函数通过将 cerr 转换为 eerr 来回溯。也就是说，try p <|> q 将在事件 p 因 cerr 而失败时“回溯”输入流的错误消费。这是一个在备选方案中对失败进行回溯的单步（尽管使用嵌套try调用，可以在sequence/cascade个解析失败中执行多个回溯步骤）。

Attoparsec 不区分 cerr 和 eerr，因此就好像所有解析器都被 try 调用包围一样。这意味着它会自动执行多个替代方案中的失败回溯步骤。

ReadP 通过同时并行评估每个可能的解析，丢弃那些曾经失败的解析，并选择剩下的“第一个”解析来隐式回溯。 它在所有可能的解析树上“回溯”失败，无论失败是否在替代上下文中生成。

事实证明，“在备选方案中对失败进行多步回溯”是一种比“在所有可能的解析树上回溯”更适度的回溯形式。

几个简化的例子可能有助于显示差异。考虑解析器：

(anyChar *> char 'a') <|> char 'b'

和输入字符串 "bd"。此解析器因 Parsec/Megaparsec 而失败。左侧的替代方案在失败之前使用 "b" 和 anyChar，消耗了输入 (cerr)，并且整个解析器失败。不过，这对 Attoparsec 工作得很好：左侧的替代方案在 char 'a' 处失败，并且 Attoparsec 在替代方案中回溯此失败以尝试成功的 char 'b'。它还与 ReadP 一起工作，它并行构造所有可能的解析，然后在 char 'a' 失败时从左侧替代项中丢弃解析，从而导致 char 'b'.[= 的单个成功解析54=]

现在，考虑解析器：

(anyChar <|> pure '*') *> char 'b'

和输入字符串 "b"。（回想一下 pure '*' 不消耗任何东西并且总是成功。）这个解析器失败并显示 Parsec/Megaparsec，因为 anyChar 解析 "b"，pure '*' 被忽略，并且char 'b' 不匹配空字符串。它也因 Attoparsec 而失败：anyChar 成功解析了 "b"，并且在替代方案的上下文中没有失败，因此没有回溯尝试 pure '*' 替代方案。随后尝试用 char 'b' 解析空字符串失败。（这个失败，如果它发生在另一个替代方案的上下文中，可能会导致回溯那个替代方案，但永远不会重新考虑这个pure '*'替代品。）

相比之下，ReadP 解析得很好。 ReadP 并行解析备选方案，考虑到 anyChar 解析 "b" 和 pure '*' 什么都不解析。当尝试 char 'b' 解析时，前者失败但后者成功。

回到你的例子。用Attoparsec解析时，因为：

many p = ((:) <$> p <*> many p) <|> pure []

左边的选择 (:) <$> anyChar <*> many anyChar 将继续成功匹配，直到 anyChar 匹配右引号的那一点。在 EOF 处，左侧将失败（不消耗输入，尽管 Attoparsec 不关心这一点），右侧将成功。替代方案中唯一的失败是在 EOF 处，它无论如何都没有消耗任何东西，因此 Attoparsec 的自动“回溯”不起作用； Megaparsec 会做同样的事情。无论如何，一旦这个 many anyChar 成功，它就不会被重新访问，即使终止 char '"' 随后失败。

所以，这就是为什么你需要manyTill来明确地监视终止符。

如果回溯，为什么 attoparsec 需要 manyTill？

Why does attoparsec need manyTill if it backtracks?

parsing

haskell

backtracking

parser-combinators

attoparsec