c++ - 正则表达式回溯引起的栈溢出

Question

我想使用以下正则表达式将字符串与使用 std::regex 的 C++11 匹配:

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

我想要实现的是:我想匹配除分号之外的所有字符，但是，如果用撇号括起来(这表示一个字符串)，则应该忽略分号。尝试应用正则表达式时出现堆栈溢出。我意识到问题是由 excessive backtracking 引起的.不幸的是，我不知道如何摆脱这个问题。如何重写表达式，使其不会导致大量回溯？

带有虚拟文本的最小代码示例:

#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;
}

我正在使用 Visual Studio 2012。

Answer 1

如果将正则表达式语法切换为基本 posix 而不是默认的 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 选项，堆栈溢出又回来了。

如果您使用 RegExr 上的数据测试您的正则表达式你就会明白问题所在了:

正则表达式会导致无限的潜在匹配。一旦你减少了潜在的匹配集，例如通过在 Lorem 之后放置一个 ; 就不再有堆栈溢出。

这确实非常不幸:没有标准匹配选项(例如 std::regex_constants::match_any | std::regex_constants::match_continuous | std::regex_constants::match_not_null)似乎需要注意这个常见问题(例如:没有“最大匹配”)。

尽管如此，它仍然与标准库的 MSVC 实现有关。这online GCC example使用相同的表达式运行良好。因此，boost 或 RE2 替代方案可能值得考虑。

此代码在 MSVC2013 上使用 boost 1.57，运行没有任何问题。如您所见，它使用与标准相同的代码/名称，但将 std 替换为 boost:

#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;
}