[解決済み] 貪欲 vs. 渋い vs. 所有格の修飾語

質問

こんなものがありました。 チュートリアル 正規表現について、quot;greedy", "reluctant" と "possessive" の修飾子が何をするのか直感的に理解できましたが、私の理解には大きな穴があるように思われます。

具体的には、次のような例で。

Enter your regex: .*foo // Greedy qualifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfooxxxxxxfoo" starting at index 0 and ending at index 13.

Enter your regex: .*?foo // Reluctant qualifier
Enter input string to search: xfooxxxxxxfoo
I found the text "xfoo" starting at index 0 and ending at index 4.
I found the text "xxxxxxfoo" starting at index 4 and ending at index 13.

Enter your regex: .*+foo // Possessive qualifier
Enter input string to search: xfooxxxxxxfoo
No match found.

説明では、次のように言及しています。 食べる 入力文字列全体、文字が 消費 マッチャー 後方支援 foo"の右端の出現が 再掲載 など。

残念ながら、素敵なメタファーにもかかわらず、何が誰に食べられているのか、まだ理解できていません...。他のチュートリアルで（簡潔に）説明されているものをご存知でしょうか？ どのように 正規表現エンジンはどのように動作しますか？

あるいは、次の段落を多少違う表現で説明してくれる人がいれば、とてもありがたいです。

最初の例では、欲張りな量詞 .* という文字が0回以上続くものを探します。 "f" , "o" , "o" . 量詞は貪欲であるため .* の部分は、まず入力文字列全体を食べます。この時点で、式全体が成功することはない。なぜなら、最後の3文字( "f" , "o" , "o" はすでに消費されている（誰が？］ そこで、マッチャーは一文字ずつゆっくりと後退していき、一番右の "foo" が再投入され（これはどういう意味か）、その時点でマッチが成功し、検索が終了する。

しかし、2番目の例は消極的なので、まず[誰が]"nothing"を消費するところから始まります。なぜなら "foo" は文字列の先頭には現れないので、仕方なく[誰が飲み込むのか？]最初の文字( "x" での最初のマッチをトリガーします。テストハーネスは入力文字列を使い切るまでこの処理を続けます。そして、4と13の位置で別のマッチを見つけます。

3つ目の例は、量詞が所有格であるため、マッチングに失敗しています。この場合、入力文字列全体が .*+ [式の末尾にある "foo" を満たすものは何も残りません。マッチがすぐに見つからない場合、同等の貪欲な数量詞より優れています。

どのように解決するのか？

試してみる

A 欲張り 量化器は、まず可能な限りマッチングを行います。ですから .* は文字列全体にマッチします。次に、マッチャは f に続くが、残りの文字がない。そこで、quot;backtracks" を使って、欲張りな量化器を1文字少なくマッチさせます（文字列末尾の "o" はマッチしないままにしておきます）。これでもまだ f そのため、さらに1ステップ後退して、欲張りな数量化係数は再び1文字少なくマッチします（文字列の末尾の "oo" はマッチしないままです）。これは まだ にはマッチしません。 f の正規表現で、もう一段階後退します (文字列の末尾の "foo" はマッチしないままです)。ここで、マッチャは最終的に f が正規表現に含まれ o と次の o もマッチングされます。成功です!

A やむなく または "非貪欲" の量 子が最初にできるだけマッチします。そのため .* はまず何もマッチせず、文字列全体が未マッチになります。次に、マッチャは f しかし、文字列のマッチしない部分は "x" で始まっているので、これはうまくいきません。そこで、マッチャーはバックトラックして、欲のない量化子にもう1文字マッチさせます (これで "x" にマッチし、 "fooxxxxxfoo" はマッチしないままです)。次に f となり、成功します。 o と次の o も正規表現にマッチします。成功!

この例では、次に文字列のマッチしない残りの部分、"xxxxxxfoo"から同じ処理をやり直します。

A 所有格 量化詞は欲張り量化詞と同じですが、後戻りしないのが特徴です。ですから、最初は .* は文字列全体にマッチし、マッチしないものは何も残りません。そして、マッチしないものは何も残さず f を正規表現に追加しました。所有格の量詞はバックトラックしないので、マッチはそこで失敗します。