修复正则表达式中的灾难性回溯
Fixing Catastrophic Backtracking in Regular Expression
问题
我正在使用以下正则表达式来检查有效的文件路径：
^(?:[a-zA-Z]\:\|\\)([^\\/\:\*\?\<\>\"\|]+(\){0,1})+$
使用测试字符串V:\Sample Names\Libraries\DeveloperLib\DeveloperComDlgs\res被识别为有效。我什至可以毫无问题地将无效字符添加到字符串的开头。但是，当我在字符串末尾添加无效字符时，网页因灾难性回溯而冻结。
是什么原因导致此正则表达式字符串出现这种情况？
分解正则表达式
完整字符串： ^(?:[a-zA-Z]\:\|\\)([^\\/\:\*\?\<\>\"\|]+(\){0,1})+$
第一组： (?:[a-zA-Z]\:\|\\)
- 检查
- 一个大写或小写字母后跟一个冒号和一个反斜杠
- 双反斜杠
第二组： ([^\\/\:\*\?\<\>\"\|]+(\){0,1})
- 第一部分：
[^\\/\:\*\?\<\>\"\|]+
- 确保没有非法字符 (\ / : * ? < > " | )
- 第二部分：
(\){0,1}
- 根据需要多次检查部分之间的反斜杠
我认为这可能是 {0, 1} 引起的问题，因为这允许回溯，但我不确定。有什么想法吗？
您当前的正则表达式可以写成 ^(?:[a-zA-Z]:\|\\)([^\\/\:*?<>"|]+\?)+$：注意在 \ 之后的 ? 量词（它等于 {0,1} 限制量词） + 量化组.
一旦像 (a+b?)+ 这样的模式出现在模式中，就很有可能发生灾难性的回溯。匹配时一切都很好，比如 c:\aaaaaaaaaaaaaaaaaaa is matched fine, but once a char that is not allowed appears causing a no-match, (try adding * at the end, c:\aaaaaaaaaaaaaaaaaaa*), the issue will appear.
为了解决这个问题，可以匹配相同文本的量化子模式不能紧接着一个。并且使用每个子模式都是强制性的可选组可以实现这一点。
在大多数情况下，您需要将这些图案部分替换为展开的 a+(ba+)*（出现 1 次或多次 a 后跟 0 次或多次 b 序列（即没有longer optional by itself) and then 1 or more occurrences of a (so, between one a and the next a must be a b). 如果你需要在末尾匹配一个可选的 \（因为 ^(a+b?)+$ 实际上可能匹配字符串末尾的 b），您需要在末尾添加一个 b?：a+(ba+)*b?.
因此，将其转化为您当前的场景：
^(?:[a-zA-Z]:\|\\)[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*$
或者如果 \ 允许在末尾：
^(?:[a-zA-Z]:\|\\)[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*\?$
| a+ ( b a+ )* b?
看看如何 fails gracefully upon a no match, or matches as expected.
正如@anubhava 所建议的，您可以通过使用 possessive 量词（或原子组代替，因为例如 .NET 正则表达式引擎不支持所有格）进一步提高性能 不允许回溯到分组模式。一旦匹配，这些模式就不会重试，因此，失败可能会来得更快：
^(?:[a-zA-Z]:\|\\)[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*+\?$
^
或原子团示例：
^(?:[a-zA-Z]:\|\\)(?>[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*)\?$
^^^ ^
请注意 : 不是特殊的正则表达式元字符，不应转义。在字符 class 中，只有 -、^、\ 和 ] 通常需要转义，其他的也没有特殊之处。
在 The Explosive Quantifier Trap 上查看有关 灾难性回溯 的更多信息。
问题
我正在使用以下正则表达式来检查有效的文件路径：
^(?:[a-zA-Z]\:\|\\)([^\\/\:\*\?\<\>\"\|]+(\){0,1})+$
使用测试字符串V:\Sample Names\Libraries\DeveloperLib\DeveloperComDlgs\res被识别为有效。我什至可以毫无问题地将无效字符添加到字符串的开头。但是，当我在字符串末尾添加无效字符时，网页因灾难性回溯而冻结。
是什么原因导致此正则表达式字符串出现这种情况？
分解正则表达式
完整字符串： ^(?:[a-zA-Z]\:\|\\)([^\\/\:\*\?\<\>\"\|]+(\){0,1})+$
第一组： (?:[a-zA-Z]\:\|\\)
- 检查
- 一个大写或小写字母后跟一个冒号和一个反斜杠
- 双反斜杠
第二组： ([^\\/\:\*\?\<\>\"\|]+(\){0,1})
- 第一部分：
[^\\/\:\*\?\<\>\"\|]+- 确保没有非法字符 (\ / : * ? < > " | )
- 第二部分：
(\){0,1}- 根据需要多次检查部分之间的反斜杠
我认为这可能是 {0, 1} 引起的问题，因为这允许回溯，但我不确定。有什么想法吗？
您当前的正则表达式可以写成 ^(?:[a-zA-Z]:\|\\)([^\\/\:*?<>"|]+\?)+$：注意在 \ 之后的 ? 量词（它等于 {0,1} 限制量词） + 量化组.
一旦像 (a+b?)+ 这样的模式出现在模式中，就很有可能发生灾难性的回溯。匹配时一切都很好，比如 c:\aaaaaaaaaaaaaaaaaaa is matched fine, but once a char that is not allowed appears causing a no-match, (try adding * at the end, c:\aaaaaaaaaaaaaaaaaaa*), the issue will appear.
为了解决这个问题，可以匹配相同文本的量化子模式不能紧接着一个。并且使用每个子模式都是强制性的可选组可以实现这一点。
在大多数情况下，您需要将这些图案部分替换为展开的 a+(ba+)*（出现 1 次或多次 a 后跟 0 次或多次 b 序列（即没有longer optional by itself) and then 1 or more occurrences of a (so, between one a and the next a must be a b). 如果你需要在末尾匹配一个可选的 \（因为 ^(a+b?)+$ 实际上可能匹配字符串末尾的 b），您需要在末尾添加一个 b?：a+(ba+)*b?.
因此，将其转化为您当前的场景：
^(?:[a-zA-Z]:\|\\)[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*$
或者如果 \ 允许在末尾：
^(?:[a-zA-Z]:\|\\)[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*\?$
| a+ ( b a+ )* b?
看看如何 fails gracefully upon a no match, or matches as expected.
正如@anubhava 所建议的，您可以通过使用 possessive 量词（或原子组代替，因为例如 .NET 正则表达式引擎不支持所有格）进一步提高性能 不允许回溯到分组模式。一旦匹配，这些模式就不会重试，因此，失败可能会来得更快：
^(?:[a-zA-Z]:\|\\)[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*+\?$
^
或原子团示例：
^(?:[a-zA-Z]:\|\\)(?>[^\\/\:*?<>"|]+(?:\[^\\/\:*?<>"|]+)*)\?$
^^^ ^
请注意 : 不是特殊的正则表达式元字符，不应转义。在字符 class 中，只有 -、^、\ 和 ] 通常需要转义，其他的也没有特殊之处。
在 The Explosive Quantifier Trap 上查看有关 灾难性回溯 的更多信息。