正则表达式中回溯引起的堆栈溢出

Question

([^;]|'[^']*')*

#include <regex>
#include <string>
int main()
{
    std::string str = "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Sed ut suscipit enim. Praesent varius purus ac sem vulputate pulvinar. Mauris scelerisque arcu tortor, at bibendum dui rhoncus ut. Nunc dictum malesuada condimentum. Mauris ornare nunc eget efficitur tempor. Morbi ex nibh, consectetur vitae bibendum id, bibendum varius purus. Proin finibus quam vel ornare molestie. Mauris condimentum nisi efficitur, fringilla massa ut, commodo diam. Mauris lobortis laoreet magna sed commodo. Donec faucibus lectus placerat ex pulvinar interdum.";
    std::regex rgx("([^;]|'[^']*')*");
    std::regex_match(std::begin(str), std::end(str), rgx); // Stack overflow!
    return 0;
}

Answer 1

如果您将regex语法切换到基本的posix而不是deafult ECMAscript，它将不再溢出：

std::regex rgx("([^;]|'[^']*')*", std::regex_constants::basic);

我用MSVC2013进行了测试，它工作了。不幸的是，它也不符合您的期望，正如这个小变体所展示的：

...
std::smatch cm;
std::regex_search(str, cm, rgx, std::regex_constants::match_any | std::regex_constants::match_continuous | std::regex_constants::match_not_null); // No overflow!
for (int i = 0; i < cm.size(); i++)
    std::cout << "Found:" << cm[i];  // but no result is printed out. 

如果选择std::regex_constants::extended选项，堆栈溢出会再次出现。

#include <iostream>
#include <boost/regex.hpp>  // instead of <regex>
#include <string>
                            // use the boost alternative to std
using namespace boost::regex_constants;  
using boost::regex; using boost::smatch; using boost::regex_search;

int main()
{
    std::string str = "your very long string..." ;
    regex rgx("([^;]|'[^']*')*", extended | nosubs);
    smatch cm;
    //regex_match(str, cm, rgx, regex_constants:: match_continuous | match_not_null); // Stack overflow!
    regex_search(str, cm, rgx, match_continuous | match_not_null); 
    for (int i = 0; i < cm.size(); i++)
        std::cout << "Found:" << cm[i];
    return 0;
}