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

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 ，所以功能上表达式是可以的。

这是针对 v141 的 Visual Studio 2017 Professional。

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

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