regex - 没有灾难性回溯的简单字母数字正则表达式(单间距)

Question

我有以下 REGEX 表达式(有效)以允许字母数字(以及 ' 和 -)并且没有双倍间距:

  ^([a-zA-Z0-9'-]+\s?)*$

由于嵌套分组，这会导致灾难性回溯发生——这很糟糕!

我怎样才能简化这个表达式来避免灾难性回溯？？(理想情况下，这也不允许在第一个和最后一个字符中使用空格)

Answer 1

解释

嵌套组不会自动导致灾难性的回溯。在您的情况下，这是因为您的正则表达式退化为灾难性回溯的经典示例 (a*)*。

由于 \s 在 ^([a-zA-Z0-9'-]+\s?)*$ 中可选，在输入时没有任何空格但有超出允许列表的字符，正则表达式简单地退化为 ^([a-zA-Z0-9'-]+)*$。

您还可以考虑扩展原始正则表达式:

[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?[a-zA-Z0-9'-]+\s?...

因为 \s 是可选的，我们可以删除它:

[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+[a-zA-Z0-9'-]+...

然后我们得到了一系列连续的[a-zA-Z0-9'-]+，它们会尝试各种方式在它们之间分配字符并增加复杂性。

解决方案

编写正则表达式以匹配 token delimiter token ... delimiter token 的标准方法是 token (delimiter token)*。虽然可以重写正则表达式以避免重复 token，但我建议不要这样做，因为很难做到正确。为避免重复，您可能希望通过字符串连接来构造正则表达式。

按照上面的方法:

^[a-zA-Z0-9'-]+(\s[a-zA-Z0-9'-]+)*$

虽然您可以在这里看到重复，但没有灾难性的回溯，因为正则表达式只能扩展为:

[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+\s[a-zA-Z0-9'-]+...

并且 \s 和 [a-zA-Z0-9'-] 是互斥的 - 只有一种方法可以匹配任何字符串。