この正規表現がJava正規表現エンジンを強制終了するのはなぜですか?

15
Martin08 2008-11-14 13:49.

私はこの素朴な正規表現 "<([\ s] | [^ <])+?>"を持っています(引用符を除く)。とても簡単に思えますが、以下のHTMLテキストに対して機能する場合は実際に悪です。Java正規表現エンジンを無限ループに送ります。

別の正規表現( "<。+?>")があります。これは多少同じことをしますが、何も殺しません。なぜこれが起こるのか知っていますか?

<script language="JavaScript" type="text/javascript">
        var numDivs, layerName;
        layerName = "lnavLayer";
        catLinkName = "category";
        numDivs = 2;
        function toggleLayer(layerID){
            if (!(navigator.appName == "Netscape" && navigator.appVersion.substr(0, 1) < 5)){
                thisLayer = document.getElementById(layerName + layerID);
                categoryLink = document.getElementById(catLinkName + layerID);
                closeThem();
                if (thisLayer.className == 'subnavDefault'){
                    thisLayer.className = 'subnavToggled';
                    categoryLink.className = 'leftnavLinkSelectedSection';
                }
            }
        }
        function closeThem(){
            for(x = 0; x < numDivs; x++){
                theLayer = document.getElementById(layerName + (x
+ 1));
                thecategoryLink = document.getElementById(catLinkName + (x + 1));
                theLayer.className = 'subnavDefault';
                thecategoryLink.className = 'leftnavLink';
            }
        } var flag = 0; var lastClicked = 0
    //-->
    </script>

それも(のようなオンラインのJava正規表現ツールを使用してループし続けるwww.fileformat.info/tool/regex.htm)などのユーティリティRegexBuddy。

3 answers

51
Jan Goyvaerts 2008-11-15 00:04.

Java正規表現エンジンがクラッシュする理由は、正規表現のこの部分がスタックオーバーフローを引き起こすためです(実際に!):

[\s]|[^<]

ここで何が起こるかというと、\ sで一致するすべての文字は[^ <]でも一致する可能性があります。つまり、各空白文字を一致させる方法は2つあります。2つの文字クラスをAとBで表すと、次のようになります。

A|B

次に、3つのスペースの文字列を、AAA、AAB、ABA、ABB、BAA、BAB、BBA、またはBBBとして照合できます。言い換えると、正規表現のこの部分の複雑さは2 ^ Nです。これにより、私が壊滅的なバックトラックと呼んでいるものに対する保護手段がない正規表現エンジンがすべて強制終了されます。

正規表現で代替(垂直バー)を使用する場合は、代替が相互に排他的であることを常に確認してください。つまり、選択肢の多くても1つは、テキストの任意のビットに一致することが許可されます。

2
localshred 2008-11-14 14:08.

([\s]|[^<])平易な用語での正規表現とは、空白であるか文字ではない単一の文字を意味します。<空白文字は文字ではないため、冗長<です。あなたが本当に意味しているのは次のように私には思えます:

`"<([^<])+?>"`

これで無限ループが解決するかどうかはわかりませんが、指摘したいと思います。

2
Alan Moore 2008-11-15 11:17.

別の問題(Janが言ったことに加えて)は、括弧内で一度に1文字を一致させることです。これは、この単純化された例に相当します。

(.)+

正規表現のこの部分が実行されるたびに、正規表現エンジンは、バックトラックする必要がある場合に備えて、親の内部の部分式によって一致したものの開始位置と終了位置を保存する必要があります。これは、それが非キャプチャグループであったとしても当てはまります。

(?:.)+

...しかし、それはキャプチャグループであるため、さらに多くの情報を保存する必要があります。一度に1人のキャラクターのためにそれらすべてを通過することは本当に高価になります。括弧で囲まれたグループ内の単一の文字をグループ上の*または+数量詞と一致させることはほとんど正しくありません。また、キャプチャグループは、何かをキャプチャする必要がある場合にのみ使用する必要があります。それ以外の場合は、キャプチャしない種類を使用します。

Related questions

MORE COOL STUFF

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire は、彼女が息子の Shelby Blackstock と共有する「楽しい」クリスマスの伝統を明らかにしました:「私たちはたくさん笑います」

Reba McEntire が息子の Shelby Blackstock と共有しているクリスマスの伝統について学びましょう。

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルは、自然な髪のスタイリングをめぐってマライア・キャリーと結ばれました

メーガン・マークルとマライア・キャリーが自然な髪の上でどのように結合したかについて、メーガンの「アーキタイプ」ポッドキャストのエピソードで学びましょう.

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子は家族との関係を修復できるという「希望を持っている」:「彼は父親と兄弟を愛している」

