貪欲vs.嫌悪vs.所有格数量詞

正規表現に関するこの優れたチュートリアルを見つけました。「貪欲」、「消極的」、「所有格」の数量詞が何をするのかを直感的に理解できますが、理解には深刻な穴があるようです。

具体的には、次の例では次のとおりです。

Enter your regex: .*foo  // greedy quantifier
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 quantifier
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 quantifier
Enter input string to search: xfooxxxxxxfoo
No match found.

説明には、入力文字列全体を食べる、文字が消費される、マッチャーがバックオフする、「foo」の右端の出現が逆流したなどが記載されています。

残念ながら、素晴らしい比喩にもかかわらず、私はまだ誰が何を食べているのかわかりません...正規表現エンジンがどのように機能するかを（簡潔に）説明する別のチュートリアルを知っていますか？

あるいは、誰かが次の段落を多少異なる言い回しで説明できる場合、それは大いにありがたいです：

最初の例では、貪欲な数量詞。*を使用して、0回以上「何でも」を検索し、その後に「f」「o」「o」の文字を続けます。数量詞は貪欲であるため、式の。*部分は最初に入力文字列全体を食べます。この時点では、最後の3文字（ "f" "o" "o"）がすでに消費されているため（誰が？）、全体的な式は成功しません。したがって、マッチャーは、「foo」の右端のオカレンスが逆流するまで、一度に1文字ずつゆっくりと（右から左に？）バックオフします（これはどういう意味ですか？）。その時点で、一致は成功し、検索は終了します。

ただし、2番目の例は気が進まないため、最初に（誰が？）「何も」消費しないことから始まります。「foo」は文字列の先頭に表示されないため、最初の文字（「x」）を飲み込む（誰が飲み込むのか）ことを余儀なくされ、0と4で最初の一致がトリガーされます。テストハーネスはプロセスを続行します入力文字列がなくなるまで。4と13で別の一致が見つかります。

3番目の例では、数量詞が所有格であるため、一致するものを見つけることができません。この場合、入力文字列全体が。* +によって消費され（どのように？）、式の最後の「foo」を満たすために何も残されません。バックオフせずにすべてのものを取得したい状況では、所有格の数量詞を使用します（バックオフとはどういう意味ですか？）; 一致がすぐに見つからない場合は、同等の貪欲な数量詞よりもパフォーマンスが高くなります。

試してみます。

貪欲できるだけ数量詞最初の試合。したがって、.*一致は文字列全体に一致します。次に、マッチャーはf以下を照合しようとしますが、文字が残っていません。したがって、それは「バックトラック」し、貪欲な数量詞を1文字少なくします（文字列の末尾の「o」は一致しません）。それでもf正規表現のとは一致しないため、もう1つのステップをバックトラックして、貪欲な数量詞を1文字少なくします（文字列の末尾の「oo」は一致しません）。それはまだ一致していないf、それは（比類のない文字列の末尾に「foo」を残して）一歩をバックトラックして、正規表現で。これで、マッチャーは最終的fに正規表現内のと一致し、oと次oも一致します。成功！

消極できるだけわずかまたは「非貪欲な」数量詞最初の試合。したがって、.*最初は何も一致せず、文字列全体が一致しません。次に、マッチャーはf以下を照合しようとしますが、文字列の一致しない部分は「x」で始まるため、機能しません。したがって、マッチャーはバックトラックし、欲張りでない数量詞をもう1文字一致させます（「x」と一致し、「fooxxxxxxfoo」は一致しません）。次に、を一致させようとしますがf、これは成功し、正規表現のとo次oも一致します。成功！

あなたの例では、同じプロセスに従って、文字列の残りの一致しない部分「xxxxxxfoo」でプロセスを最初からやり直します。

所有数量詞はただ貪欲数量詞のようなものですが、それは後戻りしません。したがって.*、文字列全体を一致させることから始め、一致しないものは何も残しません。次にf、正規表現のに一致するものは何も残っていません。所有格の数量詞はバックトラックしないため、一致はそこで失敗します。

シーンを視覚化するのは私の練習出力です-

「吐き戻し」または「バックオフ」という正確な用語はこれまで聞いたことがありません。これらに代わるフレーズは「バックトラック」ですが、「逆流」は「バックトラック前に暫定的に受け入れられていたコンテンツが再び破棄された」というフレーズと同じくらい良いフレーズのようです。

ほとんどの正規表現エンジンについて理解する重要なことは、それらがバックトラックしていることです。正規表現のコンテンツ全体を一致させようとしながら、潜在的な部分一致を暫定的に受け入れます。最初の試行で正規表現を完全に一致させることができない場合、正規表現エンジンはその一致の1つでバックトラックします。これは、マッチングしようと*、+、?、交互、または{n,m}異なっ繰り返しをし、再試行してください。（はい、このプロセスには長い時間がかかる場合があります。）

