Gierige vs. Zögerliche vs. Besitzergreifende Qualifikatoren

Question

Ich fand dies Lehrgang über reguläre Ausdrücke, und obwohl ich intuitiv verstehe, was die Qualifikatoren "gierig", "zurückhaltend" und "besitzergreifend" bewirken, scheint es eine ernsthafte Lücke in meinem Verständnis zu geben.

Konkret im folgenden Beispiel:

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.

In der Erklärung heißt es Essen die gesamte eingegebene Zeichenkette, Buchstaben wurden verbraucht , Matcher zurückdrehend wurde das äußerste rechte Vorkommen von "foo" Erbrochenes , usw.

Leider verstehe ich trotz der schönen Metaphern immer noch nicht, was von wem gegessen wird... Kennen Sie eine andere Anleitung, die (kurz und bündig) erklärt wie Reguläre Ausdrücke funktionieren?

Wenn jemand den folgenden Absatz in einer etwas anderen Formulierung erklären kann, wäre das sehr hilfreich:

Das erste Beispiel verwendet den gierigen Quantifizierer .* um "irgendetwas" zu finden, null oder mehr Mal, gefolgt von den Buchstaben "f" , "o" , "o" . Da der Quantifizierer gierig ist, ist die .* Teil des Ausdrucks frisst zunächst die gesamte Eingabezeichenfolge. An diesem Punkt kann der Gesamtausdruck nicht erfolgreich sein, weil die letzten drei Buchstaben ( "f" , "o" , "o" ) sind bereits verbraucht worden [von wem?]. Also zieht sich der Matcher langsam [von rechts nach links?] einen Buchstaben nach dem anderen zurück, bis das äußerste rechte Vorkommen von "foo" erbrochen wurde [was bedeutet das?], woraufhin die Suche erfolgreich ist und die Suche endet.

Das zweite Beispiel ist jedoch widerwillig und beginnt damit, dass zunächst [von wem?] "nichts" konsumiert wird. Denn "foo" nicht am Anfang der Zeichenkette steht, ist es gezwungen, den ersten Buchstaben zu verschlucken [wer verschluckt? "x" ), was die erste Übereinstimmung bei 0 und 4 auslöst. Unser Test-Kabelbaum setzt den Prozess fort, bis die Eingabezeichenkette erschöpft ist. Es findet eine weitere Übereinstimmung bei 4 und 13.

Im dritten Beispiel wird keine Übereinstimmung gefunden, weil der Quantor ein Possessivum ist. In diesem Fall wird die gesamte Eingabezeichenkette von .*+ [wie?], so dass nichts übrig bleibt, um das "foo" am Ende des Ausdrucks zu erfüllen. Verwenden Sie einen Possessiv-Quantifizierer für Situationen, in denen Sie alles von etwas erfassen wollen, ohne jemals einen Rückzieher zu machen [was bedeutet Rückzieher?]; er wird den entsprechenden Gier-Quantifizierer in Fällen, in denen die Übereinstimmung nicht sofort gefunden wird, übertreffen.

Answer 1

Ich werde es ausprobieren.

A gierig Quantifizierer zuerst so viele Übereinstimmungen wie möglich. So wird die .* passt auf die gesamte Zeichenfolge. Dann versucht der Matcher, die f folgen, aber es sind keine Zeichen mehr vorhanden. Also wird "zurückgegangen", so dass der gierige Quantifizierer mit einem Zeichen weniger übereinstimmt (das "o" am Ende der Zeichenkette bleibt unberücksichtigt). Das stimmt immer noch nicht mit der f in der Regex, so dass sie einen weiteren Schritt zurückgeht und den gierigen Quantifizierer wieder auf ein Zeichen weniger abstimmen lässt (wobei das "oo" am Ende der Zeichenkette unabgestimmt bleibt). Das immer noch stimmt nicht mit der f in der Regex, so dass sie einen weiteren Schritt zurückgeht (und das "foo" am Ende der Zeichenkette unangepasst lässt). Jetzt findet der Matcher endlich die f in der Regex, und die o und die nächste o sind ebenfalls aufeinander abgestimmt. Erfolg!

A widerwillig oder "nicht gierigen" Quantifizierer zunächst so wenig wie möglich entspricht. Daher ist der .* findet zunächst nichts und lässt die gesamte Zeichenkette unbearbeitet. Dann versucht der Matcher, die f folgt, aber der nicht übereinstimmende Teil der Zeichenkette beginnt mit "x", so dass dies nicht funktioniert. Also geht der Matcher zurück und macht den Non-Greedy-Quantifizierer mit einem weiteren Zeichen gleich (jetzt passt er auf das "x" und lässt "fooxxxxxxfoo" unangepasst). Dann versucht er, die Übereinstimmung mit dem f die erfolgreich ist, und die o und die nächste o auch in der Regex-Übereinstimmung. Erfolg!

