如何使这个正则表达式不会导致“灾难性回溯”？

Question

我正在尝试使用从http://daringfireball.net/2010/07/improved_regex_for_matching_urls获取的URL匹配正则表达式。

(?xi)
\b
(                       # Capture 1: entire matched URL
  (?:
    https?://               # http or https protocol
    |                       #   or
    www\d{0,3}[.]           # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}/  # looks like domain name followed by a slash
  )
  (?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                       # End with:
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                               #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)

根据另一个问题的答案，似乎有些情况会导致这个正则表达式出现灾难性回溯。例如：

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA)")

...执行起来可能需要很长时间（例如在Chrome中）

我认为问题出在代码的这部分：

(?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]+|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+

...这似乎大致相当于(.+|\((.+|(\(.+\)))*\))+，其中包含(.+)+

有没有我可以做出的更改来避免这种情况？

- David Ingersol

---

实际上，你应该放弃这个正则表达式，并想出一个能够满足你需求的正则表达式。我还没有见过一个既足够轻松使用正则表达式进行URL解析（而不是真正的解析器），又严肃到需要处理URL中嵌套括号的应用程序。从“https?://”开始，一直到第一个应该在正确的URL中进行百分比编码但没有进行编码的字符，几乎可以处理所有情况，并且不会导致正则表达式匹配器呈指数增长。 - Kyle Jones

你试过 Rubular 吗？它下面有一个方便的备忘单，你可以添加各种测试表达式来确保它的工作。 （附言：我知道这是为 js 设计的，但这仍然是一个非常方便的资源。）http://rubular.com/ - Edwin

Answer 1

将其更改为以下内容应该可以防止灾难性回溯：

(?xi)
\b
(                       # Capture 1: entire matched URL
  (?:
    https?://               # http or https protocol
    |                       #   or
    www\d{0,3}[.]           # "www.", "www1.", "www2." … "www999."
    |                           #   or
    [a-z0-9.\-]+[.][a-z]{2,4}/  # looks like domain name followed by a slash
  )
  (?:                       # One or more:
    [^\s()<>]+                  # Run of non-space, non-()<>
    |                           #   or
    \(([^\s()<>]|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
  )+
  (?:                       # End with:
    \(([^\s()<>]|(\([^\s()<>]+\)))*\)  # balanced parens, up to 2 levels
    |                               #   or
    [^\s`!()\[\]{};:'".,<>?«»“”‘’]        # not a space or one of these punct chars
  )
)

唯一的修改是在正则表达式中的每个“平衡括号”部分的第一个[^\s()<>]后面删除了+。

以下是用JS进行测试的单行版本：

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA")

原始正则表达式的问题部分是平衡的括号部分。为了简化解释回溯发生的原因，我将完全删除其中嵌套括号的部分，因为这里与本题无关:

\(([^\s()<>]+|(\([^\s()<>]+\)))*\)    # original
\(([^\s()<>]+)*\)                     # expanded below

\(                # literal '('
(                 # start group, repeat zero or more times
    [^\s()<>]+        # one or more non-special characters
)*                # end group
\)                # literal ')'

考虑字符串'(AAAAA'的情况。括号(会匹配并将AAAAA作为组消耗掉，而)无法匹配。此时，该组会放弃一个A，剩下的AAAA被捕获，并尝试从此处继续进行匹配。由于该组后面跟着一个*，因此该组可以多次匹配，所以现在([^\s()<>]+)*会匹配AAAA，然后在第二次匹配时匹配到A。当这种情况失败时，原始捕获会再放弃一个A，然后由第二个捕获消耗掉。

这样会持续很长时间，导致以下尝试进行匹配，逗号分隔的每个组表示组被匹配的不同时间和该实例匹配的字符数:

AAAAA
AAAA, A
AAA, AA
AAA, A, A
AA, AAA
AA, AA, A
AA, A, AA
AA, A, A, A
....

我可能数错了，但我相当确定在确定正则表达式无法匹配之前需要16步。随着您继续向字符串中添加其他字符，找出这一点所需的步骤数量呈指数增长。

通过删除“+”并将其更改为“\(([^\s()<>\])*\)”，您可以避免这种回溯情况。

重新添加交替以检查嵌套括号不会引起任何问题。

请注意，您可能希望向字符串结尾添加某种锚定，因为当前，“http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA”将匹配到刚好在“(”之前，所以“re.test（...）”将返回true，因为“http://google.com/?q=”匹配。

- Andrew Clark

---

不错的回答。@David - 除了F.J的建议之外，你还应该尝试使用原子分组技巧来获得更快的速度。 - Steve Wortham

@SteveWortham - 我认为原子组可能会破坏这个，看看这个JSFiddle。正则表达式(?=([abc]))\1*将变成等价于a*、b*或c*，具体取决于首先从[abc]中看到的字符。 - Andrew Clark

啊，看起来我没有充分测试它。 - Steve Wortham