parsec中的全回溯星运算符

Question

我正在尝试建立一个真正的，完全回溯+组合器在parsec上。

也就是说，它接收解析器，并尝试查找给定组合子的一个或多个实例。

例如，这意味着parse_one_or_more foolish_a将能够连续匹配9个字符a。(有关上下文，请参阅下面的代码)

据我所知，它目前没有这样做的原因是，在foolish_a找到一个匹配(前两个as)之后，many1 (try p1)永远不会放弃这个匹配。

这在parsec中是可能的吗？我敢肯定它会非常慢(这个简单的例子已经是指数级的了！)但我想知道这是否可以做到。它适用于没有时间限制的编程挑战--我不想在野外使用它

import Text.Parsec
import Text.Parsec.String (Parser)

parse_one_or_more :: Parser String -> Parser String
parse_one_or_more p1 = (many1 (try p1)) >> eof >> return "bababa"

foolish_a = parse_one_or_more (try (string "aa") <|> string "aaa")

good_a = parse_one_or_more (string "aaa")

-- |
-- >>> parse foolish_a "unused triplet" "aaaaaaaaa"
-- Left...
-- ...
-- >>> parse good_a "unused" "aaaaaaaaa"
-- Right...

Answer 1

你是对的--类似Parsec的库不能以一种对任何输入都有效的方式做到这一点。Parsec的(<|>)实现是左偏的，如果匹配，就提交给左解析器，而不管语法后面会发生什么。当(<|>)的两个参数重叠时，例如在(try (string "aa") <|> string "aaa")中，如果左侧匹配成功，则无法使parsec回溯到其中并尝试右侧匹配。

如果你想这样做，你需要一个不同的库，一个没有(<|>)操作符的左倾提交的库。

Answer 2

是的，由于Parsec生成递归下降解析器，因此您更愿意首先进行明确的猜测，以最大限度地减少回溯的需要。因此，如果你的第一个猜测是"aa"，而这恰好与后来的猜测"aaa"重叠，那么回溯是必要的。有时，对于某些k>1，一个文法是LL(k)，你想使用回溯是出于纯粹的必要性。

我唯一使用try的时候是当我知道回溯是相当有限的时候(k很低)。例如，我可能有一个与另一个操作符?//重叠的操作符?；由于优先级规则，我想先解析?，但我希望解析器失败，以防后面跟着//，这样它最终就能得到正确的解析。这里k= 2，所以影响很小，但我也不需要一个运算符，让我任意回溯。

如果您想要一个解析器组合器库，让您始终完全回溯，这可能会以严重的性能为代价。你可以研究一下Text.ParserCombinators.ReadP的+++对称选择运算符，它同时选择了这两个运算符，这是卡尔建议的一个例子，它是一个不偏左的提交( <|> )。