正则表达式可以匹配两个正则表达式之间的交集？

Question

给定几个正则表达式,我们可以编写一个等于它们交集的正则表达式吗？

例如,给定两个正则表达式c[a-z][a-z]和[a-z][aeiou]t,它们的交集包含cat和cut 甚至更多.我们怎样才能为它们的交集写一个正则表达式？

谢谢.

Answer 1

正则表达式中的逻辑AND表示为

(?=...)(?=...)

所以,

(?=[a-z][aeiou]t)(?=c[a-z][a-z])

Answer 2

先行示例易于使用,但从技术上讲不再是常规语言.但是,可以采用两种常规语言的交集,并且该补语是常规的.

首先请注意,正则表达式可以转换为NFA和从NFA转换; 它们都是表达常规语言的方式.

第二,根据德莫根定律,

因此,这些是计算两个RegEx的交集的步骤:

• 将两个RegEx转换为NFA.
• 计算两个NFA的补充.
• 计算两个补语的联合.
• 计算该联盟的补充.
• 将生成的NFA转换为RegEx.

一些来源:

• 联盟和RegEx到NFA:http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_06.pdf
• NFA到RegEx:http://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf
• NFA的补充:https://cs.stackexchange.com/questions/13282/complement-of-non-deterministic-finite-automata

Answer 3

首先，让我们就条款达成一致。我的句法假设是

多个正则表达式的交集是一个正则表达式，它与每个组件正则表达式也都匹配的字符串匹配。

一般选择

要检查两个模式的交集，通常的方法是（伪代码）：

if match(regex1) && match(regex2) { champagne for everyone! }

正则表达式选项

在某些情况下，您可以对前瞻进行相同的操作，但对于复杂的正则表达式而言，这样做几乎没有好处，除了使您的正则表达式对敌人更加模糊之外。为什么收益不大？因为引擎无论如何都要多次解析整个字符串。

布尔AND

与检查字符串完全符合regex1和regex2的AND的一般模式是：

^(?=regex1$)(?=regex2$)

$每个前瞻中的in确保每个字符串与模式匹配，仅此而已。

与时匹配

当然，如果您不想只检查AND的布尔值，而且还想进行一些实际匹配，则在先行查找之后，可以添加点星号来使用该字符串：

^(?=regex1$)(?=regex2$).*

或者...在检查了第一个条件之后，只需匹配第二个条件：

^(?=regex1$)regex2$

这是例如密码验证中使用的一种技术。有关此的更多详细信息，请参见精通Lookahead和Lookbehind。

奖励部分：正则表达式联合

假设您对以下正则表达式的并集感兴趣，而不是在相交处工作，即，与两个正则表达式匹配的正则表达式：

1. 抓住
2. 猫1
3. 猫2
4. 猫3
5. 5类

这是通过交替|运算符完成的：

catch|cat1|cat2|cat3|cat5

此外，此类正则表达式通常可以压缩，如下所示：

cat(?:ch|[1-35]) 

Answer 4

从数学上讲,两种常规语言的交集是规则的,因此必须有一个接受它的正则表达式.

通过相应的NFA构建它可能是最简单的.考虑与两个正则表达式相对应的两个NFA.新状态Q是来自两个NFA的对(Q1,Q2).如果第一个NFA中存在转换(P1,x,Q1),第二个NFA中存在(P2,x,Q2),那么只有转换((P1,P2),x,(Q1,Q2) ))在新的NFA中.如果Q1和Q2都是初始/最终,则新状态(Q1,Q2)是初始/最终.

如果你使用具有ε-移动的NFA,那么对于每个转变(P1,ε,Q1),对于所有状态P2将存在转变((P1,P2),ε,(Q1,P2)).同样地,对于第二个NFA中的ε-移动.

现在使用任何已知算法将新NFA转换为正则表达式,就是这样.

至于PCRE,严格来说,它们不是正则表达式.在一般情况下无法做到这一点.有时您可以使用前瞻,^(?=regex1$)(?=regex2$)但这只适用于匹配整个字符串,对于搜索或嵌入其他正则表达式不利.没有锚定,两个前瞻可能最终匹配不同长度的字符串.这不是交集.