5

私は正規表現を持っています：

(<select([^>]*>))(.*?)(</select\s*>)

レイジーリピート量指定子を使用するため、長い文字列（500を超えるオプションがある）の場合、100,000回を超えてバックトラックし、失敗します。遅延反復数量詞を使用しない、より良い正規表現を見つけるのを手伝ってください

4

2 に答える 2

2 
<select[^>]*>[^<]*(?:<(?!/select>)[^<]*)*</select>

...または人間が読める形式：

<select[^>]*>    # start tag
[^<]*            # anything except opening bracket
(?:              # if you find an open bracket
  <(?!/select>)  #   match it if it's not part of end tag
  [^<]*          #   consume any more non-brackets
)*               # repeat as needed
</select>        # end tag

これは、Friedlが彼の著書「 MasteringRegularExpressions」で開発した「展開ループ」手法の例です。気が進まない数量詞に基づくパターンを使用して、RegexBuddyで簡単なテストを行いました。

(?s)<select[^>]*>.*?</select>

...そして一致するものを見つけるのに約6,000ステップかかりました。展開されたループパターンは500ステップしかかかりませんでした。また、終了タグ（）から閉じ括弧を削除し</selectて一致を不可能にした場合、失敗を報告するのに必要な手順は800ステップのみでした。

正規表現フレーバーが所有格の数量詞をサポートしている場合は、それらも使用してください。

<select[^>]*+>[^<]*+(?:<(?!/select>)[^<]*+)*+</select>

一致を達成するためにほぼ同じ数のステップが必要ですが、プロセスで使用するメモリが大幅に少なくなります。そして、一致する可能性がない場合、それはさらに迅速に失敗します。私のテストでは、一致するものを見つけるのにかかったのと同じ数の約500ステップを要しました。

于 2010-11-02T15:03:51.423 に答える
1

残念ながら、これは機能しません。正しい例については、AlanMooreの回答を参照してください。

(<select([^>]*>))(.*+)(</select\s*>)

perl regexpのマンページから：

デフォルトでは、定量化されたサブパターンがパターン全体の残りの部分を一致させることができない場合、Perlはバックトラックします。ただし、この動作は望ましくない場合があります。したがって、Perlは「所有格」の数量詞形式も提供します。

       *+     Match 0 or more times and give nothing back
       ++     Match 1 or more times and give nothing back
       ?+     Match 0 or 1 time and give nothing back
       {n}+   Match exactly n times and give nothing back (redundant)
       {n,}+  Match at least n times and give nothing back
       {n,m}+ Match at least n but not more than m times and give nothing back

例えば、

      'aaaa' =~ /a++a/

「a++」は文字列内のすべての「a」を飲み込み、パターンの残りの部分には何も残さないため、一致することはありません。この機能は、バックトラックしてはいけない場所についてのPerlのヒントを与えるのに非常に役立ちます。たとえば、一般的な「二重引用符で囲まれた文字列に一致する」問題は、次のように記述すると最も効率的に実行できます。

      /"(?:[^"\\]++|\\.)*+"/
于 2010-11-02T13:18:53.080 に答える