Chciwy vs. niechętny vs. zaborczy

To tylko moja praktyka wizualizacji sceny-

Nie słyszałem wcześniej dokładnych terminów "regurgitate" lub "cofanie się"; zwrot, który mógłby je zastąpić, to "backtracking", ale "regurgitate" wydaje się równie dobrym zwrotem, jak każde inne wyrażenie dla "treści, które zostały wstępnie zaakceptowane przed backtrackingiem, wyrzuciły je ponownie".

Ważną rzeczą do uświadomienia sobie o większości silników regex jest to, że są one backtracking : będą wstępnie zaakceptować potencjalne, częściowe dopasowanie, starając się dopasować całą zawartość wyrażenia regularnego. Jeśli regex nie może być całkowicie dopasowany przy pierwszej próbie, to silnik regex backtrack na jednym z jego dopasowań. Spróbuje dopasować *, +, ?, alternacja, lub {n,m} powtarzanie inaczej, i spróbuj ponownie. (I tak, ten proces Może zająć dużo czasu.)

Pierwszy przykład wykorzystuje chciwy kwantyfikator .* aby znaleźć "cokolwiek", zero lub więcej razy, po których następują litery "f "" o " "o". Ponieważ kwantyfikator na greedy, the .* część wyrażenie najpierw zjada całe wejście sznurek. W tym momencie, ogólnie wyrażenie nie może odnieść sukcesu, ponieważ trzy ostatnie litery ("f "" o "" o") mają już zostały skonsumowane (przez kogo?).

Ostatnie trzy litery, f, o, i o zostały już spożyte przez początkową .* część reguły. Jednak następny element w regex, f, nie ma nic w łańcuchu wejściowym. Silnik będzie zmuszony do backtrack na jego początkowym dopasowaniu .* i spróbuj dopasować wszystkie znaki oprócz ostatniego. (Może to być smart i powrót do wszystkich-ale-ostatnich-trzech, ponieważ ma trzy dosłowne terminy, ale nie jestem świadomy szczegółów implementacji na tym poziomie.)

Więc matcher powoli wycofuje się (od prawej do lewej?) jedna litera na raz aż do momentu pojawienia się "foo" zostało zwrócone (co to znaczy?), w które

Oznacza to, że foo miały wstępnie były uwzględniane przy dopasowywaniu .*. Ponieważ ta próba nie powiodła się, silnik regex próbuje zaakceptować jeden znak mniej w .*. Jeśli w tym przykładzie doszło by do udanego meczu przed .*, to silnik prawdopodobnie spróbowałby skrócić mecz .* (od prawej do lewej, jak zauważyłeś, ponieważ jest to chciwy kwalifikator), a jeśli nie byłby w stanie dopasować całych wejść, To może być zmuszony do aby ponownie ocenić, co pasowało przed .* w moim hipotetycznym przykładzie.

Punkt mecz się powiódł i koniec poszukiwań.

Drugim przykładem jest jednak niechętny, więc zaczyna się od pierwszego spożywanie ( przez kogo?) "nic". Ponieważ " foo "

Początkowe nic jest konsumowane przez .?*, które pochłonie możliwie najkrótszą ilość czegokolwiek, co pozwala na dopasowanie reszty wyrażenia regularnego.

Nie pojawia się na początku / align = "left" / Linear) the

Ponownie .?* zużywa pierwszy znak, po odtworzeniu początkowego błędu, aby dopasować cały regex do najkrótszego możliwego dopasowania. (W tym przypadku silnik regex rozszerza dopasowanie dla .*? z lewej do prawej, ponieważ .*? jest niechętny.)

Pierwsza litera ("x"), która wyzwala pierwszy mecz o 0 i 4. Nasz test uprząż kontynuuje proces aż do łańcuch wejściowy jest wyczerpany. Informatyka kolejne mecze o miejsca 4 i 13.

Trzeci przykład nie znajduje dopasować, ponieważ kwantyfikator jest zaborczy. W tym przypadku cała input string jest używany przez .* + , ( jak?)

A .*+ pochłonie jak najwięcej, a nie cofnie się, aby znaleźć nowe dopasowania, gdy regex jako całość nie znajdzie dopasowania. Ponieważ forma dzierżawcza nie spełnia backtracking, prawdopodobnie nie zobaczysz wielu zastosowań z .*+, ale raczej z klasami znaków lub podobnymi ograniczeniami: account: [[:digit:]]*+ phone: [[:digit:]]*+.