In Ihrem Beispiel beginnt der Prozess dann mit dem verbleibenden nicht übereinstimmenden Teil der Zeichenkette, "xxxxxxfoo", und folgt demselben Prozess.

A besitzergreifend Quantifizierer ist genau wie der gierige Quantifizierer, aber er geht nicht zurück. Er beginnt also mit .* die gesamte Zeichenkette ab, so dass nichts unabgeglichen bleibt. Dann gibt es nichts mehr, was mit der f in der Regex. Da der Possessivquantor nicht zurückverfolgt werden kann, schlägt die Übereinstimmung dort fehl.

Answer 2

Es ist nur meine Übungsausgabe, um die Szene zu visualisieren.

Answer 3

Ich habe die genauen Begriffe "Wiederkäuen" oder "Rückzieher" noch nie gehört; der Ausdruck, der sie ersetzen würde, ist "Backtracking", aber "Wiederkäuen" scheint ein ebenso guter Ausdruck zu sein wie jeder andere für "der Inhalt, der vor dem Backtracking vorläufig akzeptiert wurde, wurde wieder verworfen".

Das Wichtigste, was man über die meisten Regex-Engines wissen muss, ist, dass sie Rückverfolgung Sie werden vorläufig eine potenzielle Teilübereinstimmung akzeptieren, während versucht wird, den gesamten Inhalt der Regex abzugleichen. Wenn die Regex beim ersten Versuch nicht vollständig übereinstimmt, dann wird die Regex-Engine zurückverfolgen bei einem seiner Treffer. Es wird versucht, eine Übereinstimmung * , + , ? Alternation, oder {n,m} Wiederholung anders, und versuchen Sie es erneut. (Und ja, dieser Prozess puede sehr lange dauern).

Das erste Beispiel verwendet die gierige Quantifizierer .*, um "alles" zu finden, null oder mehrere Male, gefolgt von den Buchstaben "f" "o" "o". Da der Quantifizierer gierig ist, frisst der Teil .* des Ausdrucks Ausdrucks zuerst die gesamte Eingabe Zeichenfolge. An diesem Punkt kann der gesamte Ausdruck nicht erfolgreich sein, da die letzten drei Buchstaben ("f" "o" "o") bereits bereits verzehrt wurden ( von wem? ).

Die letzten drei Buchstaben, f , o y o wurden bereits von der ursprünglichen .* Teil der Vorschrift. Allerdings ist das nächste Element in der Regex, f hat nichts mehr in der Eingabezeichenfolge. Die Maschine wird gezwungen zurückverfolgen über seine ursprüngliche .* übereinstimmen, und versuchen Sie, bis auf das letzte Zeichen zu passen. (Es könnte sein smart und zurück zu all-but-the-last-three, weil es drei wörtliche Begriffe hat, aber ich kenne die Details der Implementierung auf dieser Ebene nicht).

Der Abgleicher langsam wieder zurück ( von rechts nach links? ) ein Buchstabe nach dem anderen bis das äußerste rechte Vorkommen von "foo" ausgekotzt wurde ( Was bedeutet das? ), bei dem

Dies bedeutet, dass die foo hatte vorläufig beim Abgleich berücksichtigt wurden .* . Da dieser Versuch fehlgeschlagen ist, versucht die Regex-Engine, ein Zeichen weniger in .* . Wenn es ein erfolgreiches Spiel gegeben hätte vor die .* in diesem Beispiel, dann würde die Maschine wahrscheinlich versuchen, die .* übereinstimmen (von rechts nach links, wie Sie sagten, da es sich um einen gierigen Qualifier handelt), und wenn er nicht in der Lage war, die gesamten Eingaben abzugleichen, dann könnte er gezwungen sein, neu zu bewerten, was er abgeglichen hatte vor die .* in meinem hypothetischen Beispiel.

Punkt ist die Übereinstimmung erfolgreich und die Suche endet.

Das zweite Beispiel ist jedoch zögerlich, also beginnt es damit, zunächst verbraucht ( von wem? ) "nichts". Weil "foo"

Das anfängliche Nichts wird verbraucht durch .?* , was die kürzestmögliche Menge von irgendetwas verbraucht, die es dem Rest der Regex erlaubt, übereinzustimmen.

erscheint nicht am Anfang der Datei Zeichenkette steht, wird es gezwungen, zu schlucken ( die Schwalben?) die

