Attoparsec 解析失败，但使用正确的回溯应该不会失败。

Question

我正在使用Attoparsec，据说它默认采用回溯。但是下面这行代码：

parseOnly  (string "foo" *> many1 anyChar <* string "bar") "fooxxxbar"

出现以下错误：

Left "not enough input"

为什么会这样？如果many1 anyChar决定只解析三个字符(xxx)，它应该是成功的。因为回溯的缘故，它应该在某个时候考虑这样做，不是吗？

如何使用Attoparsec实现等效于/foo(.*)bar/正则表达式的正确方法？

- Iguana Bob

Answer 1

我正在使用Attoparsec，据说它默认会回溯。

并不完全是这样。Attoparsec确实支持回溯，但仅在某些明确的情况下（文档中指出的情况）才支持。它的目的是高性能解析，可想而知，这与回溯不太兼容。

你需要使用manyTill或manyTill'。请注意，回溯行为在文档中有所提及。

ghci> manyTill1 p e = (:) <$> p <*> manyTill p e 
ghci> parseOnly (string "foo" *> manyTill1 anyChar (string "bar")) "fooxxxbar"
Right "xxx"

- Alec

---

好的，文档明确表示：“attoparsec解析器在失败时总是回溯”。有哪些具有完全回溯支持的解析器组合器？对我来说，性能不是问题，而使用manyTill提出的解决方案在我的用例中效果不佳。 - Iguana Bob

@IguanaBob regex-applicative 不会回溯，但只要有可能就会成功匹配。ReadP 具有相同的特性并且可以解析更多的语法。ReadS 基本上是一个效率较低的 ReadP ，实际上会回溯 - 但我认为 "回溯" 是一个关于实现的细节，真正重要的特性是这三个库都满足的。 - Daniel Wagner