没有灾难回溯的简单字母数字正则表达式（单个间距）

Question

我有以下REGEX表达式（有效）以允许字母数字（以及'和-）并且没有双倍空格：

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

由于嵌套分组，因此可以进行灾难性的回溯-太糟糕了！

如何简化此表达式以避免灾难性回溯？ （理想情况下，第一个和最后一个字符都不允许有空格）

Answer 1

说明嵌套组不会自动导致灾难性的回溯。在您的情况下，这是因为您的正则表达式退化为灾难性回溯的经典示例(a*)*。由于\s在可选in中^([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)*。虽然可以重写regex避免重复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'-]是互斥的-只有一种方式来匹配任何字符串。