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 ===

最小限のバックトラッキング (少なくともマッチング時) のために作られていますが、私は今のところちょっと疲れた顔なので、改善する方法がかなり見逃されている可能性があります。

多くのバックトラッキングを回避するために使用される2つの仮定があります（他の人が言っているように、スタックオーバーフローを引き起こす可能性があります）：

  1. ===開始/終了マーカー行を除いて、行の先頭に がないこと。
  2. その C++ はこれらの正規表現機能、特に否定先読み ( ?!) の使用をサポートしています。ECMAScriptの方言であることを考えると、そうすべきです。

説明:

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

オブジェクトの開始マーカーを一致させてキャプチャします。これ[^=]は、あなたと同じように、ここで比較的少量のバックトラックを回避する 1 つの方法です[^ ]。OBJECT ID にスペースがあるかどうかわからないため、使用していません。

((?:

データのグループのキャプチャを開始します。その中には、非キャプチャ グループがあります。これは、各行を個別に照合するためです。

   (?!===)

===否定先読み -キャプチャされた行の先頭には必要ありません。

   [^\n]+\n

1 行を個別に一致させます。

)+)

開始マーカーと終了マーカーの間で少なくとも 1 行を一致させ、1 つのグループ内のすべての行をキャプチャします。

=== END \1 ===

エンドマーカーを合わせます。

比較 (RegexBuddy を使用):

元のバージョン：

  • 最初のマッチ: 1277 ステップ
  • 一致に失敗: 1 ステップ (これは、オブジェクト間の改行によるものです)
  • 2 番目の一致: 396 ステップ

オブジェクトを追加するたびに、前のオブジェクトのステップ数が増えます。たとえば、もう 1 つのオブジェクト (オブジェクト 2 のコピー、名前を 3 に変更) を追加すると、2203 ステップ、1322 ステップ、425 ステップになります。

このバージョン:

  • 初戦：67歩
  • マッチの失敗: 1 ステップ (オブジェクト間の改行によりもう一度)
  • 2 番目の一致: 72 ステップ
  • マッチに失敗: 1 ステップ
  • 3 試合目: 67 ステップ
于 2013-07-17T17:49:28.297 に答える
4

聖なる壊滅的な後戻り。犯人は(?:.|\\n)*。このような構成を目にするときはいつでも、トラブルを求めていることがわかります。

なんで？エンジンに、任意の文字 (改行を除く) または改行、できるだけ多く一致させるか、まったく一致させないように指示しているためです。順を追って説明します。

エンジンは期待どおりに始動し=== OBJECT2 ===、大きな問題もなく - 部分と一致し、改行が消費され、地獄が始まります。エンジンは まですべてを消費し=== END OBJECT1 ===、そこから適切な一致までバックトラックします。バックトラックとは基本的に、1 ステップ戻って正規表現を再度適用し、機能するかどうかを確認することを意味します。基本的に、文字列で可能なすべての順列を試します。これは、あなたの場合、数十万回の試行になります。それがおそらく、物事があなたにとって問題になっている理由です。

あなたのコードが改善されているのか、エラーがある(?:.|\\n)*のか​​はわかりませんが.*、* s * 単一行修飾子 (ドットは改行に一致) または[\S\s]*. その構造を私が推奨した 2 つのうちの 1 つに置き換えると、スタック オーバーフロー エラーが表示されなくなることを願っています。

編集：他の解決策もチェックしてください。なぜそんなに悪いのかを説明する以外に、あなたの問題を深く掘り下げて確実な解決策を提供する時間がありませんでした。

于 2013-07-17T12:00:24.160 に答える
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 に答える