スターとプラスによる繰り返し

1つの繰り返し演算子、つまり量指定子はすでに導入されています：疑問符です。これは、エンジンに先行するトークンを0回または1回一致させようとするように指示し、事実上オプションにします。

アスタリスクまたはスターは、エンジンに先行するトークンを0回以上一致させようとするように指示します。プラスは、エンジンに先行するトークンを1回以上一致させようとするように指示します。<[A-Za-z][A-Za-z0-9]*>は、属性のないHTMLタグに一致します。山括弧はリテラルです。最初の文字クラスは文字に一致します。2番目の文字クラスは文字または数字に一致します。スターは2番目の文字クラスを繰り返します。スターを使用したため、2番目の文字クラスが何も一致しなくても問題ありません。そのため、正規表現はのようなタグに一致します。<HTML>に一致する場合、最初の文字クラスはHに一致します。スターは2番目の文字クラスを3回繰り返させ、T, MとLにそれぞれ一致します。

また、<[A-Za-z0-9]+>を使用することもできました。これは、有効なHTMLタグではない<1>に一致するため、使用しませんでした。ただし、検索対象の文字列にこのような無効なタグが含まれていないことがわかっている場合は、この正規表現で十分な場合があります。

繰り返しの制限

トークンを繰り返すことができる回数を指定できる追加の量指定子があります。構文は{min,max}です。ここで、_min_は0または一致の最小数を示す正の整数で、_max_は一致の最大数を示す_min_以上の整数です。コンマが存在するが_max_が省略されている場合、一致の最大数は無限です。そのため、{0,1}{0,}?, {0,}{0,}**{1,}{0,}+と同じで、{1,}

と同じです。コンマと_max_の両方を省略すると、エンジンはトークンを正確に_min_回繰り返します。\b[1-9][0-9]{3}\bを使用して、1000から9999までの数値に一致させることができます。\b[1-9][0-9]{2,4}\bは、100から99999までの数値に一致します。単語境界の使用に注意してください。

貪欲性に注意！

正規表現を使用してHTMLタグに一致させたいとします。入力は有効なHTMLファイルであることがわかっているので、正規表現は無効な山括弧の使用を除外する必要はありません。山括弧の間にある場合は、HTMLタグです。

正規表現の初心者の方は、<.+><.+>This is a first testのような文字列でテストすると、驚くでしょう。正規表現はに一致し、その一致の後続行で.

に一致することを期待するかもしれません。しかし、そうではありません。正規表現はfirstに一致します。明らかに、私たちが望んでいたものではありません。理由は、プラスが_貪欲_であるためです。つまり、プラスは正規表現エンジンに先行するトークンをできるだけ多く繰り返させます。正規表現全体が失敗した場合にのみ、正規表現エンジンは_バックトラック_します。つまり、プラスに戻り、最後の反復を諦めて、正規表現の残りの部分に進みます。正規表現エンジンの内部を見て、これがどのように機能するか、そしてなぜこれが正規表現の失敗を引き起こすのかを詳細に見てみましょう。その後、2つの可能な解決策を紹介します。

プラスと同様に、スターと中括弧を使用した繰り返しは貪欲です。

正規表現エンジンの内部を見る

正規表現の最初のトークンは<です。これはリテラルです。すでにわかっているように、それが最初に一致する場所は文字列の最初の<です。次のトークンはドットで、改行以外の任意の文字に一致します。ドットはプラスによって繰り返されます。プラスは_貪欲_です。したがって、エンジンはドットをできるだけ多く繰り返します。ドットはEに一致するため、正規表現は次の文字とドットを一致させようとします。Mは一致し、ドットがもう一度繰り返されます。次の文字は>です。そろそろ問題がわかるはずです。ドットは>に一致し、エンジンはドットの繰り返しを続けます。ドットは文字列の残りのすべての文字に一致します。エンジンが文字列の終わりの後のvoidに達すると、ドットは失敗します。この時点で初めて、正規表現エンジンは次のトークン>.