Wiederum die .?* verbraucht das erste Zeichen, nachdem es nach dem anfänglichen Fehlschlag die gesamte Regex mit der kürzest möglichen Übereinstimmung zurückverfolgt hat. (In diesem Fall erweitert die Regex-Maschine die Übereinstimmung für .*? von links nach rechts, weil .*? zögerlich ist).

ersten Buchstaben (ein "x"), der die die erste Übereinstimmung bei 0 und 4. Unser Test Testprogramm setzt den Prozess fort, bis die Eingabekette erschöpft ist. Es findet eine weitere Übereinstimmung bei 4 und 13.

Das dritte Beispiel findet keine Übereinstimmung, weil der Quantor possessiv ist. In diesem Fall wird die gesamte Eingabezeichenfolge durch .*+, ( Wie? )

A .*+ so viel wie möglich verbrauchen wird, und wird nicht zurückgehen um neue Übereinstimmungen zu finden, wenn die Regex als Ganzes keine Übereinstimmung findet. Da die possessive Form kein Backtracking durchführt, werden Sie wahrscheinlich nicht viele Anwendungen mit .*+ sondern eher mit Charakterklassen oder ähnlichen Einschränkungen: account: [[:digit:]]*+ phone: [[:digit:]]*+ .

Dies kann den Regex-Abgleich drastisch beschleunigen, da Sie der Regex-Engine mitteilen, dass sie niemals zu möglichen Übereinstimmungen zurückverfolgen soll, wenn eine Eingabe nicht übereinstimmt. (Wenn Sie den gesamten Code für den Abgleich von Hand schreiben müssten, wäre dies vergleichbar mit dem Verzicht auf die Verwendung von putc(3) um ein Eingabezeichen "zurückzuschieben". Es wäre dem naiven Code, den man beim ersten Versuch schreiben könnte, sehr ähnlich. Nur dass Regex-Engines viel besser sind als ein einzelnes Zeichen, sie können alles auf Null zurückspulen und es erneut versuchen :)

Aber nicht nur die Geschwindigkeit kann erhöht werden, sondern auch die Möglichkeit, Regexe zu schreiben, die genau dem entsprechen, was Sie brauchen. Es fällt mir schwer, ein einfaches Beispiel zu finden :), aber wenn man eine Regex mit possessiven und gierigen Quantifizierern schreibt, kann man unterschiedliche Übereinstimmungen erhalten, und die eine oder andere kann besser geeignet sein.

und nichts übrig bleibt, um sie zu befriedigen das "foo" am Ende des Ausdrucks Ausdrucks. Verwenden Sie einen possessiven Quantifizierer für Situationen, in denen Sie alles von etwas ergreifen wollen, ohne ohne jemals einen Rückzieher zu machen ( Was bedeutet "zurücktreten"? ); sie wird besser abschneiden als

"Zurückgehen" bedeutet in diesem Zusammenhang "Backtracking", d. h. das Verwerfen einer vorläufigen Teilübereinstimmung, um eine andere Teilübereinstimmung zu versuchen, die erfolgreich sein kann oder auch nicht.

der entsprechende gierige Quantor in Fällen, in denen die Übereinstimmung nicht nicht sofort gefunden wird.

Answer 4

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

Ich bin mir nicht sicher, ob das die beste Erklärung im Internet ist, aber sie ist ziemlich gut geschrieben und angemessen detailliert, und ich komme immer wieder darauf zurück. Vielleicht möchten Sie es sich ansehen.

Für einfache reguläre Ausdrücke wie den, den Sie gerade betrachten, funktioniert eine Engine für reguläre Ausdrücke durch Backtracking. Im Wesentlichen wählt sie einen Abschnitt der Zeichenkette aus ("frisst") und versucht, den regulären Ausdruck mit diesem Abschnitt abzugleichen. Wenn er passt, prima. Wenn nicht, ändert die Engine ihre Wahl des Abschnitts der Zeichenkette und versucht, den regulären Ausdruck mit diesem Abschnitt abzugleichen, und so weiter, bis sie alle möglichen Optionen ausprobiert hat.

Dieser Prozess wird rekursiv angewandt: Bei dem Versuch, eine Zeichenfolge mit einem bestimmten regulären Ausdruck abzugleichen, teilt die Engine den regulären Ausdruck in Teile auf und wendet den Algorithmus auf jeden Teil einzeln an.

Der Unterschied zwischen gierigen, zögernden und besitzergreifenden Quantifizierern kommt zum Tragen, wenn die Engine entscheidet, welcher Teil der Zeichenkette abgeglichen werden soll und wie die Auswahl geändert werden soll, wenn es beim ersten Mal nicht funktioniert. Die Regeln lauten wie folgt:

• Ein Greedy-Quantifizierer sagt der Maschine, dass sie mit der gesamte Zeichenkette (oder zumindest alles, was nicht schon von den vorherigen Teilen des regulären Ausdrucks gefunden wurde) und prüfen Sie, ob sie mit dem Regexp übereinstimmt. Ist dies der Fall, kann die Engine mit dem Rest der Regexp fortfahren. Ist dies nicht der Fall, wird ein Zeichen (das letzte) aus dem zu prüfenden Teil der Zeichenkette herausgeschnitten. Wenn das nicht klappt, wird ein weiteres Zeichen abgeschnitten, usw. Ein gieriger Quantifizierer prüft also mögliche Übereinstimmungen in der Reihenfolge vom längsten zum kürzesten Zeichen.

• Ein zurückhaltender Quantifizierer sagt der Maschine, dass sie mit dem kürzest möglichen Teil der Zeichenkette beginnen soll. Wenn es passt, kann die Maschine fortfahren; wenn nicht, wird sie fügt hinzu. ein Zeichen in den zu prüfenden Abschnitt der Zeichenkette ein und versucht es so lange, bis es eine Übereinstimmung findet oder die gesamte Zeichenkette verbraucht ist. Ein reluctant quantifier prüft also mögliche Übereinstimmungen in der Reihenfolge vom kürzesten zum längsten Zeichen.

• Ein Possessiv-Quantifizierer ist wie ein Gier-Quantifizierer beim ersten Versuch: Er weist die Maschine an, zunächst die gesamte Zeichenfolge zu überprüfen. Der Unterschied besteht darin, dass der Possessivquantifikator, wenn er nicht funktioniert, sofort meldet, dass die Übereinstimmung fehlgeschlagen ist. Die Maschine ändert den untersuchten Abschnitt der Zeichenkette nicht und unternimmt keine weiteren Versuche.

Das ist der Grund, warum die Übereinstimmung mit dem Possessivquantor in Ihrem Beispiel fehlschlägt: Die .*+ wird mit der gesamten Zeichenkette abgeglichen, die übereinstimmt, aber dann sucht die Maschine nach weiteren Zeichen foo danach - aber natürlich werden sie nicht gefunden, weil man bereits am Ende der Zeichenkette angelangt ist. Wäre es ein gieriger Quantifizierer, würde er zurückgehen und versuchen, die .* nur bis zum vorletzten Zeichen übereinstimmen, dann bis zum drittletzten Zeichen, dann bis zum viertletzten Zeichen, was gelingt, weil erst dann ein foo links nach der .* hat den früheren Teil der Zeichenkette "gefressen".

Answer 5

Hier ist mein Ansatz mit Zellen- und Indexpositionen (siehe die Diagramm hier um eine Zelle von einem Index zu unterscheiden).

Gierig - Entspricht so weit wie möglich dem gierigen Quantifizierer und der gesamten Regex. Wenn es keine Übereinstimmung gibt, gehe zurück auf den Greedy-Quantifizierer.

Eingabe String: xfooxxxxxxfoo
Regex: *Foo

Die oben genannten Regex hat zwei Teile:
(i)".*" und
(ii) "foo

In jedem der folgenden Schritte werden die beiden Teile analysiert. Zusätzliche Kommentare für eine Übereinstimmung mit "Bestanden" oder "Nicht bestanden" werden in geschweiften Klammern erläutert.

Schritt 1:
(i) .* = xfooxxxxxxfoo - PASS ('.*' ist ein gieriger Quantifizierer und verwendet den gesamten Input String)
(ii) foo = Kein Zeichen mehr für die Übereinstimmung nach Index 13 - FAIL
Spiel gescheitert.

Schritt 2:
(i) .* = xfooxxxxxxfo - PASS (Backtracking auf den gierigen Quantifizierer '.*')
(ii) foo = o - FAIL
Spiel gescheitert.

Schritt 3:
(i) .* = xfooxxxxxxf - PASS (Backtracking auf den gierigen Quantifizierer '.*')
(ii) foo = oo - FAIL
Spiel gescheitert.

Schritt 4:
(i) .* = xfooxxxxxx - PASS (Backtracking auf den gierigen Quantifizierer '.*')
(ii) foo = foo - PASS
MATCH melden

Ergebnis: 1 Spiel(e)
Ich habe den Text "xfooxxxxxxfoo" gefunden, der bei Index 0 beginnt und bei Index 13 endet.