最初の例では、貪欲な数量詞。*を使用して、0回以上「何でも」を検索し、その後に「f」「o」「o」の文字を続けます。数量詞は貪欲であるため、式の。*部分は最初に入力文字列全体を食べます。この時点では、最後の3文字（ "f" "o" "o"）がすでに消費されているため（誰が？）、全体的な式は成功しません。

最後の3つの文字、f、o、およびoすでに初期によって消費された.*ルールの一部。ただし、正規表現の次の要素であるf、は、入力文字列に何も残っていません。エンジンは最初の一致でバックトラックを強制され.*、最後を除くすべての文字の一致を試みます。（3つの文字通りの用語があるため、スマートで最後の3つを除くすべてに戻る可能性がありますが、このレベルでの実装の詳細はわかりません。）

したがって、マッチャーは、「foo」の右端のオカレンスが逆流するまで（これはどういう意味ですか？）、一度に1文字ずつゆっくりと（右から左に？）後退します。

これは、を照合するときに暫定的に含めてfooいたことを意味します。その試みが失敗したため、正規表現エンジンはで1つ少ない文字を受け入れようとします。成功試合があった場合は前に、この例では、その後、エンジンはおそらく短縮しようとするだろう（あなたが指摘したように、それは貪欲な修飾子ですので、右から左から）試合をし、一致することができなかった場合入力全体の場合、私の仮定の例では、以前に一致したものを再評価する必要があるかもしれません。.*.*.*.*.*

一致が成功し、検索が終了するポイント。

ただし、2番目の例は気が進まないため、最初に（誰が？）「何も」消費しないことから始まります。「foo」だから

最初の何もがによって消費されません.?*。これにより、残りの正規表現が一致するようにするために、可能な限り最短の量が消費されます。

文字列の先頭に表示されず、強制的に飲み込まれます（誰が飲み込みますか？）

.?*正規表現全体を可能な限り最短の一致で一致させる最初の失敗をバックトラックした後、再び最初の文字を消費します。（この場合、正規表現エンジンは.*?、.*?気が進まないため、一致を左から右に拡張しています。）

最初の文字（「x」）。0と4で最初の一致をトリガーします。テストハーネスは、入力文字列がなくなるまでプロセスを続行します。4と13で別の一致が見つかります。

3番目の例では、数量詞が所有格であるため、一致するものを見つけることができません。この場合、入力文字列全体が。* +によって消費されます（どのように？）

A.*+は可能な限り多くを消費し、正規表現全体が一致を見つけられなかった場合に、新しい一致を見つけるためにバックトラックしません。所有.*+格はバックトラックを実行しないため、おそらく、ではなく、文字クラスまたは同様の制限で多くの用途が見られますaccount: [[:digit:]]*+ phone: [[:digit:]]*+。

これにより、入力が一致しない場合に潜在的な一致をバックトラックしてはならないことを正規表現エンジンに指示しているため、正規表現の一致を大幅に高速化できます。（一致するすべてのコードを手作業で作成する必要がある場合、これはputc(3)入力文字を「プッシュバック」するために使用しないのと似ています。最初の試行で作成する可能性のある単純なコードと非常に似ています。正規表現エンジンを除きます。プッシュバックの単一の文字よりもはるかに優れており、すべてをゼロに巻き戻して再試行できます。:)

しかし、潜在的なスピードアップ以上に、これにより、一致する必要があるものと正確に一致するregexを作成することもできます。簡単な例を思い付くのに苦労しています:)しかし、所有格と欲張りの数量詞を使用して正規表現を作成すると、異なる一致が得られる可能性があり、どちらかがより適切な場合があります。

式の最後の「foo」を満たすために何も残しません。バックオフせずにすべてのものを取得したい状況では、所有格の数量詞を使用します（バックオフとはどういう意味ですか？）; それはアウトパフォームします

このコンテキストでの「バックオフ」とは、「バックトラック」を意味します。つまり、一時的な部分一致を破棄して、別の部分一致を試行します。これは成功する場合と失敗する場合があります。

一致がすぐに見つからない場合の同等の貪欲な数量詞。

http://swtch.com/~rsc/regexp/regexp1.html

それがインターネット上で最良の説明であるかどうかはわかりませんが、それはかなりよく書かれていて、適切に詳細であり、私はそれに戻ってきます。あなたはそれをチェックしたいかもしれません。

