re.search() in python 进入无限循环

Question

我正在尝试从文本文档中提取文件路径（Windows/Ubuntu、relative/absolute）。

下面的正则表达式代码用于检查一个单词是否为文件路径。

它适用于大多数情况，但在一种情况下失败，它会进入无限循环。有什么解释吗？

import re
path_regex = re.compile(r'^([\.]*)([/]+)(((?![<>:"/\|?*]).)+((?<![ .])(\|/))?)*$' , re.I)
text = '/var/lib/jenkins/jobs/abcd-deploy-test-environment-oneccc/workspace/../workspace/abcd-deploy-test-environment.sh'
path_regex.search(text)

Answer 1

确实有问题
您已经覆盖了与虚假量词混合的子表达式。

修改了斜线之间的必填部分
使用这个 ^([\.]*)([/]+)((?:[^<>:"/\|?*.\r\n]|\.(?![\/]))[\/]?)*$

很容易修复

主要是看你在防什么。
守卫是，如果前面没有点，则允许使用正斜线或反斜线。

因此，您必须在排除 class 中包含点以及 \ 和 /
然后在单独的交替中对它们进行限定。

如果你这样做，它总是会通过的。

 ^ 
 ( [\.]* )                     # (1)
 ( [/]+ )                      # (2)
 (                             # (3 start)
      (?:                           # Group start (required between slashes)
           [^<>:"/\|?*.\r\n]            # Any character, but exclude these
        |                              # or,
           \.                            # The dot, if not followed by forward or back slash
           (?! [\/] )
      )                             # Group end
      [\/]?                        # Optional forward or back shash
 )*                            # (3 end)
 $

Answer 2

sln 很好地解决了你的问题，所以我会尝试解释一下问题是什么。

欢迎来到 catastrophic backtracking 的欢乐世界。你的问题的核心在(((?![<>:"/\|?*]).)+((?<![ .])(\|/))?)*。（既然我这么说了，你的问题就都解决了吧？简单易行。）

假设您有点像我，并且在第一次有人说 "regex backtracking" 时茫然地眨了几次眼睛，我们可以使用较短的输入 /path./ 来处理您的正则表达式。根据您的正则表达式，这是一条无效路径，但让我们（在某种程度上）轻松解决了这个问题。

^([\.]*)([/]+) 匹配前导 /。这很好用。

为了这里的可读性，我将调用有问题的捕获组的前半部分，((?![<>:"/\|?*]).)+，x+，以及后半部分，((?<![ .])(\|/))?， y?。整个群是(x+y?).

匹配`path./`时`(x+y?)*$`如何回溯？

x+ 匹配 path.
y? 匹配 </code>（它匹配 0 次，这很好，因为 <code>?）
(x+y?)现在匹配了一次
(x+y?) 重复并失败，因为它不匹配 /。因此，(x+y?)* 匹配了 path.
$ 失败，因为它不匹配 /.
正则表达式引擎回溯：
- (x+y?)* 只能回溯到它的第一次迭代，因为它只有一次迭代。
- 在那次迭代中，y? 无法回溯，因为它匹配了 0 次。
- x+ 回溯，只匹配 path 而不是 path.
x+ 匹配 path
y? 匹配 </code></li> <li><code>(x+y?) 现在匹配了一次 (path)
(x+y?) 重复并再次匹配：
- x+ 匹配 .
- y? 匹配 </code></li> </ul></li> <li><code>(x+y?) 重复，但由于不匹配 / 而失败。因此，(x+y?)* 匹配了 path.
- $ 失败，因为它不匹配 /.
- 正则表达式引擎回溯：
  - (x+y?)* 只能回溯到它的第一次迭代，因为在它的第二次迭代中 x+ 只匹配了一次而 y? 匹配了 0 次。
  - y?在第一次迭代中匹配了0次，所以无法回溯
  - x+ 可以回溯到只匹配 pat
- 希望您明白了，但是 (x+y?) 匹配了两次：pat、h.；然后在下一个回溯中我们有 pat h .，然后是 pa th.，依此类推。

引擎需要 478 步才能确定 /path./ 与您的正则表达式不匹配。有问题的捕获组中的每个额外字符都会增加 lot 的回溯数量，并且在某个点之后，您的正则表达式实现将放弃它的手并放弃。 sln的解决方案只需要49步。

正则表达式引擎在回溯时的行为既难以解释又难以掌握，尤其是在仅限于 Markdown 时，因此我建议通过 a debugger 运行您的正则表达式来可视化正在发生的事情.

re.search() in python 进入无限循环

re.search() in python goes into an infinite loop

python

regex

text-mining

regular-language

匹配`path./`时`(x+y?)*$`如何回溯？

re.search() in python 进入无限循环

re.search() in python goes into an infinite loop

python

regex

text-mining

regular-language

匹配path./时(x+y?)*$如何回溯？

匹配`path./`时`(x+y?)*$`如何回溯？