regex - 是否可以在 Attoparsec 中有效地预测多个字符？

Question

我正在尝试用一个函数来扩充 Haskell 的 Attoparsec 解析器库

takeRegex :: Regex -> Parser ByteString

使用其中一种正则表达式实现。

(动机:好的正则表达式库可以提供与输入长度成线性关系的性能，而 attoparsec 需要回溯。我的输入的一部分特别适合使用正则表达式进行解析，甚至回溯 Text.Regex.PCRE 库也能帮助我该部分的 attoparsec 代码加速了 4 倍。)

Attoparsec 曾经有一个 getInput :: Parser ByteString获取(不消耗)剩余输入的函数；这对我的目的来说可能是非常完美的，因为我的输入是非增量的、严格的并且相当小——我一次运行解析器以获取一行日志文件。有了它，我似乎可以做类似的事情

takeRegex re = do
  input <- getInput
  m <- matchM re input
  take $ length m

不幸的是，最近版本的 attoparsec 缺少此功能。有什么方法可以达到同样的效果吗？为什么这个功能被删除了？

现在有 takeByteString :: Parser ByteString函数，它接受并消耗其余的输入。如果有一个函数可以尝试解析并在不实际消耗任何内容的情况下获取结果，则可以将其与它结合使用，但我似乎也找不到(或弄清楚如何实现)这样的函数。

有没有办法用当前版本的 attoparsec 来实现这一点？

Answer 1

有一些解决方案，但没有一个很好....

方法 1- 快速实现，但运行速度不快

好吧，(根据 http://hackage.haskell.org/package/attoparsec-0.10.1.1/docs/Data-Attoparsec-ByteString.html )， attoparsec 总是在失败时回溯，所以你总是可以做这样的事情 -

parseLine1 = do
  line <- takeTill (== '\n')
  char '\n'
  case <some sort of test on line, ie- a regex> of
    Just -> return <some sort of data type>
    Nothing -> fail "Parse Error"

然后稍后其中许多链接在一起将按预期工作

parseLine = parseLine1 <|> parseLine2

如您所见，此解决方案的问题在于，您仍在进行大量回溯，这确实会减慢速度。

方法2-传统方法

处理这类事情的通常方法是重写语法，或者在解析器组合器的情况下，移动东西，使完整的算法只需要一个前瞻字符。这几乎总是可以在实践中完成，尽管它有时会使逻辑更难遵循......

例如，假设您有这样的语法产生规则-

pet = "dog" | "dolphin"

这需要两个字符的前瞻才能解决任一路径。相反，您可以像这样离开整个事情

pet => "ca" halfpet
halfpet => "g" | "lphin"

不需要并行处理，但是语法就丑多了。 (虽然我把它写成一个生产规则，但是有一对一的映射到一个类似的解析器组合器)。

方法3-正确的方法，但涉及到写作。

您想要这样做的真正方法是将正则表达式直接编译为解析器组合器....一旦您编译任何常规语言，生成的算法总是只需要一个前瞻字符，因此生成的 attoparsec 代码应该非常简单(就像方法 1 中读取单个字符的例程一样)，但工作将是编译正则表达式。

编译一个正则表达式在很多教科书中都有涉及，所以我不会在这里详细介绍，但它基本上相当于用新的状态替换正则表达式状态机中的所有模棱两可的路径。或者换句话说，它会自动“留下”所有需要回溯的案例。

(我写了一个库，它在上下文无关语法中自动“留下”许多情况，将几乎所有上下文无关语法转换为线性解析器一次，但我还没有让它可用......有一天，当我清理它时我会的)。