c++ - 为什么VC++中的程序会出现这个正则表达式 "freeze"？

Question

我有以下代码，最初使用 C++11 的正则表达式库 ( #include <regex> ) 进行编程，但现在使用 Boost 尝试进行故障排除:

boost::regex reg(R"(.*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z]*[0-9]+[a-z0-9]*)).*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z]+)).*?(\d+).*?((?:[a-z][a-z]+)))", boost::regex::icase);
boost::cmatch matches;

if (boost::regex_match(request, reg) && matches.size() > 1)
{
    printf("Match found");
}
else
{
    printf("No match.");
}

执行时，这段代码似乎“卡住”在 boost::regex_match(request, reg) 上，好像需要很长时间来处理。我等了五分钟才处理(以防这是处理问题)，但程序状态是相同的。

我tested the STL's regex library version of the above code online on cpp.sh and onlinegdb ，并且它在那里完美地工作。然后我将此代码复制到 VC++ 项目中，代码再次卡住:

#include <iostream>
#include <string>
#include <regex>

int main()
{
    std::string request = "\\login\\\\challenge\\jRJkdflp3gvTzrwiQ3tyKSqnyppmaZog\\uniquenick\\Lament\\partnerid\\0\\response\\4767846ef255a88da9b10f7c923a1e6e\\port\\-14798\\productid\\11489\\gamename\\crysiswars\\namespaceid\\56\\sdkrevision\\3\\id\\1\\final\\";
    std::regex reg(R"(.*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z]*[0-9]+[a-z0-9]*)).*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z]+)).*?(\d+).*?((?:[a-z][a-z]+)))", std::regex::icase);
    std::smatch matches;

    if (std::regex_search(request, matches, reg) && matches.size() > 1)
    {
        printf("Match found");
    }
    else
    {
        printf("No match.");
    }
}

相关字符串如下:

\login\challenge\jRJwdflp3gvTrrwiQ3tyKSqnyppmaZog\uniquenick\User\partnerid\0\response\4767846ef255a83da9b10f7f923a1e6e\port-14798\productid\11489\gamename\crysiswars\namespaceid\56\sdkrevision\3\id\1\final\

我在另一台计算机(全新项目)上安装的 Visual Studio 2017 上测试了相同的代码，并得到了完全相同的结果...这似乎表明编译器正在执行的操作导致代码卡住/执行长时间处理。我目前无法在本地另一个编译器上进行测试。

正则表达式字符串checks out on regex101 ，所以在功能上这个表达式是可以的。

这是针对 Visual Studio 2017 Professional 的 v141。

为什么会发生这种情况？我该如何解决？

Answer 1

你的问题是回溯问题之一。
在boost示例中，您使用regex_match强制匹配
整个字符串。
如果使用 regex_search 并添加 ^..$，您将获得相同的结果。

但是，您的字符串永远无法匹配，因为您强制它结束
在字母上，但字符串实际上以反斜杠结尾。
这会强制引擎重试所有这些 .*? 位置。

解决方法是在正则表达式的末尾添加一个最终的.*?，这将让
正则表达式完成了匹配整个字符串的任务。

其他事情可能会有所帮助，您可以稍微清理一下正则表达式和/或添加一些
原子组和/或添加一些斜杠来代替那些 .*?

无论如何，使用这个:

^.*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z]+)).*?((?:[a-z][ a-z]*[0-9]+[a-z0-9]*)).*?((?:[a-z][a-z]+)).*?((?:[a-z][a-z0- 9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]* )).*?((?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+). *?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z0-9_]*)).*?( (?:[a-z][a-z0-9_]*)).*?((?:[a-z][a-z0-9_]*)).*?(\d+).*?((?: [a-z][a-z0-9_]*)).*?(\d+).*?((?:[a-z][a-z]+)).*?(\d+).*?((?: [a-z][a-z]+)).*?$

输出

 **  Grp 0 -  ( pos 0 : len 207 ) 
\login\challenge\jRJwdflp3gvTrrwiQ3tyKSqnyppmaZog\uniquenick\User\partnerid\0\response\4767846ef255a83da9b10f7f923a1e6e\port-14798\productid\11489\gamename\crysiswars\namespaceid\56\sdkrevision\3\id\1\final\  
 **  Grp 1 -  ( pos 1 : len 5 ) 
login  
 **  Grp 2 -  ( pos 7 : len 9 ) 
challenge  
 **  Grp 3 -  ( pos 17 : len 32 ) 
jRJwdflp3gvTrrwiQ3tyKSqnyppmaZog  
 **  Grp 4 -  ( pos 50 : len 10 ) 
uniquenick  
 **  Grp 5 -  ( pos 61 : len 4 ) 
User  
 **  Grp 6 -  ( pos 66 : len 9 ) 
partnerid  
 **  Grp 7 -  ( pos 76 : len 1 ) 
0  
 **  Grp 8 -  ( pos 78 : len 8 ) 
response  
 **  Grp 9 -  ( pos 94 : len 25 ) 
ef255a83da9b10f7f923a1e6e  
 **  Grp 10 -  ( pos 120 : len 4 ) 
port  
 **  Grp 11 -  ( pos 125 : len 5 ) 
14798  
 **  Grp 12 -  ( pos 131 : len 9 ) 
productid  
 **  Grp 13 -  ( pos 141 : len 5 ) 
11489  
 **  Grp 14 -  ( pos 147 : len 8 ) 
gamename  
 **  Grp 15 -  ( pos 156 : len 10 ) 
crysiswars  
 **  Grp 16 -  ( pos 167 : len 11 ) 
namespaceid  
 **  Grp 17 -  ( pos 179 : len 2 ) 
56  
 **  Grp 18 -  ( pos 182 : len 11 ) 
sdkrevision  
 **  Grp 19 -  ( pos 194 : len 1 ) 
3  
 **  Grp 20 -  ( pos 196 : len 2 ) 
id  
 **  Grp 21 -  ( pos 199 : len 1 ) 
1  
 **  Grp 22 -  ( pos 201 : len 5 ) 
final