Może to drastycznie przyspieszyć dopasowanie regex, ponieważ mówisz silnikowi regex, że nigdy nie powinien cofać się nad potencjalnymi dopasowaniami, jeśli Dane wejściowe nie pasują. (Gdybyś musiał ręcznie napisać cały pasujący kod, byłoby to podobne do nigdy nie używania putc(3) do 'odepchnięcia' znaku wejściowego. Byłoby bardzo podobne do naiwnego kodu, który można by napisać za pierwszym razem. Z tym, że silniki regex są o wiele lepsze niż pojedynczy znak push-back, mogą cofnąć wszystkie wstecz do zera i spróbować ponownie. :)

Ale więcej niż potencjalne przyspieszenie, może to również pozwolić ci pisać wyrażenia regularne, które pasują dokładnie do tego, co musisz dopasować. Mam problem z wymyśleniem prostego przykładu :) ale pisanie wyrażenia regularnego za pomocą dzierżawczych vs chciwych kwantyfikatorów może dać różne dopasowania, a jeden lub drugi może być bardziej odpowiedni.

Zostawiając nic pozostawione do zaspokojenia "foo" na końcu ekspresja. Use a possessive kwantyfikator dla sytuacji, w których chcesz przejąć wszystko bez co to znaczy cofać się?); będzie lepszy

"cofanie się" w tym kontekście oznacza "cofanie" - odrzucenie wstępnego partial matchu, aby spróbować innego partial matchu, który może się udać lub nie.

Odpowiednikiem kwantyfikatora w przypadki, w których mecz jest nie natychmiast znaleziony.

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

Nie jestem pewien, czy to najlepsze wyjaśnienie w Internecie, ale jest dość dobrze napisane i odpowiednio szczegółowe, i wciąż do niego wracam. Może zechcesz to sprawdzić.

Jeśli potrzebujesz wyższego poziomu (mniej szczegółowego wyjaśnienia) dla prostych wyrażeń regularnych, takich jak to, na które patrzysz, silnik wyrażeń regularnych działa poprzez cofanie. Zasadniczo wybiera ("zjada") fragment łańcucha i próbuje dopasować Wyrażenie regularne do tej sekcji. Jeśli pasuje, świetnie. Jeśli nie, Silnik zmienia swój wybór sekcji łańcucha i próbuje dopasować Wyrażenie regularne do tej sekcji, i tak dalej, dopóki nie spróbuje każdego możliwego wyboru.

Ten proces jest używany rekurencyjnie: próbując dopasować łańcuch z danym wyrażeniem regularnym, silnik podzieli Wyrażenie regularne Na części i zastosuje algorytm do każdego elementu indywidualnie.

Różnica pomiędzy chciwymi, niechętnymi i zaborczymi kwantyfikatorami pojawia się, gdy silnik dokonuje wyboru, z którą częścią łańcucha próbuje się dopasować i jak zmodyfikować ten wybór, jeśli nie zadziała za pierwszym razem. Zasady są następujące:

• Chciwy kwantyfikator mówi silnikowi, aby zaczynał od całego ciągu znaków (lub przynajmniej wszystkiego, co nie zostało jeszcze dopasowane przez poprzednie części wyrażenia regularnego) i sprawdzał, czy pasuje do wyrażenia regularnego. Jeśli tak, świetnie; silnik może kontynuować z resztą wyrażenia regularnego. Jeśli nie, spróbuje ponownie, ale przycinając jeden znak (ostatni) z sekcji łańcucha, który ma być sprawdzany. Jeśli to nie działa, to przycina inny znak itp. Tak więc chciwy kwantyfikator sprawdza możliwe dopasowania w kolejności od najdłuższego do najkrótszego.

• Niechętny kwantyfikator mówi silnikowi, aby zaczął od najkrótszego możliwego kawałka ciągu. Jeśli to pasuje, silnik może kontynuować; jeśli nie, to dodaje jeden znak do sekcji sprawdzanego łańcucha i próbuje tego, i tak dalej, aż znajdzie dopasowanie lub cały łańcuch został wykorzystany. Tak więc niechętny kwantyfikator sprawdza możliwe dopasowania w kolejności od najkrótszej do najdłuższej.

