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 并使解析成功？我为什么不能使用它呢？

- Carl Patenaude Poulin

---

我已经打开了 https://github.com/stephan-tolksdorf/fparsec/issues/15 来讨论这个功能。如果您想在 Github 上留下评论，更详细地解释您的用例（例如，您正在努力处理的真实语法，而不是 Stack Overflow 问题的简化语法），那么这将有助于 Stephan（以及我，因为我可能参与实现该功能）确定是否值得实现和测试该功能。但正如他所指出的，如果您可以重新排列语法以避免回溯，那就更好了。 - rmunn

Answer 1

这是实现类似 sepBy1 的一种方法：

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

避免在语法分析器语法中使用回溯通常会使解析器更快、更易于移植和调试。因此，如果您有机会通过重新构造语法来避免回溯（而不会使其过于复杂），我建议您这样做。

- Stephan Tolksdorf

Answer 2

我一直在查看FParsec的sepBy函数族源代码，看起来目前没有办法准确地使用任何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 中的组合函数是简单的字符串连接，但在您实际的使用场景中可能会有所不同。关键思想是，如果您能编写一个简单的函数来将您的b解析器与您的c解析器组合以产生bc结果，并且如果c解析器不太复杂，则这将对您有用。如果c非常复杂，但b很简单，请只需颠倒<|>两侧的顺序，使得先测试b，只有在b成功或失败后才测试c；这样您就不必像我刚才发布的示例代码中那样应用两次c解析器。我之所以这样写是因为这样稍微容易理解一些。

如果sepEndBy1对您无效，因为在您的实际情况下b和c解析器都太昂贵而无法解析两次，那么我能想到的唯一解决方案就是请求将这个新的sepBy变体添加到 FParsec 作为新特性。我的 FParsec 代码查看表明，可以重写实现以选择性地回溯到最后一个分隔符之前，但需要进行一些重要的测试和考虑边缘情况，因此它不会是一个五分钟的修复方案。但如果sepEndBy1解决方法对您无效，则继续并提交该功能请求。

- rmunn

---

转念一想，你或许可以使用 attempt 和/或 lookAhead 解析器组合来得到你需要的结果。我会再考虑一下，并根据这些提供建议更新我的答案——不过可能要等到明天才有时间这样做。 - rmunn

Answer 3

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

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

请注意，pstring "ba" 不会引起您之前遇到的同样问题，因为 pstring 无法仅消耗其参数的一部分；它要么消耗完整的 "ba"，要么失败而不消耗任何内容，因此如果有一个 b，则 bp 可以成功看到它。

另一个可能性是，如果这确实是完整的语法（即 ap 在其他地方没有被使用），则可以将其更改为以下等效的 EBNF：

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

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

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

- Tarmil

---

抱歉，任何开发过实际解析器应用的人都会意识到 pstring "a" 只是一个示例，在实际应用程序中可能会有复杂的解析器。因此，建议使用 pstring "ba" 在这里没有用处，并且不总是可以进行重复。 - Be Brave Be Like Ukraine

在实际情况中，如果b是分隔符，而a是你想要作为列表的内容，那么你可以使用a .>>. many (try (b >>. a))，这基本上是我第一个答案的更通用版本。 - Tarmil