より高いレベル（詳細ではない説明）が必要な場合、見ているような単純な正規表現の場合、正規表現エンジンはバックトラックによって機能します。基本的に、文字列のセクションを選択（「食べる」）し、そのセクションに対して正規表現を照合しようとします。それが一致する場合、素晴らしい。そうでない場合、エンジンは文字列のセクションの選択を変更し、可能なすべての選択が試行されるまで、そのセクションに対して正規表現を照合しようとします。

このプロセスは再帰的に使用されます。文字列を特定の正規表現と照合するために、エンジンは正規表現を断片に分割し、アルゴリズムを各断片に個別に適用します。

貪欲、消極的、所有格の数量詞の違いは、エンジンが文字列のどの部分と照合するかを選択するときに発生し、最初に機能しない場合にその選択を変更する方法です。ルールは次のとおりです。

• 貪欲な数量詞は、文字列全体（または、少なくとも、正規表現の前の部分とまだ一致していないすべての文字列）から開始し、正規表現と一致するかどうかを確認するようにエンジンに指示します。もしそうなら、素晴らしい。エンジンは残りの正規表現で続行できます。そうでない場合は、再試行しますが、チェックする文字列のセクションから1文字（最後の文字）を削除します。それが機能しない場合は、別の文字などを削除します。したがって、貪欲な数量詞は、可能な一致を最長から最短の順にチェックします。

• 気が進まない数量詞は、文字列の可能な限り短い部分から開始するようにエンジンに指示します。一致する場合、エンジンは続行できます。そうでない場合は、チェック対象の文字列のセクションに1文字を追加して試行し、一致するものが見つかるか、文字列全体が使い果たされるまで続けます。そのため、気が進まない数量詞は、一致する可能性のあるものを最短から最長の順にチェックします。

• 所有格の数量詞は、最初の試行での貪欲な数量詞のようなものです。文字列全体をチェックすることによって開始するようにエンジンに指示します。違いは、それが機能しない場合、所有格の数量詞は、その場で一致が失敗したことを報告することです。エンジンは、見ている文字列のセクションを変更せず、それ以上の試行も行いません。

これが、所有格の数量詞の一致があなたの例で失敗する理由です：は.*+一致する文字列全体に対してチェックされますが、その後エンジンは追加の文字を探し続けますfoo-しかしもちろん、あなたが'はすでに文字列の最後にあります。それが貪欲な数量詞である場合、バックトラック.*して、最後から2番目の文字まで、次に最後から3番目の文字まで、次に最後から4番目の文字までの唯一の一致を作成しようとします。そこfooの後に残され.*た文字列の前半「食べ」しています。

これは、セルとインデックスの位置を使用した私の見解です（セルとインデックスを区別するには、ここの図を参照してください）。

貪欲-貪欲な数量詞と正規表現全体に可能な限り一致させます。一致するものがない場合は、貪欲な数量詞に戻ります。

入力文字列： xfooxxxxxxfoo正規表現
：。* foo

上記の正規表現には、
（i） '。*'と
（ii） 'foo'

の2つの部分があります。以下の各手順では、2つの部分を分析します。「合格」または「不合格」への一致に関する追加のコメントは、中括弧内に説明されています。

ステップ1：
（i）。* = xfooxxxxxxfoo-PASS（ '。*'は貪欲な数量詞であり、入力文字列全体を使用します）
（ii）foo =インデックス13の後に一致する文字が残っていません-FAIL
一致に失敗しました。

ステップ2：
（i）。* = xfooxxxxxxfo-PASS（貪欲な数量詞 '。*'のバックトラッキング）
（ii）foo = o-FAIL
一致に失敗しました。

ステップ3：
（i）。* = xfooxxxxxxf-PASS（貪欲な数量詞 '。*'のバックトラック）
（ii）foo = oo-FAIL
一致に失敗しました。

ステップ4：
（i）。* = xfooxxxxxx-PASS（貪欲な数量詞 '。*'のバックトラック）
（ii）foo = foo-PASS
レポートの一致

結果：1つの一致
インデックス0で始まりインデックス13で終わるテキスト「xfooxxxxxxfoo」が見つかりました。

気が進まない-気が進まない数量詞との一致をできるだけ少なくし、正規表現全体を一致させます。一致するものがない場合は、気が進まない数量詞に文字を追加します。

入力文字列： xfooxxxxxxfoo正規表現
：。*？foo

上記の正規表現には2つの部分があります：
（i） '。*？' および
（ii） 'foo'

ステップ1：
。*？= ''（空白）
-PASS（不本意な数量詞 '。*？'との一致を可能な限り少なくします。 ''を持つインデックス0は一致します。）foo = xfo-FAIL（セル0,1,2-つまり、間のインデックス0および3）
一致に失敗しました。

