FParsec：回溯 `sepBy`

Question

考虑以下玩具语法和解析器：

(* in EBNF:
  ap = "a", { "ba" }
  bp = ap, "bc"
*)
let ap = sepBy1 (pstring "a") (pstring "b")
let bp = ap .>> (pstring "bc")
let test = run bp "abababc"

我得到以下输出：

Error in Ln: 1 Col: 7
abababc
      ^
Expecting: 'a'

很明显，sepBy1 看到了最后一个 b 并希望它通向另一个 a，但在找不到时失败。是否有 sepBy1 的变体可以回溯 b 并使此解析成功？我有什么理由不应该改用它吗？

Answer 1

我不确定返回值是否重要，但如果不重要，那么最简单的方法是更仔细地转录语法：

let ap = pstring "a" >>. many (pstring "ba")
let bp = ap .>> pstring "bc"

请注意，pstring "ba" 不会导致您遇到的相同问题，因为 pstring 不能仅使用其参数的一部分；要么它消耗了一个完整的 "ba"，要么它没有消耗任何东西就失败了，因此 bp 可以成功地看到一个 b 如果有的话。

另一种可能性，如果这确实是完整的语法（即 ap 未在其他地方的另一个产品中使用），则将其更改为以下 EBNF，等价于：

ap = "ab", { "ab" }
cp = ap, "c"

这使得使用 FParsec 更容易实现：

let ap = many1 (pstring "ab")
let cp = ap .>> pstring "c"

Answer 2

我一直在查看 FParsec source for the sepBy family of functions，看起来没有办法（目前）能够准确地完成您对任何 sepBy 函数的要求。但是，如果您的分隔符解析器很简单，您可能能够很好地近似它。

为了估计您要查找的内容，您可以尝试使用 sepEndBy，或者更可能是 sepEndBy1。它的预期用途是使用列表的 Python 语法，其中最后一项允许有尾随逗号：[ 1, 2, 3, ]。使用 sepEndBy1 将消耗最后的分隔符，因为这是您在其预期用途中想要的。但是，在您的用例中，您必须解决 sepEndBy1 使用最后一个分隔符的事实。例如，

// This parser will be either a separator *or* a prefix of the next item
let sharedParser = pstring "b"

let ap = sepEndBy1 (pstring "a") sharedParser
let restOfBp = pstring "c"
let bp = restOfBp <|> (pipe2 sharedParser restOfBp (fun b c -> b + c))

这里pipe2中的combining函数是简单的字符串拼接，但在您的实际使用场景中可能会有所不同。关键思想是 if 你可以编写一个简单的函数来将你的 b 解析器与你的 c解析器生成 bc 结果，并且如果 c 解析器不太复杂，那么这将适用于你。如果c极其复杂而b很简单，那么就把<|>两边的顺序倒过来，这样就先测试b，再测试c仅在 b 成功或失败后进行测试；这样您就不必像在我刚刚发布的示例代码中那样两次应用 c 解析器。我按照我的方式写的，因为这样更容易理解。

If sepEndBy1 not 对你有用，因为你现实生活中的 b 和 c 解析器都太解析两次很昂贵，那么我能想到的唯一解决方案就是要求将这个新的 sepBy 变体作为新功能添加到 FParsec 中。我对 FParsec 代码的研究表明，可以重写实现以选择性地回溯到最终分隔符之前，但它需要进行一些重要的测试和对边缘情况的考虑，因此它不会是一个五分钟的修复。但是，如果 sepEndBy1 解决方法对您不起作用，请继续 submit that feature request.

Answer 3

这是实现 sepBy1 变体的一种方法：

let backtrackingSepBy1 p sep = pipe2 p (many (sep >>? p)) (fun hd tl -> hd::tl)

避免解析器语法中的回溯通常会使解析器更快、更便携且更易于调试。因此，如果您有机会通过重构语法来避免回溯（不会太复杂），我建议您这样做。

FParsec：回溯 `sepBy`

FParsec: backtracking `sepBy`

f#

parser-combinators

fparsec