FParsec:回溯"sepBy" [英] FParsec: backtracking `sepBy`

问题描述

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

Consider the following toy grammar and parser:

(* 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并使此解析成功?有什么理由我不应该使用它吗?

Clearly sepBy1 sees the last b and expects it to lead into another a, failing when it doesn't find one. Is there a variant of sepBy1 which would backtrack over b and make this parse succeed? Is there any reason why I shouldn't use that instead?

推荐答案

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

This is one way to implement such a variant of sepBy1:

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

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

Avoiding backtracking in your parser grammar usually makes the parser faster, more portable and easier to debug. Hence, if you have the chance to avoid backtracking by restructuring the grammar (without complicating it too much), I'd recommend doing it.

这篇关于FParsec:回溯"sepBy"的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！