C++ - STD 正则表达式在长多行匹配期间在 MSVC 中崩溃

Question

我正在尝试使用 std::regex 从源文件中提取 /* ... */ 样式的注释。但是“regex_search”有时会在跨越多行的长匹配中崩溃(未处理的异常)。

STD 示例(无效)

这个例子对我来说崩溃了:

#include <iostream>
#include <regex>

int main()
{
    std::string in = "/*\naaa\naaaaaaaaa\naaaaaaaaa\naaaaaaaaaaaaa\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\naaaaaaaaaaaaaaaaa\naaaaaaaaa\naaaaaaaaaaaaa\naaaaaaaaa\naaaaaaaaaaaaaaaaaa\naaaaaaaaa\naaaaaaaaaaaaa\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\naaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\naaaaaaaaaaaaaaaaa\naaaaaaaaa\naaaaaaaaa\naaaaaaaaa\n*/";
    std::regex e(".*/\\*(\n|.)*?\\*/");
    std::smatch m;

    while (std::regex_search(in, m, e))
    {
        std::cout << m[0].str() << std::endl;

        in = m.suffix();
    }

    return 0;
}

我使用的是 Visual Studio 2013，所以这可能是编译器特定的问题。

编辑:作为@T.C.在评论中指出，代码在 GCC 4.9 下工作，并抛出堆栈溢出异常。这可能只是 Visual C++ 编译器的问题，也可能只是 GCC 分配了更大的堆栈。

Qt 示例(工作)

我尝试在 Qt 中实现同样的事情，没有任何问题，所以我认为我没有犯任何错误。但我非常希望不依赖任何外部库。

QRegularExpression re(".*/\\*(\n|.)*?\\*/");
QRegularExpressionMatchIterator it = re.globalMatch(QString(in.c_str()));
while (it.hasNext())
{
    QRegularExpressionMatch match = it.next();
    QString word = match.captured(0);
}

问题

这可能是 std::regex 实现中的错误吗？我有没有哪里弄错了？

Answer 1

我认为这不是编译器问题(如果您不使用 gcc < 4.9)。正则表达式崩溃是因为获得结果的步骤数太高。尝试对这种模式做同样的事情:

/\\*[\\s\\S]*?\\*/

或使用模拟 possessive quantifier 的这个:

/\\*(?=((?:[^*]+|\\*(?!/))*))\\1\\*/

(这两个模式是为了与 ECMAScript 模式一起工作而设计的，也就是说，如果我没记错的话，你的正则表达式引擎的默认模式)

关于您的原始模式:

第一个错误是以 .* 开始你的模式 (因为你使用 regex_search 方法所以不需要)。由于默认情况下量词是贪婪的，因此第一个子模式将匹配所有字符，直到每行结束。在获得匹配后，正则表达式引擎需要逐个字符回溯，直到它在字符串 中找到 /*(请注意，如果您有多个 /*同一行，只会找到最后一行)。

第二个错误是使用类似 (\\n|.)*? 的方式来描述所有字符，直到后面的内容(即 */)。

使用这种构造有几个成本:

• 您使用捕获组，因此您支付每个字符的存储成本(一个接一个)。
• 您支付了交替的费用，因为大多数时候 . 会匹配并且 \\n 没有被测试 (但是，这取决于如何你的评论看起来像，但是写 (?:.|\\n)*? 可能更高效。)
• 最重要的成本可能是您使用带有非贪婪量词的组这一事实，因为它会强制所有字符的正则表达式引擎进入组并为每个字符离开组。 如果没有惰性量词，在某些正则表达式引擎中 (?:a)+ 可能比 a+
慢 150 倍

关于你在评论中提出的问题，我会给你一个笼统的回答。

是的，某些地方限制了步数或回溯步数。如果正则表达式引擎足够聪明，它可能会在预分析期间检测到模式会在尝试做某事之前导致过多的工作，但情况并非总是如此。

要确切知道发生了什么，您可以将您的正则表达式模式放在 try/catch block 中，并检查这两个错误:

if (e.code() == std::regex_constants::error_complexity)
    std::cerr << "The complexity of an attempted match against a regular expression exceeded a pre-set level.\n";
else if (e.code() == std::regex_constants::error_stack)
    std::cerr << "There was insufficient memory to determine whether the regular expression could match the specified character sequence.\n";