• Dzierżawczy kwantyfikator jest jak chciwy kwantyfikator przy pierwszej próbie: mówi silnikowi, aby zaczął od sprawdzenia całego ciągu. Różnica polega na tym, że jeśli to nie zadziała, dzierżawczy kwantyfikator zgłasza, że mecz nie powiódł się wtedy i tam. Silnik nie zmienia sekcji przeglądanego ciągu i nie podejmuje już żadnych prób.

Dlatego dzierżawczy quantifier nie sprawdza się w twoim przykładzie: .*+ jest sprawdzany z całym łańcuchem znaków, który pasuje, ale potem silnik szuka dodatkowych znaków foo - ale oczywiście ich nie znajduje, ponieważ jesteś już na końcu łańcucha. Gdyby był chciwym kwantyfikatorem, cofnąłby się i spróbuj dopasować .* Tylko do następnego do ostatniego znaku, następnie do trzeciego do ostatniego znaku, a następnie do czwartego do ostatniego znaku, co się powiedzie, ponieważ tylko wtedy zostaje foo po .* "zjadł" wcześniejszą część łańcucha.

Oto moje podejście do pozycji komórki i indeksu (zobacz diagram tutaj, aby odróżnić komórkę od indeksu).

Greedy-Dopasuj jak najwięcej do kwantyfikatora greedy i całego wyrażenia regularnego. Jeśli nie ma dopasowania, wróć do chciwego kwantyfikatora.

Input String: xfooxxxxxfoo
Regex: .* foo

Powyższy Regex ma dwie części:
i)".* "i
(ii) " foo "

Każdy z poniższych kroków będzie przeanalizuj te dwie części. Dodatkowe komentarze do meczu "Pass" lub "Fail" są wyjaśnione w klamrach.

Krok 1:
i) .* = XFOOXXXXXFOO-PASS ('.* 'jest kwantyfikatorem chciwym i użyje całego ciągu wejściowego)
(ii) foo = żaden znak nie zostanie dopasowany po indeksie 13-FAIL
Mecz zakończył się niepowodzeniem.

Krok 2:
i) .* = xfooxxxxxfo-PASS (Backtracking on the greedy quantifier".*')
(ii) foo = o-FAIL
Mecz zakończył się niepowodzeniem.

Krok 3:
i) .* = xfooxxxxxf-PASS (Backtracking on the greedy quantifier".*')
(ii) foo = oo-FAIL
Mecz zakończył się niepowodzeniem.

Krok 4:
i) .* = XFOOXXXXXX-PASS (Backtracking on the greedy quantifier".*')
(ii) foo = Foo-PASS
Report MATCH

Wynik: 1 mecz (y)
Znalazłem tekst "xfooxxxxxxfoo" zaczynający się od indeksu 0 i kończący się na indeksie 13.

Niechętny-Dopasuj jak najmniej do niechętnego kwantyfikatora i dopasuj cały regex. jeśli nie ma dopasuj, Dodaj znaki do kwantyfikatora.

Input String: xfooxxxxxfoo
Regex: .*?foo

Powyższy regex ma dwie części:
i)".*?"i
(ii) " foo "

Krok 1:
.*? = "(blank) - PASS (Dopasuj jak najmniej do kwantyfikatora",*?'. / Align = "left" / )
foo = xfo-FAIL (Komórka 0,1,2 - tzn. indeks między 0 a 3)
Mecz zakończył się niepowodzeniem.

