当正则表达式包含 重复 组（例如 ^(one|two)*done$）时，它对于组的每次重复都有两个 备选方案 可供尝试。理论上，此正则表达式应匹配一个包含任意长序列 oneoneone…done 的字符串。实际上，回溯正则表达式引擎在某个时刻必须放弃。

如果正则表达式引擎使用递归算法，则组的每次重复都会向引擎的调用堆栈添加一个调用。当引擎实际需要进行的重复次数超过可用堆栈空间时，引擎将放弃甚至崩溃。

即使引擎是非递归的，它仍必须在每次重复时跟踪组的匹配尝试开始的位置。这是必需的，以便当正则表达式的其余部分无法匹配时，引擎可以回溯。在尝试匹配 oneoneone 时，引擎重复组 3 次。它在每次重复之前为量词存储一个回溯位置。交替运算符也在每次尝试时存储一个回溯位置。在 3 次重复之后，done 无法匹配字符串末尾。现在，引擎按相反的顺序遍历 6 个回溯位置。它在交替运算符的每个回溯位置尝试 two。它在量词的每个回溯位置尝试 done。该过程完全是线性的。即使字符串重复 one 数千次，正则表达式也会立即匹配或不匹配，具体取决于字符串末尾是否有 done。

但是，如果你对重复 one 数百万次的字符串使用此正则表达式，那么你可能会遇到正则表达式引擎的限制，该限制旨在防止其因试图记住所有这些回溯位置而耗尽内存。这可能会阻止引擎找到极长的匹配项。

上面的示例通过使用 捕获组 使情况变得更糟。在成功匹配结束时，捕获组将保存字符串中 one 或 two 的最后一次出现。但在匹配尝试期间，它还保存 one 或 two 的最近匹配，每次迭代都会保存。这会导致每次迭代组和每次回溯到组时，正则表达式引擎都会产生额外的工作。

使用非捕获和原子组进行优化

我们可以优化此正则表达式，以减少正则表达式引擎必须完成的工作量。这些是适用于所有正则表达式的良好技术。即使你只会在性能差异几乎无法衡量的较短字符串上使用正则表达式，也应该将它们视为良好的编码习惯。

首先，仅在你确实想要捕获正则表达式匹配的一部分时才使用捕获组。否则，你始终可以使用非捕获组。将没有反向引用的捕获组转换为非捕获组永远不会改变正则表达式应该匹配的内容。因此，^(?:one|two)*done$ 是我们的第一个优化。

在这种情况下，两个备选方案是互斥的。two 永远不会在 one 已匹配的位置匹配。因此，所有回溯都是不必要的。我们可以通过使用原子组来告诉正则表达式引擎：^(?>one|two)*done$。现在，正则表达式引擎每次重复该组时都会丢弃交替运算符的回溯位置。它不再尝试在 one 已匹配的位置匹配 two。

使用占有量词优化

但是量词 * 仍然会回溯。^(?>one|two)*done$ 仍然在量词回溯时尝试在 one 已匹配的每个位置匹配 done。为了停止此操作，我们可以使量词占有：^(?>one|two)*+done$。此正则表达式根本不会回溯。

此正则表达式是否真的可以匹配 oneoneone…done 的任意长序列取决于正则表达式引擎如何实现占有量词。如果占有量词根本不存储回溯位置，那么它可以。但在某些正则表达式风格中，占有量词是编写 ^(?>(?>one|two)*)done$ 的另一种方式。在这种情况下，量词仍然存储其所有回溯位置，仅当正则表达式引擎退出外部原子组时才将其丢弃。当 done 无法匹配时，这确实会提高性能。但如果正则表达式引擎受到量词可以存储的回溯位置数量的限制，则它不允许更长的成功匹配。

消除不必要的组

比将捕获组转换为非捕获组或原子组更好的方法是消除不必要的组。人们有时会不必要地对正则表达式标记进行分组，因为他们不理解正则表达式中运算符的优先级。交替运算符的优先级最低。它在正则表达式或包含它的组中交替匹配其左侧和右侧的所有内容。量词的优先级很高。它只重复它前面的标记或组。

