gpt4 book ai didi

javascript - 我怎样才能使这个正则表达式不导致 "catastrophic backtracking"?

转载 作者:数据小太阳 更新时间:2023-10-29 05:10:51 25 4
gpt4 key购买 nike

我正在尝试使用从 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
)
)

基于对 another question 的回答, 似乎有些情况导致此正则表达式为 backtrack catastrophically .例如:

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
)+

... 这似乎大致等同于 (.+|\((.+|(\(.+\)))*\))+,看起来它包含(.+)+

我能做些什么来避免这种情况吗?

最佳答案

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

(?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()<>])*\) ,您将避免这种回溯情况。

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

请注意,您可能希望在字符串末尾添加某种 anchor ,因为当前 "http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA"将匹配到 ( 之前, 所以 re.test(...)会返回 true因为http://google.com/?q=匹配。

关于javascript - 我怎样才能使这个正则表达式不导致 "catastrophic backtracking"?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10218594/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com