Zurückhaltend - Passt so wenig wie möglich auf den zurückhaltenden Quantifizierer und passt auf die gesamte Regex. Wenn es keine Übereinstimmung gibt, füge Zeichen zum zurückhaltenden Quantifizierer hinzu.

Eingabe String: xfooxxxxxxfoo
Regex: .*?foo

Die obige Regex besteht aus zwei Teilen:
(i) ".*?" und
(ii) "foo

Schritt 1:
.*? = '' (Leerzeichen) - PASS (So wenig wie möglich mit dem widerstrebenden Quantifizierer '.*?' übereinstimmen. Index 0 mit '' ist eine Übereinstimmung.)
foo = xfo - FAIL (Zelle 0,1,2 - d.h. Index zwischen 0 und 3)
Spiel gescheitert.

Schritt 2:
.*? = x - PASS (Fügen Sie dem widerstrebenden Quantifizierer '.*?' Zeichen hinzu. Zelle 0 mit 'x' ist eine Übereinstimmung.)
foo = foo - PASS
MATCH melden

Schritt 3:
.*? = '' (Leerzeichen) - PASS (Passt so wenig wie möglich zu dem widerstrebenden Quantifizierer '.*?'. Index 4 mit '' ist eine Übereinstimmung.)
foo = xxx - FAIL (Zelle 4,5,6 - d.h. Index zwischen 4 und 7)
Spiel gescheitert.

Schritt 4:
.*? = x - PASS (Hinzufügen von Zeichen zum widerstrebenden Quantifizierer '.*?'. Zelle 4.)
foo = xxx - FAIL (Zelle 5,6,7 - d.h. Index zwischen 5 und 8)
Spiel gescheitert.

Schritt 5:
.*? = xx - PASS (Hinzufügen von Zeichen zum widerstrebenden Quantifizierer '.*?'. Zelle 4 bis 5.)
foo = xxx - FAIL (Zelle 6,7,8 - d.h. Index zwischen 6 und 9)
Spiel gescheitert.

Schritt 6:
.*? = xxx - PASS (Hinzufügen von Zeichen zum widerstrebenden Quantifizierer '.*?'. Zelle 4 bis 6.)
foo = xxx - FAIL (Zelle 7,8,9 - d.h. Index zwischen 7 und 10)
Spiel gescheitert.

Schritt 7:
.*? = xxxx - PASS (Fügen Sie dem widerstrebenden Quantifizierer '.*?' Zeichen hinzu. Zelle 4 bis 7.)
foo = xxf - FAIL (Zelle 8,9,10 - d.h. Index zwischen 8 und 11)
Spiel gescheitert.

Schritt 8:
.*? = xxxxx - PASS (Fügen Sie dem widerstrebenden Quantifizierer '.*?' Zeichen hinzu. Zelle 4 bis 8.)
foo = xfo - FAIL (Zelle 9,10,11 - d.h. Index zwischen 9 und 12)
Spiel gescheitert.

Schritt 9:
.*? = xxxxxx - PASS (Fügen Sie dem zurückhaltenden Quantifizierer '.*?' Zeichen hinzu. Zelle 4 bis 9.)
foo = foo - PASS (Zelle 10,11,12 - d.h. Index zwischen 10 und 13)
MATCH melden

Schritt 10:
.*? = '' (Leerzeichen) - PASS (So wenig wie möglich mit dem widerstrebenden Quantifizierer '.*?' übereinstimmen. Index 13 ist leer.)
foo = Kein übereinstimmendes Zeichen mehr - FAIL (nach Index 13 gibt es nichts mehr, was übereinstimmen könnte)
Spiel gescheitert.

Ergebnis: 2 Spiel(e)
Ich habe den Text "xfoo" gefunden, der bei Index 0 beginnt und bei Index 4 endet.
Ich habe den Text "xxxxxxfoo" gefunden, der bei Index 4 beginnt und bei Index 13 endet.

Possessiv - Passt so weit wie möglich auf das Possessivquantum und auf die gesamte Regex. NICHT zurückverfolgen.

Eingabe String: xfooxxxxxxfoo
Regex: *+foo

Die obige Regex besteht aus zwei Teilen: '.*+' und 'foo'.

Schritt 1:
.*+ = xfooxxxxxxfoo - PASS (Entspricht so weit wie möglich dem Possessivquantor '.*')
foo = Kein übereinstimmendes Zeichen mehr - FAIL (keine Übereinstimmung nach Index 13)
Spiel gescheitert.

Note : Backtracking ist nicht erlaubt.

Ergebnis: 0 Übereinstimmung(en)