给定多个正则表达式，我们能否编写一个等于它们交集的正则表达式？
例如，给定两个正则表达式 c[a-z][a-z] 和 [a-z][aeiou]t，它们的交集包含 cat 和 cut，以及可能还有其他字符串。那么我们如何编写一个正则表达式来表示它们的交集呢？
谢谢。
正则表达式能匹配两个正则表达式之间的交集吗？
18
- Tim
2
3你对数学正则表达式感兴趣，还是对一些特定的实际应用，比如 PCRE 有兴趣？ - n. m.
@n.m.: 在两种语言中都可以实现，Python或Perl。 - Tim
5个回答
12
正则表达式中的逻辑 AND 用以下方式表示：
(?=...)(?=...)
因此，
(?=[a-z][aeiou]t)(?=c[a-z][a-z])
- Derek 朕會功夫
3
你在我添加了答案的前几秒钟就发布了这个帖子，我们一定是心灵感应了。 :) - zx81
谢谢。但是如果我想将交集中的字符串与一个字符串匹配怎么办？预查不会返回匹配项。请参见我的问题：https://dev59.com/UoDba4cB1Zd3GeqPFYYQ - Tim
如果我在模式周围加上括号，lookaheads 就会返回匹配结果：
(?=(c[a-z][a-z]))(?=([a-z][aeiou]t)) - undefined11
前瞻示例很容易使用，但从技术上讲不再是正则语言。然而，可以取两个正则语言的交集，其补集是正则的。
首先注意，正则表达式可以转换为和从NFA中；它们都是表示正则语言的方法。
其次，根据德摩根定理,
因此，以下是计算两个正则表达式交集的步骤:
- 将两个正则表达式转换为NFA。
- 计算两个NFA的补集。
- 计算这两个补集的并集。
- 计算该并集的补集。
- 将得到的NFA转换为正则表达式。
一些参考资料:
- Colonel Thirty Two
1
1NFA的补集大小可能呈指数级增长。 - n. m.
6
数学上讲，两个正则语言的交集是正则的，因此必须有一个正则表达式来接受它。最简单的方法是通过相应的NFA构建它。考虑对应于两个正则表达式的两个NFA。新状态Q是来自两个NFA的一对(Q1,Q2)。如果第一个NFA中存在(P1,x,Q1)的转换和第二个NFA中存在(P2,x,Q2)的转换，那么只有当在新的NFA中存在((P1,P2),x,(Q1,Q2))的转换时才成立。当且仅当Q1和Q2都是初始/终止状态时，新状态(Q1,Q2)是初始/终止的。
如果您使用带有ε-moves的NFA，则对于每个转换(P1,ε,Q1)，对于所有状态P2，都会有一个转换((P1,P2),ε,(Q1,P2))。第二个NFA中的ε-moves也是如此。
现在，使用任何已知算法将新的NFA转换为正则表达式，就完成了。
至于PCRE，严格来说，它们不是正则表达式。通常情况下无法实现。有时可以使用lookaheads，例如
如果您使用带有ε-moves的NFA，则对于每个转换(P1,ε,Q1)，对于所有状态P2，都会有一个转换((P1,P2),ε,(Q1,P2))。第二个NFA中的ε-moves也是如此。
现在，使用任何已知算法将新的NFA转换为正则表达式，就完成了。
至于PCRE，严格来说，它们不是正则表达式。通常情况下无法实现。有时可以使用lookaheads，例如
^(?=regex1$)(?=regex2$)，但这仅适用于匹配整个字符串，对于搜索或嵌入其他正则表达式则不适用。如果没有定位，两个lookaheads可能会匹配不同长度的字符串。这不是交集。- n. m.
2
谢谢。但是如果我想将交集中的字符串与一个字符串匹配怎么办？向前查找不返回匹配项，锚点
$ 和 ^ 不允许在字符串中间进行匹配。请参见我的问题：https://dev59.com/UoDba4cB1Zd3GeqPFYYQ - Tim@Tim，你说得对，使用前瞻无法在字符串中间进行匹配。这是该方法的限制。 - n. m.
6
首先，让我们统一术语。我的语法假设是：
多个正则表达式的交集是一个正则表达式，可以匹配每个组件正则表达式也能匹配的字符串。
通用方法
要检查两个模式的交集，通用方法为（伪代码）：
if match(regex1) && match(regex2) { champagne for everyone! }
正则表达式选项
在某些情况下，您可以使用前瞻来完成相同的任务，但对于复杂的正则表达式而言，这样做几乎没有任何好处，除了使您的正则表达式更加晦涩难懂。为什么没有优势呢？因为引擎仍然必须多次解析整个字符串。
布尔“与”
用于检查字符串是否完全符合regex1和regex2的AND的一般模式如下：
^(?=regex1$)(?=regex2$)
$在每个前瞻中确保每个字符串都匹配模式且没有多余内容。当进行AND匹配时，
当然，如果你不只想检查AND的布尔值而是要实际进行匹配，在前瞻之后，你可以添加一个点-星号来消耗字符串：
^(?=regex1$)(?=regex2$).*
或者...在检查完第一个条件后，只需匹配第二个条件：
^(?=regex1$)regex2$
这是一种技术，例如在密码验证中使用。有关更多详细信息，请参见掌握向前和向后查找。 奖励部分：正则表达式的并集 不是在交集上工作，假设您对以下正则表达式的并集感兴趣，即匹配这些正则表达式中的任何一个正则表达式：
- catch
- cat1
- cat2
- cat3
- cat5
|来实现：catch|cat1|cat2|cat3|cat5
此外，这样的正则表达式通常可以被压缩，例如：
cat(?:ch|[1-35])
- zx81
12
正则表达式（任何语言）能够实现这个吗？还是我们需要一些编程语言的帮助？ - Tim
我认为伪代码是用来测试一个字符串是否在它们的交集中，而不是实际表示它们交集中的所有字符串。 - Tim
我想编写一个正则表达式，它对应于给定正则表达式的交集。 - Tim
我认为你伪代码中的if语句只是用来测试一个字符串是否落在交集中。 - Tim
让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/55265/discussion-between-zx81-and-tim。 - zx81
显示剩余7条评论
0
对于 And 操作，我们在正则表达式中可以使用以下语法：
(REGEX)(REGEX)
以您的示例为例：
'Cat'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/)
["Cat", "C", "a", "t"]
'Ca'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/)
//null
'Cat123'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/)
//null
在哪里
([A-Za-z]+) //Match All characters
和
([aeiouAEIOU]+) //Match all vowels
将它们结合起来会匹配
([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)
例如:
'Hmmmmmm'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/)
//null
'Stckvrflw'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/)
null
'StackOverflow'.match(/^([A-Za-z]+)([aeiouAEIOU]+)([A-Za-z]+)$/)
["StackOverflow", "StackOverfl", "o", "w"]
- Harpreet Singh
6
我从这个链接学到了这个内容：
http://www.zorched.net/2009/05/08/password-strength-validation-with-regular-expressions/ - Harpreet Singh
谢谢！但在我看来，它似乎不太对。你是否意识到
=? 的意思是“匹配零次或一次等号”？这与 lookahead 无关。如果我误解了你的意图，请告诉我。 - zx81@zx81
是的，你说得对，省略“=”不影响解决方案，但输出会有所不同。
让我使用它的原因是'github'.match(/([A-Za-z]+=?)([aeiouAEIOU]+=?)([A-Za-z]+=?)/)["github", "gith", "u", "b"]'github'.match(/([A-Za-z]+?)([aeiouAEIOU]+=?)([A-Za-z]+=?)/)["github", "g", "i", "thub"]'github'.match(/([A-Za-z]+?)([aeiouAEIOU]+?)([A-Za-z]+=?)/)["github", "g", "i", "thub"]'github'.match(/([A-Za-z]+?)([aeiouAEIOU]+?)([A-Za-z]+?)/)["git", "g", "i", "t"] - Harpreet Singh
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接