parsing - 如果 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 解析器总是在失败时回溯”和“如果您将增量输入提供给解析器，它将需要与您提供的输入量成正比的内存。(这是支持任意回溯所必需的。)”。为什么是这样？这不应该是回溯的确切含义吗？

Answer 1

Attoparsec 文档中“回溯”的含义与其他回溯解析器的回溯含义不同。
在使用 try 时查看“回溯”的含义会有所帮助对于 Parsec 或 Megaparsec 解析器。这些解析器有一个概念，即在使用输入后失败(“consume err”=cerr)与在不使用任何内容后失败(“empty err”=eerr)。对于这些解析器，p <|> q替代运算符处理 p 的失败如果是 cerr(立即使整个 p <|> q 失败)与 eerr(尝试替代 q)，则情况不同。 try通过将 cerr 转换为 eerr 来实现回溯。即，try p <|> q将在事件 p 中“回溯”输入流的错误消耗cerr 失败。这是一个 单步回溯替代方案中的失败 (尽管使用嵌套的 try 调用，可以在解析失败的序列/级联中执行多个回溯步骤)。
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' 的单个成功解析.
现在，考虑解析器:

(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' parse 被尝试，它在前者上失败，但在后者上成功。
回到你的例子。用 Attoparsec 解析时，因为:

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

左替代 (:) <$> anyChar <*> many anyChar将继续成功匹配，直到 anyChar匹配右引号。在 EOF 时，左侧会失败(不消耗输入，尽管 Attoparsec 不在乎)，而右侧会成功。替代方案中唯一的失败是在 EOF 处，它无论如何都没有消耗任何东西，因此 Attoparsec 的自动“回溯”不起作用； Megaparsec 也会做同样的事情。无论如何，一旦这个 many anyChar已成功，即使终止 char '"' 也不会重新访问随后失败。
所以，这就是为什么你需要 manyTill明确注意终止字符。