所以 one|two* 将匹配 one、tw、two、twoo、twooo 等。我们需要该组重复交替，而不仅仅是最后的 o。但我们不需要在备选方案周围添加额外的组。在 (?:(?:one)|(?:two))* 中的两个嵌套组是不必要的。

(?:[ab])+ 也有一个不必要的组。字符类被视为单个正则表达式标记。量词可以直接重复它：[ab]+。

这些不必要的组有多大的影响取决于正则表达式引擎。如果你遵循使用非捕获组的建议，那么引擎可能能够优化掉不必要的组。但如果你有不必要的捕获组，它就无法做到这一点。正则表达式引擎无法知道你是否需要在之后检索捕获组匹配的文本，因此它无法删除它们。

重复单个标记

从理论上讲，^(?:a|b|c)+$ 和 ^[abc]+$ 是相同的。在实践中，大多数回溯引擎执行后者的速度要快得多。字符类可以同时尝试这两个字符。它不需要像交替运算符那样回溯来尝试其他字符。字符类的每次迭代都完全匹配一个字符。虽然量词可能需要回溯，但它不需要回溯位置来执行此操作。它只需要记住迭代次数即可。它可以通过在字符串中向后移动一个字符并递减迭代次数来进行回溯。这使得 ^[abc]+$ 能够匹配任何长度的字符串。

"(?:[^"]|\\.)*" 是一个简单的解决方案，用于匹配可能包含双引号的双引号字符串，如果双引号被反斜杠转义。我们允许换行，并假设 点 与它们匹配。

上面的正则表达式是正确的，因为它匹配所有双引号字符串，并且不匹配其他任何内容。但它过于简单，因为它执行得很差。至少它使用了一个非捕获组。如果我们翻转这两个备选方案，我们可以使用一个原子组（记住正则表达式引擎是 急切的）。但是，除非正则表达式引擎具有根本不存储回溯位置的所有格量词，否则只要我们为字符串中的每个字符重复该组，我们就无法让这个正则表达式匹配数百万个字符长的双引号字符串。

为了优化此正则表达式，我们需要重复否定字符类："(?:[^"\\]+|\\.)*"。这允许正则表达式快速匹配字符串中未转义字符的运行。由于未转义字符比转义字符更常见，这显著减少了正则表达式引擎需要记住的回溯位置数。外部组仅对每次未转义字符运行和每次转义字符运行重复一次。如果闭合引号匹配失败，两个量词仍将回溯。但大多数迭代将是内部量词，它可以更快地回溯。

请注意，否定字符类现在包括反斜杠。这确保了两个备选方案互斥。这是至关重要的。如果您注意到了灾难性回溯主题，那么您会注意到类似的嵌套量词模式。虽然我们的正则表达式在闭合引号匹配失败时会回溯，但它以线性方式进行，因为第二个备选方案永远无法匹配第一个备选方案匹配的字符。

我们可以将此优化更进一步。我们不需要对未转义字符运行重复该组，我们也不需要在转义字符和未转义字符之间交替。我们只需要该组来处理转义字符。"[^"\\]*(?:\\.[^"\\]*)*"将双引号字符串视为一系列零个或多个未转义字符，后跟零个或多个转义字符，每个转义字符后跟零个或多个未转义字符。现在，该组仅记住字符串中每个未转义字符的一个回溯位置。这使正则表达式能够匹配几乎任何长度的字符串。如果一个字符串包含数百万个转义字符，它只会遇到正则表达式引擎限制。如果闭合引号匹配失败，它将回溯。但所有回溯尝试都会立即失败，因为该组以\\.开头，而\\.与[^"\\]*互斥。

如果正则表达式引擎支持原子分组或占有量词，那么我们可以用"(?>[^"\\]*(?>\\.[^"\\]*)*)"或"[^"\\]*+(?:\\.[^"\\]*+)*+"为优化锦上添花。在尝试匹配闭合双引号时，这两个正则表达式都会丢弃所有回溯位置。因此，它们根本不会回溯。