Krok 2:
.*? = X-PASS (Add characters to the quantifier".*?'. Komórka 0 posiadająca "x" jest zgodna.)
foo = Foo-PASS
Report MATCH

Krok 3:
.*? = "(blank) - PASS (Dopasuj jak najmniej do kwantyfikatora",*?'. / Align = "left" / )
foo = xxx-FAIL (Cell 4,5,6 - i.e index between 4 and 7)
Mecz zakończył się niepowodzeniem.

Krok 4:
.*? = X-PASS ( Dodaj znaki do niechętny kwantyfikator".*?'. Cela 4.)
foo = xxx-FAIL (Cell 5,6,7 - i.e index between 5 and 8)
Mecz zakończył się niepowodzeniem.

Krok 5:
.*? = xx-PASS (Dodaj znaki do kwantyfikatora".*?'. Cela 4 do 5.)
foo = xxx-FAIL (Cell 6,7,8 - i.e index between 6 and 9)
Mecz zakończył się niepowodzeniem.

Krok 6:
.*? = XXX-PASS (Dodaj znaki do kwantyfikatora".*?'. Cela od 4 do 6.)
foo = xxx - FAIL (Komórka 7,8,9 - czyli indeks między 7 a 10)
Mecz zakończył się niepowodzeniem.

Krok 7:
.*? = xxxx-PASS (Dodaj znaki do kwantyfikatora".*?'. Cela od 4 do 7.)
foo = xxf-FAIL (Komórka 8,9,10 - tzn. indeks między 8 a 11)
Mecz zakończył się niepowodzeniem.

Krok 8:
.*? = xxxxx-PASS (Dodaj znaki do kwantyfikatora".*?'. Cela od 4 do 8.)
foo = xfo-FAIL (Komórka 9,10,11-czyli indeks między 9 i 12)
Mecz zakończył się niepowodzeniem.

Krok 9:
.*? = xxxxxx-PASS (Dodaj znaki do kwantyfikatora".*?'. Cela od 4 do 9.)
foo = Foo-PASS (Komórka 10,11,12 - indeks między 10 a 13)
Report MATCH

Krok 10:
.*? = "(blank) - PASS (Dopasuj jak najmniej do kwantyfikatora",*?'. Indeks 13 jest pusty.)
foo = No character left to match-FAIL (nie ma nic po indeksie 13 do dopasowania)
Mecz nie udało się.

Wynik: 2 mecz (ów)
Znalazłem tekst "xfoo" zaczynający się od indeksu 0 i kończący się na indeksie 4.
Znalazłem tekst "xxxxxxfoo" zaczynający się od indeksu 4 i kończący się na indeksie 13.

Dzierżawczy-Dopasuj jak najwięcej do dzierżawczego kwantyfikatora i dopasuj cały regex. Nie cofaj się.

Input String: xfooxxxxxfoo
Regex: .* + foo

Powyższy regex ma dwie części:'.* + "i " foo".

Krok 1:
.*+ = XFOOXXXXXFOO-PASS (Dopasuj jak najwięcej do kwantyfikatora dzierżawczego".*')
foo = No character left to match-FAIL (Nothing to match po indeksie 13)
Mecz zakończył się niepowodzeniem.

uwaga: cofanie nie jest dozwolone.

wynik: 0 mecz (ów)

Greedy: "dopasuj najdłuższy możliwy ciąg znaków"

: "dopasuj najkrótszą możliwą sekwencję znaków"

Dzierżawczy: jest to trochę dziwne, ponieważ nie próbuje (w przeciwieństwie do chciwych i niechętnych) znaleźć dopasowania dla całego wyrażenia regularnego.

Przy okazji: Żadna implementacja regex pattern matcher nigdy nie użyje backtrackingu. Wszystkie prawdziwe matryce wzorcowe są niezwykle szybkie - prawie niezależne od złożoności wyrażenia regularnego!

Greedy Quantification polega na dopasowaniu wzorca przy użyciu wszystkich pozostałych nie wartościowanych znaków ciągu podczas iteracji. Znaki niezaliczone rozpoczynają się w sekwencji aktywnej . Za każdym razem, gdy dopasowanie nie występuje, znak na końcu jest poddawany kwarantannie i sprawdzanie jest wykonywane ponownie.

Gdy tylko główne warunki wzorca regex są spełnione przez sekwencję aktywną, podejmowana jest próba walidacji pozostałych warunków względem kwarantanna. Jeśli ta Walidacja się powiedzie, dopasowane znaki w kwarantannie zostaną zweryfikowane, a pozostałe niezrównane znaki pozostaną niewalidowane i zostaną użyte, gdy proces rozpocznie się na nowo w następnej iteracji.

Przepływ znaków jest z aktywnej sekwencji do kwarantanny. Wynikiem tego zachowania jest to, że jak najwięcej oryginalnej sekwencji jest zawarte w meczu, jak to możliwe.

Niechętna kwantyfikacja jest w większości taka sama jak chciwa kwalifikacja z tym, że przepływ znaków jest odwrotnie-to znaczy, że zaczynają się w i przepływają do } aktywnego ciągu . Wynikiem tego zachowania jest to, że jak najmniej oryginalnej sekwencji jest zawarte w meczu, jak to możliwe.

Kwantyfikacja dzierżawcza {[2] } nie ma kwarantanny i zawiera wszystko w stałej aktywnej sekwencji .