电子邮件类似的正则表达式灾难性回溯

Question

我想匹配电子邮件的开头，即：

1. 1个字符（来自字母和数字）
2. 0或1个点
3. 1个或多个字符
4. {第2和第3点}的重复次数为0或更多次
5. @字符

我一直在Regex101上尝试应用正则表达式\w(\.?\w+)*@。

我遇到了灾难性回溯的错误。我做错了什么？这个正则表达式正确吗？

- Bartłomiej Szałach

---

我正在将此正则表达式应用于 http://pastebin.com/dQwUHeS0。 - Bartłomiej Szałach

特别是这种形式的赋值，但总的问题是关于匹配这种类型的文本。我知道“不能用正则表达式解析[X]HTML” :) - Bartłomiej Szałach

@WiktorStribiżew 原始问题中提到了0或1个点。 - eddiem

1 还是 0？\w(\.\w+)?@ - Wiktor Stribiżew

抱歉，我原本想说的是\w+(\.\w+)?@，但现在我看到你需要的是\w+(\.\w+)*@，甚至是^\w+(\.\w+)*@。 - Wiktor Stribiżew

Answer 1

问题

当字符串的一部分可以以多种不同的方式匹配正则表达式时，就会发生“灾难性回溯”，因此需要反复尝试确定字符串是否实际匹配。一个简单的例子：正则表达式a+a+b匹配两个或更多个a后跟一个b。如果在aaaaaaaaaaa上运行它，问题就出现了：首先，第一个a+匹配所有内容，但在第二个a+处失败。然后，它尝试将第一个a+与除一个a之外的所有内容匹配，第二个a+与一个a匹配（这是“回溯”），然后在b上失败。但是正则表达式并不“聪明”到足以知道它可以停在那里 - 因此必须继续按照这个模式进行下去，直到尝试给第一个和第二个分配一些a的每个拆分为止。一些正则表达式引擎将意识到它们陷入了困境，并在经过足够的步骤后退出，显示您看到的错误。

针对您的特定模式：您拥有的内容匹配任何数量的字母或数字，混合任何数量的 . 其中 . 不能在第一个字符后面跟随@。唯一的额外限制是不能有两个相邻的点。实际上，这与我的示例相同： * 应用于包含 + 的部分，就像多个重复的 + 部分一样。

原子分组

您可以尝试使用原子分组。基本上它表示“一旦找到任何匹配项，请不要回溯到它”。毕竟，如果您已经找到了一些/w，它不会包含/.，也没有必要不断重新检查 - 点不是字母或数字，而且这些都不是@。

在这种情况下，结果将是\w(?>\.?\w+)*@。请注意，并非所有正则表达式引擎都支持原子分组，尽管您链接的那个支持。如果字符串仅匹配，则不会更改任何内容 - 如果不匹配或包含非匹配项，则处理步骤将减少。使用评论中@eddiem的示例，使用原始方法在166311步中找到两个匹配项，但添加原子分组仅需要623步。

占有量词

另一个选择是使用占有量词 - \w(\.?\w+)*+@大致意思相同。*+具体来说，“星号匹配的任何内容都不会在其中回溯”。在上述情况下，它在558步内匹配 - 但意思略有不同，它将所有重复视为一个原子值，而不是多个不同的原子值。我认为在这种情况下没有区别，但在某些情况下可能会有区别。同样，并非所有正则表达式引擎都支持。

- Vivian

---

很不幸，我不想要有两个点连在一起。 - Bartłomiej Szałach

@BartłomiejSzałach 已调整。 - Vivian

Answer 2

在嵌套量词的情况下，如果内部组包含至少一个可选子模式，则通常会出现灾难性回溯，使量化的子模式与外部组前面的子模式匹配，而外部组不在模式的末尾。

您的正则表达式引起了问题，因为(\.?\w+)*不在末尾，有一个可选的\.?，表达式缩减为\w(\w+)*@。

例如aaa.aaaaaa.a.aa.aa，但现在是aaa..aaaa.a

您需要的是

^\w+(?:\.\w+)*@

请查看正则表达式演示

• ^ - 字符串开始（避免部分匹配）
• \w+ - 一个或多个单词字符
• (?:\.\w+)* - 零个或多个序列：
  • \. - 一个字面点
  • \w+ - 一个或多个单词字符
• @ - 一个字面 @ 字符。

- Wiktor Stribiżew