正则expression式:确定两个正则expression式是否可以匹配相同的input?

我想知道两个已知的正则expression式之间是否会有冲突 ,以便让用户构造一个互斥的正则expression式列表。

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

 '^xy1\d' '[^\d]\d2$' 

是否有可能使用计算机algorithm确定两个正则expression式是否可以产生这样的冲突 ? 怎么样?

这里没有涉及到的停滞问题。 所有你需要的是计算非空的^xy1\d[^\d]\d2$的交点。

在这里我不能给你一个algorithm,但是这里有两个方法来生成交集,而不是诉诸DFA的构build:

然后是RAGEL

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

更新:我刚刚用OP的正则expression式来试用Ragel。 Ragel可以从生成的状态机中为graphviz生成一个“点”文件,这非常棒。 在Ragel语法中,OP的正则expression式的交集看起来像这样:

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

并具有以下状态机:

替代文字http://i36.tinypic.com/28lqbf4.png

而空的十字路口:

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

看起来像这样:

替代文字http://i33.tinypic.com/dxxp2x.png

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

这个问题可以重申为“两个或多个正则expression式描述的语言是否有非空的交集”?

如果将问题局限于纯正则expression式(无反向引用,前瞻,后向或允许识别上下文无关语言或更复杂语言的其他function),问题至less是可以确定的。 正则语言在交叉点处被closures,并且有一个algorithm将两个正则expression式作为input,并在有限时间内生成识别交集的DFA。

每个正则expression式都可以转换为非确定型有限自动机,然后转换为确定型有限自动机。 一对DFA可以转换为识别交叉点的DFA。 如果从开始状态到最终DFA的任何接受状态都有path,则交集非空(使用您的术语为“冲突”)。

不幸的是,在将初始NFA转换为DFA时,可能会有指数式的放大,因此在实际中,随着inputexpression式的增长,问题很快就变得不可行。

如果允许对纯正则expression式进行扩展,则所有的注单都closures – 这些语言在交叉点下不再closures,所以这种构造将不起作用。

我在python中使用了这个包: http : //qntm.org/greenery

是的,我认为这是可以解决的:不要把正则expression式看作是匹配的string,你也可以把它们想象成生成string。 也就是说,他们会匹配的所有string。

设[R]是由正则expression式R生成的string集合。然后给定正则expression式R和T,我们可以尝试将T与[R]匹配。 如果[R]中有一个与T相匹配的string,那么[R]匹配T

应该有可能将其发展为一种algorithm,其中[R]按照需要进行延迟构build:在正常的正则expression式匹配将尝试匹配inputstring中的下一个字符,然后前进到string中的下一个字符,修改后的algorithm将检查对应于input正则expression式的FSM是否可以在其当前状态下生成匹配字符,然后同时前进到“所有下一个状态”。