如何避免正则表达式中的灾难性回溯？

Question

我正在尝试为字符串测试创建一个正则表达式。

基本上我想要的是something-something。

'a' ===> TRUE
'abc' ===> TRUE
'a-b' ===> TRUE
'-' ===> FALSE
'a-' ===> FALSE
'-b' ===> FALSE

于是第一个版本的正则表达式诞生了。

/^[\w]+[-\s]?[\w]+$/

它工作得很好，但如果字符串只有一个字母，则无法通过。

'a', failed

所以我修改了这个模式

^[\w]+([-\s]?[\w]+)*$

这段代码是可以工作的，但如果被测试的字符串很长（比如20个或更多字母），则浏览器会卡住，而且我知道发生了什么，那就是“灾难性回溯”。

那么在这种情况下，我该如何改进它呢？

更新：

我想我错过了一个场景，它应该也支持重复组。

aaa aaa aaa aaa ===> TRUE
aaa-aaa aaa-aaa ===> TRUE

这就是为什么我用了括号来创建这个组。

- SPG

Answer 1

您遇到的问题是模式([-\s]?[\w]+)*中的双重重复 - 您允许一个或多个\w和一个可选的空格或破折号。该组还重复零次或多次，这将导致灾难性回溯，因为可选的[-\s]意味着有许多方法可以匹配相同的输入。例如，abc可以被(\w\w\w)，(\w\w)(\w)，(\w)(\w\w)，(\w)(\w)(\w)匹配，正则表达式引擎将尝试所有这些可能性，因为模式([-\s]?[\w]+)*（或通过删除破折号使其更加明显([\w]+)*）允许这样做。

当模式的结尾无法匹配时，将尝试所有可能性。例如，对于输入“aaa-”，最后一个“-”将失败，但正则表达式引擎将继续回溯并检查所有排列组合。

相反，您可以简化您的正则表达式为此：

/^\w+(?:[-\s]\w+)*$/

1. 如果只有一个项目，您不需要字符类 [\w] - 这不会改变任何内容，但删除方括号使其更易于阅读。
2. 如果您不想提取模式的后半部分，则可以使用 非捕获组 - (?:)。
3. 使整个模式的后半部分可选。这意味着您要么匹配\w+（一个或多个单词字符），要么匹配完整的\w+[-\s]\w+。引擎不会强制重新尝试失败的匹配。

最后一步是解决问题，其他只是轻微的清理。重要的是模式受到限制，不允许多种方式匹配错误的输入 - [-\s] 是必须的，\w+（至少一个）也是必须的，因此重复组 (?:[-\s]\w+)* 不会有重叠的匹配。如果我们手动扩展为 ([-\s]\w\w\w)、([-\s]\w\w)([-\s]\w) 和 ([-\s]\w)([-\s]\w\w)，就容易看出这不会匹配相同的输入。

const regex = /^\w+(?:[-\s]\w+)*$/;

const valid = [
  'a',
  'abc',
  'a-b',
  'aaa aaa aaa aaa',
  'aaa-aaa aaa-aaa',
  'a'.repeat(100),
  `a-${'a'.repeat(100)}`,
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}`,
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}`,
  `a ${'a'.repeat(100)} ${'a'.repeat(100)}`,
  `a ${'a '.repeat(100)}a`,
]

const invalid = [
  '-',
  'a-',
  '-b',
  'aaa aaa aaa aaa-',
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}-`,
  `a ${'a'.repeat(100)} ${'a'.repeat(100)} `,
  `a-${'-'.repeat(100)}`,
  `a ${' '.repeat(100)}`,
  `a-${'-'.repeat(100)}a`,
  `a ${'a '.repeat(100)}`,
  `-${'a'.repeat(100)}`,
  ` ${'a'.repeat(100)}`,
  `${'a'.repeat(100)}-`,
  `${'a'.repeat(100)} `,
  `a-${'a'.repeat(100)}-${'a'.repeat(100)}-`,
  `a-${'-'.repeat(100)}`,
  `a-${'a-'.repeat(100)}`,
  `-${'a'.repeat(100)}`,
  `${'a'.repeat(100)}-`,
]

console.log('---- VALID ----');
for (const s of valid) 
  test(s);

console.log('---- INVALID ----');
for (const s of invalid) 
  test(s);


function test(str) {
  console.log(`${str} ===> ${regex.test(str)}`);
}

- VLAZ

Answer 2

这对我有用，融入了@VLAZ的反馈。指定开始^、结束$和可选字符分组(-\w+)?是关键组成部分。

编辑：融合空格需要将(-\w+)?更改为([-\s]\w+)*，这将匹配空格或连字符后面的任意字符序列，然后至少一个单词字符。

const pattern = /^\w+([-\s]\w+)*$/;
const tests = [
  'a', // ===> TRUE
  'abc', // ===> TRUE
  'a-b', // ===> TRUE,
  'aaa aaa aaa aaa', // ===> TRUE
  'aaa-aaa aaa-aaa', // ===> TRUE
  '-', // ===> FALSE
  'a-', // ===> FALSE
  '-b', // ===> FALSE,
];

console.log(tests.map(test => pattern.test(test)));

// performance
const start = performance.now();
const perf = `${'a'.repeat(1000)}-${'a'.repeat(1000)} ${'b'.repeat(1000)}-${'b'.repeat(1000)}`;
console.log(`${perf.length} char string took ${performance.now() - start}ms. Got result: ${pattern.test(perf)}`);

- Lewis

---

我会选择\w+(?:-\w+)?。当你将第二部分设为可选时，这种方式更简单。 - VLAZ

@VLAZ，我喜欢这种模式可以让我直接读取并准确判断其匹配情况。 - Lewis

还有@VLAZ，该模式匹配最后两个。=( - Lewis

是的，为了简洁起见，我没有添加锚点，这就是为什么它匹配的原因。我的重点是展示正则表达式的主体部分。 - VLAZ

Answer 3

使用非捕获组来避免灾难性回溯，确保程序正常运行。

^\w+(?:[-|\s]\w+)*$

- SPG