8

除了我之前的问题：ECMAScript Regex for a multilined string 之外，我已经实现了以下加载过程：

void Load( const std::string& szFileName )
{
     static const std::regex regexObject( "=== ([^=]+) ===\\n((?:.|\\n)*)\\n=== END \\1 ===", std::regex_constants::ECMAScript | std::regex_constants::optimize );
     static const std::regex regexData( "<([^>]+)>:([^<]*)\\n", std::regex_constants::ECMAScript | std::regex_constants::optimize );

     std::ifstream inFile( szFileName );
     inFile.exceptions( std::ifstream::badbit );

     std::string szFileData( (std::istreambuf_iterator<char>(inFile)), (std::istreambuf_iterator<char>()) );

     inFile.close();

     std::vector<std::future<void>> vecFutures;

     for( std::sregex_iterator itObject( szFileData.cbegin(), szFileData.cend(), regexObject ), end; itObject != end; ++itObject )
     {
          if( (*itObject)[1] == "OBJECT1" )
          {
               vecFutures.emplace_back( std::async( []( std::string szDataString ) {
                    for( std::sregex_iterator itData( szDataString.cbegin(), szDataString.cend(), regexData ) { // Do Stuff }
               }, (*itObject)[2].str() ) );
          }
          else if( (*itObject)[1] == "OBJECT2" )
          {
               vecFutures.emplace_back( std::async( []( std::string szDataString ) {
                    for( std::sregex_iterator itData( szDataString.cbegin(), szDataString.cend(), regexData ) { // Do Stuff }
               }, (*itObject)[2].str() ) );
          }
     }

     for( auto& future : vecFutures )
     {
          future.get();
     }
}

但是，使用此文件加载它会导致堆栈溢出（参数：0x00000001、0x00332FE4）：

=== OBJECT2 ===
<Name>:Test Manufacturer
<Supplier>:Test Supplier
<Address>:Test Multiline
Contact
Address
<Email>:test@test.co.uk
<Telephone Number>:0123456789
=== END OBJECT2 ===
=== OBJECT1 ===
<Number>:1
<Name>:Test
<Location>:Here
<Manufacturer>:
<Model Number>:12345
<Serial Number>:54321
<Owner>:Me
<IP Address>:0.0.0.0
=== END OBJECT1 ===

我一直无法找到堆栈溢出的来源，但看起来外部std::sregex_iterator循环是负责任的。

提前致谢！

4

4 回答 4

4

这是另一个尝试：

=== ([^=]+) ===\n((?:(?!===)[^\n]+\n)+)=== END \1 ===

在您的 C++ 中，它显然会写成：

=== ([^=]+) ===\\n((?:(?!===)[^\\n]+\\n)+)=== END \\1 ===

它是为了最小的回溯（至少在匹配时），虽然我现在有点老脸先生，所以可能错过了很多改进它的方法。

它做了两个假设，用于避免大量回溯（正如其他人所说，这可能导致堆栈溢出）：

  1. ===除了开始/结束标记线之外，一条线的开头永远没有 a 。
  2. C++ 支持这些正则表达式功能 - 特别是使用负前瞻 ( ?!)。它应该，考虑到它是 ECMAScript 方言。

解释：

=== ([^=]+) ===\n

匹配并捕获对象开始标记。这[^=]是在这里避免相对少量回溯的一种方法，与您的相同 - 我们没有使用[^ ]，因为我不知道 OBJECT id 中是否可能有空格。

((?:

开始捕获数据组。在其中，一个非捕获组，因为我们将单独匹配每一行。

   (?!===)

负前瞻 - 我们不希望===在我们捕获的行的开头。

   [^\n]+\n

单独匹配一行。

)+)

匹配开始和结束标记之间的至少一条线，然后捕获单个组中的所有线。

=== END \1 ===

匹配结束标记。

比较（使用 RegexBuddy）：

原始版本：

  • 第一场比赛：1277步
  • 匹配失败：1 步（这是由于对象之间的换行所致）
  • 第二场比赛：396步

每个添加的对象都会导致前一个对象的步数增加。例如，再添加一个对象（对象 2 的副本，重命名为 3）将导致：2203 步、1322 步、425 步。

这个版本：

  • 第一场比赛：67步
  • 匹配失败：1 步（再次由于对象之间的换行）
  • 第二场比赛：72步
  • 匹配失败：1 步
  • 第三场比赛：67步
于 2013-07-17T17:49:28.297 回答
4

神圣的灾难性回溯。罪魁祸首是(?:.|\\n)*。每当您看到这样的构造时，您就知道您是在自找麻烦。

为什么？因为您告诉引擎匹配任何字符（换行符除外）或换行符，尽可能多地匹配，或者不匹配。让我带你了解一下。

引擎将按预期启动并匹配=== OBJECT2 ===-part 没有任何重大问题，将消耗一个换行符，然后地狱将开始。引擎消耗一切，一直到=== END OBJECT1 ===，并从那里回溯到合适的匹配。回溯基本上意味着返回一步并再次应用正则表达式以查看它是否有效。基本上用你的字符串尝试所有可能的排列。在您的情况下，这将导致数十万次尝试。这可能就是为什么事情对你来说是个问题。

我不知道您的代码是否更好或其中是否有任何错误，但(?:.|\\n)*与.*使用 * s *ingle 行修饰符（点匹配换行符）或[\S\s]*. 如果您用我推荐的两个结构之一替换该结构，您希望不再看到堆栈溢出错误。

编辑：也查看其他解决方案，除了解释为什么它如此糟糕之外，我真的没有时间深入研究并为您的问题提供可靠的解决方案。

于 2013-07-17T12:00:24.160 回答
1

Your expressions appear to be causeing a lot of backtracking. I would change your expressions to:

First: ^===\s+(.*?)\s+===[\r\n]+^(.*?)[\r\n]+^===\s+END\s+\1\s+===

Second: ^<([^>]+)>:([^<]*)

Both of these expressions work with the options: Multiline, and DotMatchesAll options. By including the start of line anchor ^ it limits the backtracking to at most one line or one group.

于 2013-07-08T02:49:30.920 回答
0

尝试使用此模式：

static const std::regex regexObject( "=== (\\S+) ===\\n((?:[^\\n]+|\\n(?!=== END \\1 ===))*)\\n=== END \\1 ===", std::regex_constants::ECMAScript | std::regex_constants::optimize );
于 2013-07-07T21:44:29.910 回答