.net - 可以处理机器生成的正则表达式 : *non-backtracking*, O(n) 的正则表达式实现？

Question

编辑 2:要实际证明为什么这仍然很重要，请查看 stackoverflow's own regex-caused outage today (2016-07-20)。 !

编辑:自从我第一次问这个问题以来，这个问题已经有了很大的发展。请参阅下面的两个快速+兼容但不完全功能的实现。如果您知道更多或更好的实现，请提及它们，这里还没有理想的实现!

我在哪里可以找到可靠的快速正则表达式实现？

有没有人知道 .NET 或 native 的正常非回溯(System.Text.RegularExpressions 回溯)线性时间正则表达式实现，并且可以从 .NET 合理使用？为了有用，它需要:

有一个 最坏情况 正则表达式评估的时间复杂度O(m*n) 其中 m 是正则表达式的长度，n 是输入的长度。

有一个 O(n) 的正常时间复杂度 ，因为几乎没有正则表达式实际触发指数状态空间，或者，如果可以，只在输入的一个微小子集上触发。

有一个 合理的施工速度 (即没有潜在的指数 DFA)

供人类而非数学家使用 - 例如我不想重新实现 unicode 字符类: .NET 或 PCRE 风格的字符类是加分项。

奖励积分:

积分为了实用性，如果它实现了基于堆栈的功能 让它处理嵌套 以消耗 O(n+m) 内存而不是 O(m) 内存为代价。

的奖励积分要么 捕获子表达式 或 替换(如果可能的子表达式匹配的数量呈指数级，则枚举所有这些本质上是指数级的 - 但枚举前几个不应该是，对于替换也是类似的)。您可以通过使用另一个来解决缺少任何一个功能，因此拥有其中一个就足够了。

lota 奖励积分 将正则表达式视为第一类值 (因此您可以采用联合、交集、串联、否定 - 特别是否定和交集，因为通过正则表达式定义的字符串操作很难做到这些)

懒惰匹配即匹配无限流而不将其全部放入内存中是一个加分项。如果流不支持查找，则在单次传递中(通常)不可能捕获子表达式和/或替换。

反向引用已失效 ，它们从根本上是不可靠的；即在给定的病理输入情况下总是可以表现出指数行为。

存在这样的算法(这是基本的自动机理论......) - 但是否有任何可从 .NET 访问的实际可用的实现？

背景:(你可以跳过这个)

我喜欢使用 Regex 进行快速和脏文本清理，但我一再遇到问题，perl/java/python/.NET 使用的常见回溯 NFA 实现显示指数行为。不幸的是，一旦您开始自动生成正则表达式，这些情况就很容易触发。当您在匹配相同前缀的正则表达式之间交替时，即使是非指数性能也会变得非常糟糕 - 例如，在一个非常基本的示例中，如果您使用字典并将其转换为正则表达式，则性能会很差。

有关为什么存在更好的实现并且自 60 年代以来一直存在的快速概述，请参阅 Regular Expression Matching Can Be Simple And Fast .

不太实用的选择:

几乎理想:FSA toolkit .可以将正则表达式编译为 DFA + NFA 的快速 C 实现，也允许转换器(!)，具有一流的正则表达式(封装是的!)，包括交集和参数化的语法。 但它在序言中 ...(为什么主流语言没有这种实用功能？？？)

快速但不切实际:一个完整​​的解析器，例如优秀的 ANTLR通常支持可靠的快速正则表达式。但是，antlr 的语法要冗长得多，并且当然允许可能无法生成有效解析器的构造，因此您需要找到一些安全的子集。

好的实现:

RE2 - 一个谷歌开源库，旨在实现合理的 PCRE 兼容性减去反向引用。鉴于作者，我认为这是 plan9 的正则表达式库的 unix 端口的继承者。

TRE - 也大多与 PCRE 兼容，甚至可以反向引用，尽管使用那些会失去速度保证。它有一个 super 漂亮的近似匹配模式!

不幸的是，这两种实现都是 C++，并且需要从 .NET 使用互操作。

Answer 1

首先，你的建议是可能的，而且你当然知道你的主题。您还知道不使用反向引用实现的代价是内存。如果您对环境进行了足够的控制，这可能是一种合理的方法。

在继续之前，我唯一要评论的是，我鼓励您质疑使用 RegEx 的选择。您显然更熟悉您的具体问题以及您尝试解决的问题，因此只有您才能回答问题。我认为 ANTLR 不是一个好的选择；但是，自制规则引擎(如果范围有限)可以根据您的特定需求进行高度调整。这一切都取决于您的具体问题。

对于那些阅读这篇文章并“没有捕获重点”的人，这里有一些背景阅读:

Regular Expression Matching Can Be Simple And Fast

从同一个站点，有许多实现 linked on this page .

上述文章的整个讨论的要点是，最好的答案是同时使用两者。为此，我所知道的唯一广泛使用的实现是 TCL 语言使用的实现。据我所知，它最初是由 Henry Spencer 编写的，它采用了这种混合方法。有一些尝试将其移植到 c 库，但我不知道有哪些被广泛使用。 Walter Waldo 和 Thomas Lackner's都被提及和 linked here .还提到了 boost library虽然我不确定实现。您还可以查看 TCL 代码本身(从 their site 链接)并从那里开始工作。

简而言之，我会选择 TRE或 Plan 9因为这些都得到了积极的支持。

显然，这些都不是 C#/.Net，我不知道有一个是。