regex - 在Attoparsec中是否可以有效地预见多个Char？

我正在尝试使用功能增强Haskell的Attoparsec解析器库

takeRegex :: Regex -> Parser ByteString

使用其中一种regexp实现。

(动机:好的regex库可以提供与输入长度成线性关系的性能，而attoparsec需要回溯。输入的一部分特别适合使用regexp解析，甚至回溯的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是否可以实现此目的？

最佳答案

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

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

编译正则表达式在许多教科书中都有介绍，因此在这里我不做详细介绍，但是从本质上讲，这相当于用新的状态替换了正则表达式状态机中的所有歧义路径。或者换句话说，它会自动“遗留因素”所有需要回溯的情况。

(我编写了一个库，可以自动“舍弃”上下文无关文法中的许多情况，几乎将所有上下文无关文法一次转换为线性解析器，但是我尚未将它可用....有一天，当我清理它时我会的)。

关于regex - 在Attoparsec中是否可以有效地预见多个Char？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20894973/