是否有可能在Attoparsec中有效地展望多个Char？

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 中读取单个字符的例程），但工作将是编译正则表达式。

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

（我写了一个库，可以在上下文无关语法中自动“留下因子”，将几乎所有上下文无关语法一次转换为线性解析器，但我还没有使其可用......有一天，当我清理它时我会的）。