FParsec:回溯“”

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

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

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

避免语法中的回溯通常会使解析器更快、更可移植和更易于调试。因此，如果您有机会通过重构语法来避免回溯(而不使语法复杂化)，我建议您这样做。

Answer 2

我一直在查看函数族，看起来(目前)没有任何方法(目前)能够精确地满足您对任何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代码的研究表明，可以将实现重写为可选的回溯到最终分隔符之前，但它需要对边缘情况进行一些重要的测试和考虑，这样就不会有5分钟的修复。但是，如果sepEndBy1的解决方案对您不起作用，那么请继续使用提交该功能请求。

Answer 3

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

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

请注意，pstring "ba"不会引起与您相同的问题，因为pstring不能只使用其参数的一部分；要么它消耗完整的"ba"，要么它在不消耗任何东西的情况下失败，因此如果有一个b，bp可以成功地看到一个b。

如果这确实是完整的语法(即在其他地方的其他产品中没有使用ap )，另一种可能是将其更改为以下EBNF，这是等价的：

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

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

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