Lightyear requireFailure 不做回溯

Question

我想解析一系列任意 4 个字符。但是，这些字符不应形成特定的字符串（在下面的示例中为 "bb"）。所以 "aaaa" 和 "abcd" 可以，但是 "bbcd" 和 "abbc" 都不应该匹配。

我编写了以下解析器：

ntimes 4 (requireFailure (string "bb") *> anyChar)

但是，我注意到，它 "eats" 单个 b 个字符。例如

parse (ntimes 4 (requireFailure (string "bb") *> anyToken)) "abcde"

结果为 ['a', 'c', 'd', 'e']（但是，如预期的那样，它在 "bbcd" 和 "abbc" 上失败）。

作为解决方法，我使用了自己的 requireFailure:

实现

requireFailure' : Parser a -> Parser ()
requireFailure' p = do
    isP <- p *> pure True <|> pure False
    if isP then fail "argument parser to fail"
           else pure ()

所以

parse (ntimes 4 (requireFailure' (string "bb") *> anyToken)) "abcde"

如我所料给出 ['a', 'b', 'c', 'd']。

显然光年解析器是 backtrack-by-default，除非有人调用 commitTo。

所以我的问题是，为什么 requireFailure 的库实现在参数失败时不进行回溯，这是预期的行为吗？

Answer 1

如果您查看 the implementation of requireFailure，您会看到它调用 "success" 延续 us 状态 s 它在 之后得到 运行它的参数而不是它之前得到的参数 ST i pos tw。

requireFailure : ParserT str m tok -> ParserT str m ()
requireFailure (PT f) = PT $ \r, us, cs, ue, ce, (ST i pos tw) =>
                               f r
                                 (\t, s => ue [Err pos "argument parser to fail"] s)
                                 (\t, s => ce [Err pos "argument parser to fail"] s)
                                 (\errs, s => us () s)
                                 (\errs, s => cs () s)
                                 (ST i pos tw)

文档声称 requireFailure 在秒差距和 that doesn't consume any input 中被称为 notFollowedBy，所以你可以说这是 LightYear 方面的一个错误。

您可以打开一个错误报告，建议用类似的东西替换当前代码（我不知道 Idris 是否支持 @ 模式）：

requireFailure : ParserT str m tok -> ParserT str m ()
requireFailure (PT f) = PT $ \r, us, cs, ue, ce, s@(ST i pos tw) =>
                               f r
                                 (\t, s => ue [Err pos "argument parser to fail"] s)
                                 (\t, s => ce [Err pos "argument parser to fail"] s)
                                 (\errs, _ => us () s)
                                 (\errs, _ => cs () s)
                                 s

Lightyear requireFailure 不做回溯

Lightyear requireFailure does not do backtracking

idris

parser-combinators

lightyear