可以处理机器生成的正则表达式的正则表达式实现:*非回溯*,O(n)？

Question

编辑2:为了实际演示为什么这仍然很重要,今天看看 stackoverflow自己的正则表达式导致的停机(2016-07-20)!

编辑:自从我第一次提出这个问题以来,这个问 请参阅下面的两个快速+兼容但不完全全功能的实现.如果你知道更多或更好的实现,请提及它们,这里仍然没有理想的实现!

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

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

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

奖励积分:

• 实用性的奖励点如果它实现了基于堆栈的功能,它允许它以消耗O(n + m)内存而不是O(m)内存为代价来处理嵌套.
• 奖励积分或者捕获子表达式或更换(如果有可能的子表达式匹配一个指数,然后枚举所有的人本质上是指数-但列举的前几个不应该是,同样的替代).您可以通过使用另一个来解决缺少任一功能的问题,因此使用其中一个功能就足够了.
• 将正则表达式作为第一类值处理的许多奖励点(因此你可以采用并集,交集,连接,否定 - 特别是否定和交集,因为通过正则表达式定义的字符串操作很难做到这一点)
• 懒惰匹配即在无限流上进行匹配而不将其全部放入内存中是一个优点.如果流不支持搜索,则捕获子表达式和/或替换不是(通常)单次传递.
• 反向引用已经消失,它们从根本上说是不可靠的; 即,在病理输入情况下,总是可以表现出指数行为.

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

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

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

为了快速了解为什么存在更好的实现并且从60年代开始,请参阅正则表达式匹配可以简单快速.

不太实用的选择:

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

好的实施:

• RE2 - 一个谷歌开源库,旨在获得合理的PCRE兼容性减去反向引用.鉴于作者,我认为这是plan9的正则表达式lib的unix端口的继承者.
• TRE - 也主要与PCRE兼容,甚至可以进行反向引用,尽管使用那些你失去速度保证.它有一个超级漂亮的近似匹配模式!

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

Answer 1

首先,你的建议是可能的,你当然知道你的主题.您还知道不使用反向引用实现的权衡是内存.如果你足够控制你的环境,这可能是一个合理的方法.

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

对于阅读此内容并且"忽略了重点"的人,这里有一些背景阅读:

• 正则表达式匹配可以简单快速

在同一个站点上,此页面上链接了许多实现.

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

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

显然,这些都不是C#/ .Net,我不知道是哪一个.