ハリー王子が家族、特にチャールズ王とウィリアム王子との関係について望んでいると主張したある情報源を発見してください。

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドは、パニックに陥った休暇の瞬間に、彼女がジャッド家の家長であることを認識しました

ワイノナ・ジャッドが、母親のナオミ・ジャッドが亡くなってから初めての感謝祭のお祝いを主催しているときに、彼女が今では家長であることをどのように認識したかを学びましょう.

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

誰かがこのナンバープレートを取得するために490万ドルを費やした

誰かがこのナンバープレートを取得するために490万ドルを費やした

著者による画像。(グラフィック:パガニ、エミレーツオークション)少数のナンバープレートは、UAEの主要なステータスシンボルです。

ドナルド・トランプは、攻撃用武器ではなく、シリア人に対する禁止案でオーランド銃乱射事件に対応します

ドナルド・トランプは、攻撃用武器ではなく、シリア人に対する禁止案でオーランド銃乱射事件に対応します

ドナルド・トランプは、「過激なイスラムテロに正直である」ことをすぐに祝福した後、トゥデイのショーに呼びかけ、日曜日の早朝に50人が死亡したような大量射殺を防ぐために何をすべきかについて話し合った。オーランドのパルスナイトクラブ。トランプは、情報収集の改善の必要性を強調しました(「何らかの理由で、彼らはこれらの人々を報告しておらず、間違っていることがたくさん起こっていることを知っています」と彼は言い、「彼ら」が誰であるかを明確にしませんでした)。

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

それにふたを置きます。実際、すべてに蓋をしてください。14ドルで12個のシリコンストレッチキッチン蓋を手に入れよう. [エクスクルーシブ]

Tomorrow's Kitchen シリコンストレッチ蓋 12個パック | $14 | アマゾン | プロモーション コード 20OFFKINJALids は基本的にキッチンの靴下です。常に迷子になり、二度と閉じられない孤立したコンテナーが残ります。しかし、蓋が伸びて、残った容器、鍋、フライパン、さらには大きなスライスされた果物のすべてに適合するとしたらどうでしょうか? その非常に特殊な蓋を失うことを二度と心配する必要はありません。

あなたの最高のワシントン DC ハックを教えてください

あなたの最高のワシントン DC ハックを教えてください

このコラムでは、ロサンゼルスやラスベガスなど、いくつかの産業都市をハッキングしました。今こそ、軍産複合都市の時代です。

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

米国のフィギュア スケートは、チーム イベントでの最終決定の欠如に「苛立ち」、公正な裁定を求める

ロシアのフィギュアスケーター、カミラ・バリエバが関与したドーピング事件が整理されているため、チームは2022年北京冬季オリンピックで獲得したメダルを待っています。

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

Amazonの買い物客は、わずか10ドルのシルクの枕カバーのおかげで、「甘やかされた赤ちゃんのように」眠れると言っています

何千人ものAmazonの買い物客がMulberry Silk Pillowcaseを推奨しており、現在販売中. シルクの枕カバーにはいくつかの色があり、髪を柔らかく肌を透明に保ちます。Amazonで最大46%オフになっている間にシルクの枕カバーを購入してください

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

パデュー大学の教授が覚醒剤を扱った疑いで逮捕され、女性に性的好意を抱かせる

ラファイエット警察署は、「不審な男性が女性に近づいた」という複数の苦情を受けて、12 月にパデュー大学の教授の捜査を開始しました。

コンセプト ドリフト: AI にとって世界の変化は速すぎる

コンセプト ドリフト: AI にとって世界の変化は速すぎる

私たちの周りの世界と同じように、言語は常に変化しています。以前の時代では、言語の変化は数年または数十年にわたって発生していましたが、現在では数日または数時間で変化する可能性があります。

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

犯罪擁護派のオークランドが暴力犯罪者のロミオ・ロレンゾ・パーハムを釈放

SF攻撃で91歳のアジア人女性が殴られ、コンクリートに叩きつけられた

認知症を患っている 91 歳のアジア人女性が最近、47 番街のアウター サンセット地区でロメオ ロレンゾ パーハムに襲われました。伝えられるところによると、被害者はサンフランシスコの通りを歩いていたところ、容疑者に近づき、攻撃を受け、暴行を受けました。

ℝ

“And a river went out of Eden to water the garden, and from thence it was parted and became into four heads” Genesis 2:10. ? The heart is located in the middle of the thoracic cavity, pointing eastward.

メリック・ガーランドはアメリカに失敗しましたか?

バイデン大統領の任期の半分以上です。メリック・ガーランドは何を待っていますか?

メリック・ガーランドはアメリカに失敗しましたか?

人々にチャンスを与えることは、人生で少し遅すぎると私は信じています。寛大に。

Language