欲張りな量指定子と怠惰な量指定子

量指定子は一見すると非常に単純に見えますが、実際にはトリッキーな場合があります。

/\d+/よりも複雑なものを検索する予定がある場合は、検索がどのように機能するかを十分に理解する必要があります。

例として、次のタスクを見てみましょう。

テキストがあり、すべての引用符 "..." をギュメマーク: «...» に置き換える必要があります。これは、多くの国でタイポグラフィに使用されるのが望ましいです。

たとえば、"Hello, world" は «Hello, world» になるはずです。„Witaj, świecie!” (ポーランド語) や 「你好，世界」 (中国語) など、他の引用符も存在しますが、今回のタスクでは «...» を選択しましょう。

最初に行うべきことは、引用符で囲まれた文字列を見つけることです。そうすれば、それらを置き換えることができます。

/".+"/g のような正規表現 (引用符、その後に何か、次に別の引用符) は、適切に見えるかもしれませんが、そうではありません！

試してみましょう

let regexp = /".+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch" and her "broom"

...意図したとおりに機能しないことがわかります！

2つの一致 "witch" と "broom" を見つけるのではなく、1つの一致: "witch" and her "broom" を見つけています。

これは、「貪欲さはすべての悪の根源である」と表現できます。

貪欲な検索

一致を見つけるために、正規表現エンジンは次のアルゴリズムを使用します

• 文字列内のすべての位置について
  • その位置でパターンを一致させようとします。
  • 一致がない場合は、次の位置に進みます。

これらの一般的な言葉では、正規表現が失敗する理由が明確ではないため、パターン ".+" の検索がどのように機能するかを詳しく説明しましょう。

1. 最初のパターン文字は引用符 " です。

   正規表現エンジンは、ソース文字列 a "witch" and her "broom" is one のゼロの位置でそれを見つけようとしますが、そこには a があるため、すぐに一致しません。

   次に、エンジンは進みます: ソース文字列内の次の位置に進み、そこでパターンの最初の文字を見つけようとしますが、再び失敗し、最終的に 3 番目の位置で引用符を見つけます。

2. 引用符が検出されると、エンジンはパターンの残りの部分の一致を見つけようとします。残りの対象文字列が .+" に適合するかどうかを確認しようとします。

   この場合、次のパターン文字は . (ドット) です。これは、「改行を除く任意の文字」を示しているため、次の文字列文字 'w' が適合します

3. 次に、量指定子 .+ のためにドットが繰り返されます。正規表現エンジンは、一致に文字を次々と追加します。

   ...いつまで？すべての文字がドットと一致するため、文字列の末尾に達したときにのみ停止します。

4. これで、エンジンは .+ の繰り返しを完了し、パターンの次の文字を検索しようとします。それは引用符 " です。しかし、問題があります: 文字列が終了し、もう文字がありません！

   正規表現エンジンは、.+ を取りすぎたことを理解し、バックトラックを開始します。

   言い換えれば、量指定子の一致を 1 文字短くします

   次に、.+ が文字列の末尾の 1 文字前で終了すると仮定し、その位置からパターンの残りの部分に一致するかどうかを試みます。

   そこに引用符があれば、検索は終了しますが、最後の文字は 'e' なので、一致するものはありません。

5. ...そのため、エンジンは .+ の繰り返し回数をさらに 1 文字減らします

   引用符 '"' は 'n' と一致しません。

6. エンジンはバックトラックを続けます: パターンの残りの部分 (この場合は '"') が一致するまで、'.' の繰り返し回数を減らします。

7. 一致が完了しました。

8. したがって、最初の一致は "witch" and her "broom" です。正規表現にフラグ g がある場合、検索は最初の一致が終わったところから続行されます。残りの文字列 is one には、もう引用符がないため、結果はこれ以上ありません。

これはおそらく私たちが期待したものではないかもしれませんが、これがその仕組みです。

貪欲モード (デフォルト) では、量指定された文字は可能な限り多く繰り返されます。

正規表現エンジンは、.+ にできるだけ多くの文字を一致に追加し、パターンの残りの部分が一致しない場合は、それを 1 つずつ短縮します。

今回のタスクでは、別のものが必要です。ここで、怠惰モードが役立ちます。

怠惰モード

量指定子の怠惰モードは、貪欲モードの反対です。これは、「最小回数繰り返す」ことを意味します。

量指定子の後に疑問符 '?' を置くことで有効にできます。これにより、*? または +?、あるいは '?' の場合は ?? になります。

明確にするために、通常、疑問符 ? はそれ自体が量指定子 (ゼロまたは 1) ですが、別の量指定子 (またはそれ自体) の後 に追加された場合、別の意味を持ちます。つまり、一致モードを貪欲から怠惰に切り替えます。

正規表現 /".+?"/g は意図したとおりに機能します: "witch" と "broom" が見つかります

let regexp = /".+?"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch", "broom"

変更を明確に理解するために、検索をステップごとにトレースしましょう。

1. 最初のステップは同じです: 3 番目の位置でパターンの開始 '"' を見つけます

2. 次のステップも似ています: エンジンはドット '.' の一致を見つけます

3. そして今、検索は異なって行われます。 +? の怠惰モードがあるため、エンジンはドットをもう一度一致させようとせず、停止して、パターンの残りの部分 '"' を今すぐ一致させようとします。

   そこに引用符があれば、検索は終了しますが、'i' があるため、一致するものはありません。

4. 次に、正規表現エンジンはドットの繰り返し回数を増やし、もう一度試行します

   また失敗しました。次に、繰り返し回数が再び増え...

5. ...パターンの残りの部分の一致が見つかるまで続きます

