Regexbuddy に式を入力すると、次のメッセージが表示されます
正規表現が複雑すぎるため、一致の試行は早期に中止されました。一緒に使用する予定の正規表現エンジンは、それをまったく処理できず、クラッシュする可能性があります。この状況を回避する方法については、ヘルプ ファイルで「壊滅的なバックトラッキング」を参照してください。
壊滅的なバックトラッキングを調べると、次の説明が得られます
ランナウェイ正規表現: 壊滅的なバックトラッキング
正規表現 (x+x+)+y について考えてみましょう。恐ろしく悲鳴を上げて、この不自然な例を xx+y と書いて、ひどく入れ子になった量指定子を使わずにまったく同じに一致させるべきだと言う前に、それぞれの "x" がより複雑なものを表し、特定の文字列が両方の "x" に一致すると仮定してください。 . 実際の例については、以下の HTML ファイルのセクションを参照してください。
この正規表現を xxxxxxxxxxy に適用するとどうなるか見てみましょう。最初の x+ は、10 個の x 文字すべてに一致します。2 番目の x+ は失敗します。最初の x+ は 9 つの一致に戻り、2 番目の x+ は残りの x を取得します。グループは 1 回一致しました。グループは繰り返されますが、最初の x+ で失敗します。1回の繰り返しで十分なので、グループは一致します。y は y と一致し、全体的な一致が見つかりました。正規表現が機能することが宣言され、コードが顧客に出荷され、顧客のコンピューターが爆発します。ほとんど。
対象の文字列に y がない場合、上記の正規表現は見苦しくなります。y が失敗すると、正規表現エンジンはバックトラックします。グループには、バックトラックできる反復が 1 つあります。2 番目の x+ は 1 つの x のみに一致したため、後戻りできません。しかし、最初の x+ は 1 つの x をあきらめることができます。2 番目の x+ はすぐに xx に一致します。グループは再び 1 回反復し、次の反復で失敗し、y で失敗します。再びバックトラックすると、2 番目の x+ には 1 つのバックトラック位置があり、x に一致するように縮小されます。グループは 2 回目の反復を試みます。最初の x+ は一致しますが、2 番目は文字列の最後でスタックします。再びバックトラックすると、グループの最初の繰り返しの最初の x+ は、それ自体を 7 文字に減らします。2 番目の x+ は xxx に一致します。y に失敗すると、2 番目の x+ は xx に縮小され、次に x に縮小されます。これで、グループは 2 回目の反復に一致することができます。各 x+ に対して 1 つの x を使用します。しかし、この (7,1),(1,1) の組み合わせも失敗します。したがって、(6,4)、(6,2)(1,1)、(6,1)、(2,1)、(6,1)、(1,2)、そして Iドリフトし始めたと思います。
RegexBuddy のデバッガーで 10x 文字列に対してこの正規表現を試すと、最後の y が欠落していることを確認するのに 2558 ステップかかります。11x ストリングの場合、5118 ステップが必要です。12 の場合、10238 ステップかかります。明らかに、ここでは O(2^n) の指数関数的な複雑さがあります。21x では、デバッガーは 280 万ステップで頭を下げ、壊滅的なバックトラッキングの悪いケースを診断します。
RegexBuddy は、サークル内にあることを検出し、一致の試行を中止するという点で寛容です。他の正規表現エンジン (.NET など) は永遠に動き続けますが、他の正規表現エンジン (バージョン 5.10 より前の Perl など) はスタック オーバーフローでクラッシュします。スタック オーバーフローは、Windows では特に厄介です。アプリケーションが痕跡や説明なしに消えてしまう傾向があるためです。ユーザーが独自の正規表現を提供できる Web サービスを実行する場合は、十分に注意してください。正規表現の経験がほとんどない人は、指数関数的に複雑な正規表現を思い付く驚くべきスキルを持っています。
コードで処理する必要があると思います。Regexbuddyの作成者に連絡して、このシナリオを検出するために何が必要かを尋ねることをお勧めします。