ステップ2：
。*？= x-PASS（不本意な数量詞 '。*？'に文字を追加します。'x 'を持つセル0は一致します。）
foo = foo-PASS
レポートの一致

ステップ3：
。*？= ''（空白）-PASS（不本意な数量詞 '。*？'との一致を可能な限り少なくします。 ''を持つインデックス4は一致します。）
foo = xxx-FAIL（セル4,5,6-つまり、間のインデックス4および7）
一致に失敗しました。

ステップ4：
。*？= x-PASS（不本意な数量詞 '。*？'に文字を追加します。セル4）
foo = xxx-FAIL（セル5,6,7-つまり、5から8の間のインデックス）
一致に失敗しました。

ステップ5：
。*？= xx-PASS（不本意な数量詞 '。*？'に文字を追加します。セル4から5）
foo = xxx-FAIL（セル6,7,8-つまり、6と9の間のインデックス）
一致に失敗しました。

ステップ6：
。*？= xxx-PASS（不本意な数量詞 '。*？'に文字を追加します。セル4から6）
foo = xxx-FAIL（セル7,8,9-つまり、7から10の間のインデックス）
一致に失敗しました。

ステップ7：
。*？= xxxx-PASS（不本意な数量詞 '。*？'に文字を追加します。セル4から7）
foo = xxf-FAIL（セル8,9,10-つまり、8から11の間のインデックス）
一致に失敗しました。

ステップ8：
。*？= xxxxx-PASS（不本意な数量詞 '。*？'に文字を追加します。セル4から8）
foo = xfo-FAIL（セル9,10,11-つまり、9から12の間のインデックス）
一致に失敗しました。

ステップ9：
。*？= xxxxxx-PASS（不本意な数量詞 '。*？'に文字を追加します。セル4から9。）
foo = foo-PASS（セル10、11、12-つまり、10から13までのインデックス）
MATCHを報告します。

ステップ10：
。*？= ''（空白）-PASS（不本意な数量詞 '。*？'との一致を可能な限り少なくします。インデックス13は空白です。）
foo =一致する文字が残っていません-FAIL（インデックス13の後に一致するものはありません）
一致失敗しました。

結果：2つの一致
インデックス0で始まり
インデックス4で終わるテキスト「xfoo」が見つかりました。インデックス4で始まりインデックス13で終わるテキスト「xxxxxxfoo」が見つかりました。

所有格-所有格の量子化器に可能な限り一致させ、正規表現全体を一致させます。バックトラックしないでください。

入力文字列： xfooxxxxxxfoo正規表現
：。* + foo

上記の正規表現には、「。* +」と「foo」の2つの部分があります。

ステップ1：
。* + = xfooxxxxxxfoo-PASS（所有格の数量詞 '。*'に可能な限り一致します）
foo =一致する文字が残っていません-FAIL（インデックス13の後に一致するものがありません）
一致に失敗しました。

注：バックトラックは許可されていません。

結果： 0一致

欲張り：「可能な限り長い文字シーケンスに一致する」

気が進まない：「可能な限り短い文字シーケンスに一致する」

所有格:(貪欲で消極的であるのとは対照的に）正規表現全体に一致するものを見つけようとしないため、これは少し奇妙です。

ちなみに、正規表現パターンマッチャーの実装でバックトラッキングを使用することはありません。すべての実際のパターンマッチャーは非常に高速で、正規表現の複雑さにほとんど依存しません。

貪欲な数量化には、反復中に文字列の残りの未検証文字をすべて使用するパターンマッチングが含まれます。未検証の文字はアクティブなシーケンスで始まります。一致が発生しないたびに、最後の文字が隔離され、チェックが再度実行されます。

正規表現パターンの主要な条件のみがアクティブなシーケンスによって満たされる場合、検疫に対して残りの条件を検証する試みが行われます。この検証が成功すると、検疫内の一致した文字が検証され、残りの一致しない文字は未検証のままになり、次の反復でプロセスが新たに開始されるときに使用されます。

文字の流れは、アクティブなシーケンスから検疫への流れです。結果として生じる動作は、元のシーケンスのできるだけ多くが一致に含まれることです。

不本意な数量化は、文字の流れが逆であることを除いて、貪欲な認定とほとんど同じです。つまり、文字の流れは検疫から始まり、アクティブなシーケンスに流れ込みます。結果として生じる動作は、元のシーケンスが可能な限り一致に含まれないことです。

所有格の数量化には検疫がなく、固定されたアクティブなシーケンスのすべてが含まれます。