如何将任意正则表达式转化为其补集，而不需要复杂的手动编辑？

Question

如何将任意正则表达式转化为其补集，而不需要复杂的手动编辑？

15

下面是伪代码示例，不是真正的正则表达式，但仍然是我想要表达的一个例子：

.* (anything)

-.* (NOT anything)

[A-Z] (Any letter A to Z, caps only)

-[A-Z] (NOT any letter A to Z, caps only)

编辑：在问题中将反转改为补集。这是更改所在的位置：“将任何正则表达式转换为其补集”。

- blunders

6个回答

9

只需运行正则表达式并逻辑反转输出即可。所以将：

if(/foo/)

to:

if(!/foo/)

使用前导符号，字符类可以被反转：

[A-Z] -> [^A-Z]

许多特殊字符也有相应的反义符号，如果将指定符号大写。

\s whitespace
\S non-whitespace
\w word character
\W non-word-character
\d digit
\D non-digit

- Eyal

1

完全正确的答案，而且显然是最简单的方法，尽管它只适用于整个正则表达式被反转的情况；如果您想否定正则表达式的一部分，它将无法工作。 - Spudley

@Eyal：仍在思考你的回答，这是不同的，但很好。我仍然相信我需要正则表达式的反转，而不是输出。谢谢您的发布！ - blunders

2

“需要”是指什么？作业吗？反函数到底是什么也不太清楚。 - Eyal

6

需要考虑的几种变化：

匹配由一组特定字符组成的字符串：^[a-z]*$

匹配由除了某组特定字符以外的任何字符组成的字符串：^[^a-z]*$

请注意，还有一些快捷方式：

\w：任何字母数字字符（包括_），
\W：任何非字母数字字符；
\s：任何空白字符，
\S：任何非空白字符，
\d：任何数字，
\D：任何非数字。

这可能会变得相当复杂，例如如果你想要...

只匹配非字母字符：[\d_\W]，或者
只匹配字母：[^\d_\W]（即“不是数字，不是_，也不是非字母数字字符”）

匹配包含子字符串的字符串：^.*substring.*$

匹配不包含子字符串的字符串：^(?:(?!substring).)*$

请注意，我们必须检查字符串中每个位置是否“不包含”子字符串。你还可以将任何正则表达式替换为substring，以匹配包含或不包含某个特定子正则表达式的字符串。

匹配任何内容：.*（如果你想要匹配换行符，你需要设置编程语言的相应选项，例如在Python中使用re.DOTALL）

如果你不知道如何设置该选项，则匹配任何内容：[\s\S]*

永远不要匹配任何内容（出于任何原因）：

$^（即在字符串开头之前匹配字符串结尾），
\b\B（匹配既是单词边界又不是单词边界的位置），或者
(?!)（匹配不能匹配空字符串的位置）。

- Tim Pietzcker

4

通过使用负向前瞻，您将能够处理大多数基本情况。

/(?!(OriginalRegex)).*?/

- Colin Hebert

@Colin_Hebert: 我怎么知道它不能处理“大多数基本情况”。谢谢！ - blunders

3

你的第一个例子没有意义，但对于第二个例子，你可以使用类字符否定：

[a-z] --> [^a-z]

- SilentGhost

@SilentGhost：哈，我知道这没有意义，所以我把它列为一个例子。感谢指出类字符否定，并给出一个例子！ - blunders

1

我正在尝试理解正则表达式的反向定义。

match(input, regular_expression) = {match1, match2, ..., matchN}

反向操作应该如何工作？是否应该像下面这样：

match(input, inverse_regular_expression) = {imatch1, imatch2, ..., imatchN}

如果是这样，第一组结果和第二组结果之间有什么关系？如果不是，那么它是什么？

- Uphill_ What '1

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eamon Nerbonne · Accepted Answer

首先，我相信你指的是正则表达式的补集，而不是它的逆。正则表达式的逆并没有太多意义；但如果将其视为函数，则可以说匹配器的逆是生成所有匹配字符串的生成器——或者类似的东西。另一方面，语言的补集是原始语言中所有不在其中的字符串。

然后，这里有两个要考虑的观点：

基本上

正则语言的补集是正则的。这意味着可以为补集生成一个可接受的DFA（实际上很简单：只需交换非接受状态集和接受状态集）。任何这样的DFA都可以表示为正则表达式——因此原则上确实可以制作这样的正则表达式。

请参阅维基百科文章Regular Languages作为起点。

实际上

现今大多数现代语言中使用的典型Perl兼容正则语法没有补集运算符。对于完整的正则表达式，您可以通过使用否定前瞻运算符(?!X)来获得类似的结果：当且仅当X不匹配时，它将匹配一个字符串。然而，这是补集运算符的一个较差的替代品，因为您将无法像通常那样将其用作更大正则表达式的一部分；此正则表达式不会“消耗”输入，这意味着它在与其他运算符结合时的行为不同。

例如，如果您将数字字符串匹配为[0-9]*，要匹配整个字符串，您需要在前面加上^并在后面添加$，但是要使用此技术查找补集，则需要编写^(?!^[0-9]*$).*$ - 而这样的否定正则表达式的通常串联，据我所知，是不可逆转的。

有点讽刺的是，正则表达式的实际化身在理论上更强大，因为它具有反向引用，但在实践中却不太灵活，因为语言不能很容易地表达补集和交集操作。