.net – 可以处理机器生成的正则表达式的正则表达式实现：*无回

编辑：自从我第一次问到这个问题以来,这个问题已经有了很大的看到下面两个快速兼容但不完全功能齐全的实现.如果你知道更多或更好的实现,请提及它们,这里还没有一个理想的实现！

在哪里可以找到可靠的快速Regex实现？

有没有人知道正常的非回溯(System.Text.RegularExpressions回溯)线性时间正则表达式实现,对于.NET或本机,可从.NET中合理使用？为了有用,需要：

>具有O(m * n)的正则表达式估计的最差情况时间复杂度,其中m是正则表达式的长度,n是输入的长度.
>具有O(n)的正常时间复杂度,因为几乎没有正则表达式实际上触发指数状态空间,或者如果它们可以,则仅在输入的一小段子集上这样做.
>具有合理的施工速度(即没有潜在的指数型DFA)
>意图供人类使用,而不是数学家使用.我不想重新实现unicode字符类：.NET或PCRE样式字符类是一个加号.

奖金积分：

如果实现了基于堆栈的功能,它可以以消耗O(n m)存储器而不是O(m)存储器为代价处理嵌套来实现实惠的积分.
>获取子表达式或替换的奖励积分(如果存在指数数量的可能的子表达式匹配,则枚举所有这些都是固有的指数级 – 但是枚举前几个不应该是,并且类似地替换).您可以通过使用其他功能来删除任一功能,因此使用任一功能就足够了.
>将正则表达式视为第一类值的很多奖励积分(因此,您可以采用联合,交集,并置,否定 – 特别是否定和交集,因为这些非常难以通过字符串操作正则表达式定义)
>懒惰的匹配,即在无限流上进行匹配,而不把它全部放在内存中是一个加号.如果流不支持搜索,则在单次通过中不会(通常)捕获子表达式和/或替换.
>反向引用,它们根本不可靠;即可以在病理输入情况下始终呈现指数行为.

存在这样的算法(这是基本的自动机理论…) – 但是有什么实用的实现可以从.NET访问？

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

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

要快速了解为什么更好的实现存在并且自60年代以来,请参阅Regular Expression Matching Can Be Simple And Fast.

不太实用的选择：

>几乎理想：FSA toolkit.可以将正则表达式编译成DFA的NFA的快速C实现,也允许传感器(！)具有包含交叉和参数化语法的一级正则表达式(封装yay！).但它是在prolog …(为什么这种实用功能的东西在主流语言中不可用)
>快速但不切实际：一个完整??的解析器,如优秀的ANTLR通常支持可靠的快速正则表达式.然而,antlr的语法更加冗长,当然也允许不能生成有效解析器的构造,因此您需要找到一些安全的子集.

良好的实施：

> RE2 – 一个谷歌开源库,旨在合理的PCRE兼容性减去反向引用.笔者认为这是plan9的正则表达式lib的unix端口的继承者.
> TRE – 大多与PCRE兼容,甚至反向引用,尽管使用那些您失去速度保证.它有一个大型的近似匹配模式！

不幸的是,两个实现都是C,并且需要从.NET使用互操作.