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

我写了一个正则表达式，将文件路径解析为不同的组（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";

=> OK

但是，当我尝试，我知道这将不匹配的路径来测试，这样的：

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

=> BUG

测试当我称这部分代码时冻结

Match match = s_fileRegex.Match(path);

当我查看我的Process Explorer时，发现处理器的100％挂起了进程QTAgent32.exe。这是什么意思？

来源

2010-08-04 RedPaladin

您在验证之前是否考虑过[解析路径]（http://stackoverflow.com/questions/3386258/parsing-a-given-path-in-c）？ – kennytm 2010-08-04 07:44:08

为什么不在Path类中使用有用的方法？没有必要使用正则表达式来提取这些信息。 – Jens 2010-08-04 07:46:28

RegEx真的是走错路。我仍然想知道为什么这RegEx杀死regexr.com：> – atamanroman 2010-08-04 07:48:02

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

我觉得你在正则表达式中使用的太频繁了*。 *并不意味着“连接” - 它表示“0次或更多次”。例如不应该有这里*：

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

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

来源

2010-08-04 07:54:14

好的答案，tyvm :)（+1）也许你可以把这个链接在你的答案，这很好解释发生这种情况： http：// www.regular-expressions.info/catastrophic.html – atamanroman 2010-08-04 07:56:57

@fielding：当然。完成！ – 2010-08-04 08:00:05

为什么不只是使用System.IO.Path函数？

驱动器：http://msdn.microsoft.com/en-us/library/system.io.path.getpathroot.aspx
目录：http://msdn.microsoft.com/en-us/library/system.io.path.getdirectoryname.aspx负什么是得到了驱动
文件名：http://msdn.microsoft.com/en-us/library/system.io.path.getfilenamewithoutextension.aspx
扩展：http://msdn.microsoft.com/en-us/library/system.io.path.getextension.aspx

来源

2010-08-04 07:45:51 Amber

我只是使用FileInfo和Path类来获取信息。

如果你选择使用正则表达式，然后注意，正则表达式不匹配所有合法的文件名：有一大堆合法的文件名令牌从你的正则表达式中丢失。

来源

2010-08-04 07:53:53

马克拜尔是正确的，该问题的原因是catastrophic backtracking，但它是导致问题的最后一部分，而不是与驱动器号相匹配的位。

例如，在

(?<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}) 
    $) 
)

你可以看到，

([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+) 
| 
([a-zA-Z0-9_]+)

可以用多种不同的方式，将与文件名长度成倍增加匹配相同的字符串。

当正则表达式的扩展部分无法匹配时，正则表达式引擎会为文件名部分回溯并尝试一个不同的排列，希望这可以使扩展部分匹配 - 这当然不会发生，但正则表达式引擎无法弄清楚。当被要求在你提供的路径上测试正则表达式时，RegexBuddy在1.000.000次迭代后中止匹配尝试。 C＃正则表达式引擎将持续运行，直到它耗尽所有排列，在此期间将CPU固定在100％。

为了解决这个问题，通常需要避免重复元素的重复，以避免匹配相同事物的变化，并且可能包含atomic groups中的匹配部分，如果后面的正则表达式不会被回溯到失败。

就你而言，最好使用正确的工具来完成这个工作，而这些工具就是.NET的路径操作函数。

来源

2010-08-04 08:07:56

非常感谢您的回复。您有权利，我将使用.NET框架上提供的功能！ – RedPaladin 2010-08-04 08:16:26

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

回答

相关问题