为了账号安全,请及时绑定邮箱和手机立即绑定

正则表达式:确定两个正则表达式是否可以匹配相同的输入?

/ 猿问

正则表达式:确定两个正则表达式是否可以匹配相同的输入?

扬帆大鱼 2019-12-27 09:57:46

我想找出两个已知的正则表达式之间是否可能存在冲突,以便允许用户构造一个互斥的正则表达式列表。


例如,我们知道下面的正则表达式完全不同,但是它们都匹配xy50:


'^xy1\d'

'[^\d]\d2$'

是否可以使用计算机算法确定两个正则表达式是否存在这种冲突?怎么样?


查看完整描述

3 回答

?
慕盖茨9453107

这里没有暂停问题。您所需要做的就是计算^xy1\d和的交集是否[^\d]\d2$为非空。


我在这里无法给您提供算法,但是下面是关于不使用DFA构造而生成交集的方法的两次讨论:


http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html

然后是愤怒


http://www.complang.org/ragel/

它也可以计算正则表达式的交集。


更新:我只是用OP的正则表达式试用了Ragel。Ragel可以从生成的状态机中为graphviz生成一个“点”文件,这是了不起的。OP的regexp的交集在Ragel语法中看起来像这样:


('xy1' digit any*) & (any* ^digit digit '2') 

并具有以下状态机:


而空路口:


('xy1' digit any*) & ('q' any* ^digit digit '2')

看起来像这样:


因此,如果所有其他方法都失败了,那么您仍然可以让Ragel通过比较生成的“点”文件来计算相交并检查其是否输出了空状态机。


查看完整回答
反对 回复 2019-12-27
?
慕尼黑8549860

问题可以用“两个或多个正则表达式描述的语言是否具有非空交集”来重新描述吗?

如果将问题限制为纯正则表达式(没有反向引用,超前,向后查找或其他允许识别上下文无关或更复杂语言的功能),则该问题至少是可确定的。规则语言在交集下是封闭的,并且有一种算法将这两个正则表达式作为输入并在有限时间内生成可识别交集的DFA。

每个正则表达式可以转换为不确定的有限自动机,然后转换为确定的有限自动机。可以将一对DFA转换为可识别相交的DFA。如果存在从开始状态到最终DFA的任何接受状态的路径,则交集为非空(使用您的术语来说是“冲突”)。

不幸的是,当将初始NFA转换为DFA时,可能会出现指数爆炸,因此,随着输入表达式大小的增加,该问题在实践中很快变得不可行。

而且,如果允许对纯正则表达式进行扩展,那么所有的赌注都将失效-此类语言将不再在交集下关闭,因此该构造将无法正常工作。


查看完整回答
反对 回复 2019-12-27
?
慕尼黑的夜晚无繁华

是的,我认为这是可以解决的:除了将正则表达式视为匹配字符串之外,您还可以将它们视为生成字符串。也就是说,它们将匹配的所有字符串。

令[R]为正则表达式R生成的字符串集。然后将正则表达式R和T赋予正则表达式,我们可以尝试将T与[R]进行匹配。也就是说[R]匹配T,如果[R]中有匹配T的字符串。

应当有可能将其开发为一种算法,其中[R]可以根据需要延迟构造:常规正则表达式匹配将尝试匹配输入字符串中的下一个字符,然后前进到字符串中的下一个字符,这是经过修改的算法将检查与输入正则表达式相对应的FSM是否可以在其当前状态生成匹配字符,然后同时前进到“所有下一个状态”。


查看完整回答
反对 回复 2019-12-27

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信