php - 指数関数的な実行時間でのPCRE正規表現

Question

再帰的なバックトラッキングを使用した正規表現の実装では、場合によっては指数関数的な実行時間が発生する可能性があります。

私は、PCREエンジンのそのような病理学的正規表現を見つけようとしています。

Perl正規表現（たとえば、これ）に対して指数関数的であることが知られているいくつかの正規表現を試しましたが、テストでPCREを使用した指数関数的なランタイムを示したものはありませんでした。

Answer 1

あなたのテストでは、すべての正規表現が失敗すると予想されましたか？そして、彼らが失敗したとき、あなたは正確にその理由を知りましたか？正規表現エンジンが過度のバックトラックを検出したため、一致が失敗している可能性があります。それが発生するかどうかはわかりませんが、次のように成功するはずの正規表現を試してください。

(?i)lorem(?:.|\s)*pri\.

RegexBuddyを使用して、その正規表現を以下のテキストの最初の段落に適用すると、期待どおりに段落全体が強調表示されました。段落の最後のピリオドを削除すると、強調表示が消え、デバッガーは100万回の操作の後であきらめたと言いました。そこには驚きはありませんが、期間を元に戻して2番目の段落を追加したとき、それでも失敗しました。

---

Lorem ipsum tritani impedit civibus ei pri、legimus antiopam no sed、quo id evertiforensibusmaiestatis。Vim adintellegatconsequuntur。Te dicam impeditinciderintmea。Usu prompta alterum contentiones no、ut esse fabellassplendidepri。

Ne utroque nominavi moderatius qui、ius at suas velit nihil、vidit blandit facilisipriut。Ad vel offendit reprehendunt、mea ex quemipsumcomplectitur。Veri cetero feugait cu usu、dolor corpora adolescens vim、sit voluptuaplaceratsadipscing。Pro dicat dicta doloresで、最小のadmodum constituam eos ut、vix ut movetcausaetractatos。Impetus praesenteumno。