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

问题描述

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

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

标签： parsinghaskellbacktrackingparser-combinatorsattoparsec

解决方案

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

try当使用Parsec 或 Megaparsec 解析器时，它有助于查看“回溯”的含义。这些解析器具有消耗输入后失败（“consume err” = cerr）与不消耗任何内容后失败（“empty err” = err）的概念。对于这些解析器，如果它是 cerr （立即使整个失败）与 err （尝试替代），则p <|> q替代运算符对失败的处理不同。该函数通过将 cerr 转换为 err 来回溯。也就是说，在cerr 失败的情况下，将“回溯”输入流的错误消耗。这是在替代方案中回溯失败的一个步骤（尽管使用嵌套pp <|> qqtrytry p <|> qptry调用，可以在解析失败的序列/级联中执行多个回溯步骤）。

Attoparsec 不区分 cerr 和 err，所以就好像所有解析器都被try调用包围。这意味着它会自动执行多个步骤来回溯替代方案中的故障。

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

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

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

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

和输入字符串"bd"。此解析器因 Parsec/Megaparsec 而失败。左边的替代方案在失败之前消耗了"b"with anyChar，消耗了输入（cerr），整个解析器失败了。不过，这与 Attoparsec 配合得很好：左侧替代方案在处失败char 'a'，并且 Attoparsec 在尝试char 'b'成功的替代方案中回溯此失败。它还与ReadPwhich 并行构造所有可能的解析一起工作，然后在失败时从左侧替代方案中丢弃解析char 'a'，从而导致单个成功的解析 by 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 的自动“回溯”不起作用；Megaparsec 会做同样的事情。无论如何，一旦成功，即使终止随后失败many anyChar，也不会重新访问它。char '"'

因此，这就是为什么您需要manyTill明确注意终止字符的原因。

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

问题描述

解决方案

推荐阅读