に進みます。これまでのところ、<.+はfirst testに一致し、エンジンは文字列の終わりに達しました。>はここでは一致できません。エンジンは、プラスがドットを必要な回数よりも多く繰り返したことを記憶しています。（プラスはドットが1回だけ一致することを_要求_していることを忘れないでください。）失敗を認めるのではなく、エンジンは_バックトラック_します。プラスの繰り返しを1つ減らし、正規表現の残りの部分をもう一度試します。

なので、.+の一致はEM>first tesに減ります。正規表現の次のトークンはまだ>です。しかし、文字列の次の文字は最後のtです。繰り返しますが、これらは一致しないため、エンジンはさらにバックトラックします。これまでの合計一致はfirst teに減ります。しかし、>はまだ一致できません。したがって、エンジンは.+の一致はEM>first</EMの一致までバックトラックを続けます。これで、>は文字列の次の文字に一致できます。正規表現の最後のトークンが一致しました。エンジンはfirstfirst

が正常に一致したことを報告します.正規表現エンジンは一致を返すことに_熱心_であることを忘れないでください。別の一致があるかどうかを確認するために、それ以上バックトラックを続けることはありません。最初に見つけた有効な一致を報告します.貪欲さのため、これは最も左にある最長一致です.

貪欲さの代わりに怠惰

この問題の簡単な解決策は、プラスを貪欲ではなく_怠惰_にすることです.怠惰な量指定子は、「非貪欲」または「消極的」と呼ばれることもあります.正規表現のプラスの後に疑問符を付けることで、これを行うことができます.スター、中括弧、疑問符自体にも同じことができます.そのため、例は<.+?>になります.正規表現エンジンの中身をもう一度見てみましょう.

繰り返しますが、<は最初の<に一致します.次のトークンはドットで、今回は怠惰なプラスで繰り返されます.これは、正規表現エンジンにドットをできるだけ少なく繰り返すように指示します.最小値は1です.したがって、エンジンはドットをEと一致します.要件が満たされ、エンジンは>とMに進みます.これは失敗します.繰り返しますが、エンジンは_バックトラック_します.しかし今回は、バックトラッキングは怠惰なプラスにリーチを減らすのではなく拡大させます.なので、.+の一致はEMに拡張され、エンジンは再び>の一致までバックトラックを続けます。これで、>は正常に一致します.正規表現の最後のトークンが一致しました.エンジンはが正常に一致したことを報告します.それがもっと私たちが望むものです.

怠惰の代替

この場合、プラスを怠惰にするよりも良い選択肢があります。否定文字クラス<[^>]+>を使用できます.これが優れている理由は、バックトラッキングによるものです.怠惰なプラスを使用する場合、エンジンは一致させようとしているHTMLタグの各文字に対してバックトラックする必要があります.否定文字クラスを使用する場合、文字列に有効なHTMLコードが含まれている場合はバックトラッキングはまったく発生しません.バックトラッキングは正規表現エンジンを遅くします.テキストエディターで1回検索する場合、違いに気付くことはありません.しかし、スクリプトでタイトなループ内で、またはEditPad Proのカスタム構文の色分けスキームでこのような正規表現を繰り返し使用する場合、多くのCPUサイクルを節約できます.

正規表現指向エンジンのみがバックトラックします.テキスト指向エンジンはバックトラックしないため、速度ペナルティを受けません.しかし、怠惰な量指定子もサポートしていません.

\Q…\Eエスケープシーケンスの繰り返し

\Q…\Eシーケンスは一連の文字をエスケープし、それらをリテラル文字として一致します.エスケープされた文字は個々の文字として扱われます.\Eの後に量指定子を配置すると、最後の文字にのみ適用されます.たとえば、\Q*\d+*\E+を*\d+**\d+*に適用すると、マッチする部分は*\d+**になります。アスタリスクだけが繰り返されます。Java 4と5にはバグがあり、\Q…Eシーケンス全体が繰り返され、結果として対象文字列全体がマッチします。このバグはJava 6で修正されました。