c# - 正则表达式匹配需要很长时间才能执行

Question

我编写了一个正则表达式，将文件路径解析为不同的组(DRIVE、DIR、FILE、EXTENSION)。

^((?<DRIVE>[a-zA-Z]):\\)*((?<DIR>[a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+)))\\)*(?<FILE>([a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+))\.(?<EXTENSION>[a-zA-Z0-9]{1,6})$))

我用 C# 做了一个测试。当我要测试的路径正确时。结果非常快，这正是我想要的。

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor.csproj";

=> 好的

但是当我尝试使用我知道不会匹配的路径进行测试时，如下所示:

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor?!??????";

=> 错误

当我调用这部分代码时，测试卡住了

Match match = s_fileRegex.Match(path);

当我查看我的 Process Explorer 时，我看到 QTAgent32.exe 进程卡在我处理器的 100% 上。这是什么意思？

Answer 1

您遇到的问题称为 catastrophic backtracking这是由于正则表达式可以通过多种方式匹配字符串的开头，这会由于 .NET 中的回溯正则表达式引擎而降低性能。

我认为您在正则表达式中使用 * 的频率太高了。 * 并不意味着“连接”——它意味着“0 次或更多次”。例如这里不应该有 *:

((?<DRIVE>[a-zA-Z]):\\)*

最多只能有一个驱动器规范。您应该在这里使用 ? 代替，否则如果您希望驱动器规范是强制性的，则根本没有量词。同样，您的正则表达式中似乎还有其他地方量词不正确。