6. 次の検索は、現在の一致の末尾から開始され、もう 1 つの結果が得られます

この例では、怠惰モードが +? でどのように機能するかを確認しました。量指定子 *? と ?? も同様の方法で機能します。つまり、正規表現エンジンは、パターンの残りの部分が指定された位置で一致できない場合にのみ繰り返し回数を増やします。

怠惰は、? を使用した量指定子に対してのみ有効になります。

他の量指定子は貪欲なままです。

たとえば

alert( "123 456".match(/\d+ \d+?/) ); // 123 4

1. パターン \d+ は、できるだけ多くの数字 (貪欲モード) に一致させようとするため、123 を見つけて停止します。次の文字はスペース ' ' であるためです。

2. 次に、パターンにスペースがあり、一致します。

3. 次に、\d+? があります。量指定子は怠惰モードであるため、1 桁の数字 4 を見つけて、そこからパターンの残りの部分が一致するかどうかを確認しようとします。

   ...しかし、\d+? の後にパターンには何もありません。

   怠惰モードは、必要がない限り何も繰り返しません。パターンが終了したので、完了です。一致 123 4 が得られました。

別の方法

正規表現を使用すると、同じことを行う複数の方法があることがよくあります。

この例では、正規表現 "[^"]+" を使用して、怠惰モードを使用せずに引用符で囲まれた文字列を見つけることができます

let regexp = /"[^"]+"/g;

let str = 'a "witch" and her "broom" is one';

alert( str.match(regexp) ); // "witch", "broom"

正規表現 "[^"]+" は、引用符 '"' の後に 1 つ以上の非引用符 [^"] が続き、次に閉じ引用符が続くものを探すため、正しい結果が得られます。

正規表現エンジンが [^"]+ を探すとき、閉じ引用符に達すると繰り返しを停止し、完了です。

このロジックが怠惰な量指定子を置き換えないことに注意してください！

それはただ異なるだけです。どちらかが必要な場合もあります。

怠惰な量指定子が失敗し、このバリアントが正しく機能する例を見てみましょう。

たとえば、<a href="..." class="doc"> 形式のリンクを、任意の href で見つけたいとします。

どの正規表現を使用しますか？

最初のアイデアは、/<a href=".*" class="doc">/g かもしれません。

確認してみましょう

let str = '...<a href="link" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// Works!
alert( str.match(regexp) ); // <a href="link" class="doc">

機能しました。しかし、テキストに多くのリンクがある場合はどうなるかを見てみましょう。

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*" class="doc">/g;

// Whoops! Two links in one match!
alert( str.match(regexp) ); // <a href="link1" class="doc">... <a href="link2" class="doc">

「魔女」の例と同じ理由で、結果は間違っています。量指定子 .* が多すぎる文字を取得しました。

一致は次のようになります

<a href="....................................." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

量指定子 .*? を怠惰にすることで、パターンを変更しましょう

let str = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// Works!
alert( str.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

これで、2 つの一致があり、機能しているようです

<a href="....." class="doc">    <a href="....." class="doc">
<a href="link1" class="doc">... <a href="link2" class="doc">

...しかし、もう 1 つのテキスト入力でテストしてみましょう

let str = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let regexp = /<a href=".*?" class="doc">/g;

// Wrong match!
alert( str.match(regexp) ); // <a href="link1" class="wrong">... <p style="" class="doc">

これで失敗しました。一致にはリンクだけでなく、その後ろに多くのテキスト (<p...> を含む) が含まれています。

なぜ？

それが何が起こっているかです

1. まず、正規表現はリンクの開始 <a href=" を見つけます。
2. 次に、.*? を探します。これは1文字（遅延評価で！）を取得し、" class="doc"> に一致するかどうかを確認します（一致しません）。
3. 次に、別の文字を .*? に取り込み、これを繰り返します。そして、最終的に " class="doc"> に到達します。

しかし、問題は、それがすでにリンク <a...> の先、別のタグ <p> の中にあるということです。これでは、私たちが望むものではありません。

テキストに合わせて、マッチした部分を図示したものがこちらです

<a href="..................................." class="doc">
<a href="link1" class="wrong">... <p style="" class="doc">

したがって、<a href="...something..." class="doc"> を探すパターンが必要ですが、欲張りなバリアントと怠惰なバリアントの両方に問題があります。

正しいバリアントは、href="[^"]*" です。これは、`href` 属性の内側の文字をすべて、一番近い引用符まで取得します。まさに私たちが求めているものです。

動作例

let str1 = '...<a href="link1" class="wrong">... <p style="" class="doc">...';
let str2 = '...<a href="link1" class="doc">... <a href="link2" class="doc">...';
let regexp = /<a href="[^"]*" class="doc">/g;

// Works!
alert( str1.match(regexp) ); // null, no matches, that's correct
alert( str2.match(regexp) ); // <a href="link1" class="doc">, <a href="link2" class="doc">

まとめ

量指定子には2つの動作モードがあります

欲張り (Greedy)

デフォルトでは、正規表現エンジンは、量指定された文字を可能な限り多く繰り返そうとします。たとえば、\d+ は可能なすべての数字を消費します。これ以上消費できなくなると（数字がなくなったか、文字列の終わり）、パターンの残りの部分とのマッチングを続けます。一致するものがない場合は、繰り返しの数を減らし（バックトラック）、再度試行します。

怠惰 (Lazy)

量指定子の後に疑問符 ? を付けることで有効になります。正規表現エンジンは、量指定された文字の各繰り返し前に、パターンの残りの部分との一致を試みます。

見てきたように、怠惰モードは欲張り検索の「万能薬」ではありません。代替案は、パターン "[^"]+" のように、除外を含む「微調整された」欲張り検索です。