如果阿特帕秒后退，为什么它需要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解析器无法匹配，尽管它确实有回溯：其文件说"attoparsec解析器总是在失败时回溯“，”如果您将增量输入提供给解析器，它将需要与所提供的输入量成比例的内存量。(这是支持任意回溯所必需的。“为什么会这样呢？这不正是回溯的意思吗？

Answer 1

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

当将try用于Parsec或Megaparsec解析器时，它有助于回顾“回溯”意味着什么。这些解析器有一个概念，即在使用输入后失败(“消费错误”= cerr)，而在不使用任何东西之后失败(“空错误”= eerr)。对于这些解析器，如果p <|> q alternative操作符是cerr (立即使整个p <|> q失败)，而不是eerr (尝试替代q )，则它将不同地对待p的失败。try函数通过将cerr转换为eerr来回溯。也就是说，try p <|> q将“回溯”在p使用cerr失败时输入流的错误消耗。这是在中对失败进行回溯的一个步骤(尽管使用嵌套的try调用，可以在一个序列/级联的解析失败中执行多个回溯步骤)。

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

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

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

几个简化的例子可能有助于显示不同之处。考虑解析器：

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

和输入字符串"bd"。此解析器在Parsec/兆位秒中失败。左边的选项在使用了输入(cerr)之后，在失败之前使用了"b"和anyChar，而整个解析器都失败了。不过，这对于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'解析时，前者失败，后者成功。

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

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

左边的可选(:) <$> anyChar <*> many anyChar将继续成功匹配，直到并包括anyChar匹配结束引号的点。在EOF，左侧将失败(而不消耗输入，尽管Attoparsec并不关心这一点)，而右侧将成功。备选方案中唯一的失败是EOF，它根本不消耗任何东西，因此Attoparsec的自动“回溯”不起作用；巨无霸so也会做同样的事情。无论如何，一旦这个many anyChar成功了，它将不会被重新访问，即使终止的char '"'随后失败。

所以，这就是为什么您需要manyTill显式地监视终止字符。