Chciwi kontra niechętni kontra kwantyfikatory dzierżawcze

Znalazłem ten doskonały samouczek na temat wyrażeń regularnych i chociaż intuicyjnie rozumiem, co robią kwantyfikatory „chciwi”, „niechętni” i „zaborczy”, wydaje się, że mam poważne wątpliwości.

W szczególności w następującym przykładzie:

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.

Wyjaśnienie wspomina jedzenia cały ciąg wejściowy, listów zostały zużyte , dopasowujący odejściu , skrajna występowanie „foo” został regurgitated , etc.

Niestety, pomimo miłych metafor, wciąż nie rozumiem, co je ktoś ... Czy znasz inny samouczek, który wyjaśnia (zwięźle), jak działają silniki wyrażeń regularnych?

Alternatywnie, jeśli ktoś może wyjaśnić nieco inaczej frazując następujący akapit, byłoby to bardzo mile widziane:

Pierwszy przykład wykorzystuje chciwy kwantyfikator. *, Aby znaleźć „cokolwiek”, zero lub więcej razy, a następnie litery „f” „o” „o”. Ponieważ kwantyfikator jest zachłanny, część. * Wyrażenia najpierw zjada cały ciąg wejściowy. W tym momencie ogólne wyrażenie nie może się powieść, ponieważ ostatnie trzy litery („f” „o” „o”) zostały już wykorzystane ( przez kogo? ). Tak więc dopasowujący powoli cofa się ( od prawej do lewej? ) Po jednej literze, aż do wystąpienia zwrotu „foo” znajdującego się najbardziej po prawej stronie ( co to znaczy? ), W którym to momencie dopasowanie kończy się i wyszukiwanie się kończy.

Drugi przykład jest jednak niechętny, więc zaczyna się od skonsumowania ( przez kogo? ) „Nic”. Ponieważ „foo” nie pojawia się na początku łańcucha, jest zmuszone do przełknięcia ( kto połyka?) Pierwszej litery („x”), co wyzwala pierwsze dopasowanie przy 0 i 4. Nasza uprząż testowa kontynuuje proces dopóki łańcuch wejściowy nie zostanie wyczerpany. Znajduje kolejny mecz przy 4 i 13.

W trzecim przykładzie nie można znaleźć dopasowania, ponieważ kwantyfikator jest dzierżawczy. W tym przypadku cały ciąg wejściowy jest zużywany przez. * +, ( Jak? ) Nie pozostawiając nic, co mogłoby zaspokoić „foo” na końcu wyrażenia. Użyj kwantyfikatora dzierżawczego w sytuacjach, w których chcesz przejąć wszystko bez wycofywania się ( co oznacza wycofanie? ); przewyższy równoważny chciwy kwantyfikator w przypadkach, gdy dopasowanie nie zostanie natychmiast znalezione.

Spróbuję.

Chciwy kwantyfikatorów pierwsze mecze w jak największym stopniu. Więc .*dopasowuje cały ciąg. Następnie dopasowujący próbuje dopasować fponiższe, ale nie ma już znaków. Więc „cofa się”, powodując, że zachłanny kwantyfikator pasuje o jeden mniej znaków (pozostawiając „o” na końcu ciągu niedopasowane). To wciąż nie pasuje do fwyrażenia regularnego, więc cofa się o jeszcze jeden krok, dzięki czemu zachłanny kwantyfikator ponownie dopasowuje jeden znak mniej (pozostawiając „oo” na końcu łańcucha niedopasowane). To wciąż nie pasuje do fwyrażenia regularnego, więc cofa się o jeszcze jeden krok (pozostawiając „foo” na końcu łańcucha niedopasowane). Teraz dopasowywacz w końcu pasuje fdo wyrażenia regularnego,oosą również dopasowane. Sukces!

Niechętnie lub „non-chciwych” kwantyfikator pierwsze mecze w jak najmniejszym stopniu. Więc na początku .*nic nie pasuje, pozostawiając cały ciąg niezrównany. Następnie dopasowujący próbuje dopasować fnastępujące, ale niedopasowana część łańcucha zaczyna się od „x”, więc to nie działa. Więc dopasowujący backtracki, sprawiając, że niechciany kwantyfikator dopasuje jeszcze jeden znak (teraz pasuje do „x”, pozostawiając „fooxxxxxxfoo” bez porównania). Następnie próbuje dopasować f, co się powiedzie, a także oi następne ow wyrażeniu regularnym również. Sukces!

W twoim przykładzie następnie rozpoczyna proces od pozostałej niedopasowanej części ciągu „xxxxxxfoo”, wykonując ten sam proces.

Zaborczy kwantyfikator jest jak chciwy kwantyfikatorem, ale tak nie jest BackTrack. Zaczyna się więc od .*dopasowania całego łańcucha, nie pozostawiając niczego bez porównania. Wtedy nie ma już nic, co by pasowało fdo wyrażenia regularnego. Ponieważ kwantyfikator dzierżawczy nie cofa się, dopasowanie kończy się niepowodzeniem.

To tylko wynik mojej praktyki wizualizacji sceny

Nie słyszałem wcześniej dokładnych określeń „regurgitate” lub „wycofywanie się”; fraza, która je zastąpiłaby, to „cofanie się”, ale „regurgitacja” wydaje się równie dobra, jak każda inna fraza dla „treści, które zostały wstępnie zaakceptowane przed cofnięciem”.

Ważną rzeczą, o której należy pamiętać w przypadku większości silników wyrażeń regularnych jest to, że wycofują się : wstępnie zaakceptują potencjalne, częściowe dopasowanie, jednocześnie próbując dopasować całą zawartość wyrażenia regularnego. Jeśli wyrażenia regularnego nie można całkowicie dopasować przy pierwszej próbie, silnik wyrażenia regularnego cofnie się na jednym ze swoich dopasowań. Będzie spróbować dopasowanie *, +, ?, zmiany, lub {n,m}powtórzenie 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, a następnie litery „f” „o” „o”. Ponieważ kwantyfikator jest zachłanny, część. * Wyrażenia najpierw zjada cały ciąg wejściowy. W tym momencie ogólne wyrażenie nie może się powieść, ponieważ ostatnie trzy litery („f” „o” „o”) zostały już wykorzystane ( przez kogo? ).

Ostatnie trzy litery, f, o, i obyły już wykorzystywane przez początkowej .*części reguły. Jednak następny element wyrażenia regularnego fnie ma nic w ciągu wejściowym. Silnik zostanie zmuszony do cofnięcia się przy pierwszym .*dopasowaniu i spróbuje dopasować postać przedostatnią. (Może być sprytny i cofać się do prawie trzech ostatnich, ponieważ ma trzy dosłowne terminy, ale nie znam szczegółów implementacji na tym poziomie).

Tak więc dopasowujący powoli cofa się ( od prawej do lewej? ) Po jednej literze, aż do momentu, gdy najbardziej po prawej stronie występuje „foo” ( co to znaczy? ), Przy czym

Oznacza to, fooże wstępnie uwzględniono to podczas dopasowywania .*. Ponieważ ta próba się nie powiodła, silnik wyrażeń regularnych próbuje zaakceptować jedną mniejszą liczbę znaków .*. Gdyby były udane mecze przed.* w tym przykładzie, to silnik będzie prawdopodobnie spróbować skrócenie .*meczu (od prawej do lewej, jak pan zauważył, bo jest chciwy kwalifikator), a jeśli to nie był w stanie meczu cała wejść, to może być zmuszony do ponownej oceny, co to było dopasowane przed.* w moim hipotetycznym przykładzie.

wskaż, że dopasowanie się powiedzie i wyszukiwanie się zakończy.

Drugi przykład jest jednak niechętny, więc zaczyna się od skonsumowania ( przez kogo? ) „Nic”. Ponieważ „foo”

Początkowe nic nie jest zużywane .?*, co zużywa możliwie najkrótszą ilość wszystkiego, co pozwala dopasować resztę wyrażenia regularnego.

nie pojawia się na początku łańcucha, jest zmuszony do przełknięcia ( kto połyka?)

Ponownie .?*zużywa pierwszą postać, po cofnięciu początkowego braku dopasowania całego wyrażenia regularnego do możliwie najkrótszego dopasowania. (W tym przypadku silnik regex rozszerza dopasowanie .*?z lewej na prawą, ponieważ .*?jest niechętny).

pierwsza litera („x”), która wyzwala pierwsze dopasowanie przy 0 i 4. Nasza wiązka testowa kontynuuje proces do wyczerpania ciągu wejściowego. Znajduje kolejny mecz przy 4 i 13.

W trzecim przykładzie nie można znaleźć dopasowania, ponieważ kwantyfikator jest dzierżawczy. W takim przypadku cały ciąg wejściowy jest zużywany przez. * +, ( Jak? )

A .*+zużyje tyle, ile to możliwe, i nie cofnie się, aby znaleźć nowe dopasowania, gdy regex jako całość nie znajdzie dopasowania. Ponieważ forma zaborczy nie wykonuje Backtracking, prawdopodobnie nie będzie widać wiele zastosowań z .*+, ale raczej z klas postaci lub podobnych ograniczeń: account: [[:digit:]]*+ phone: [[:digit:]]*+.

Może to drastycznie przyspieszyć dopasowanie wyrażeń regularnych, ponieważ mówisz silnikowi wyrażeń regularnych, że nigdy nie powinien cofać się względem potencjalnych dopasowań, jeśli dane wejściowe się nie zgadzają. (Gdyby trzeba było ręcznie napisać cały pasujący kod, byłoby to podobne do tego, aby nigdy nie putc(3)„wypychać” znaku wejściowego. Byłby bardzo podobny do naiwnego kodu, który można napisać przy pierwszej próbie. Z wyjątkiem silników regex znacznie lepiej niż jeden znak push-back, mogą przewinąć do tyłu do zera i spróbować ponownie. :)

Ale więcej niż potencjalne przyspieszenia, może to również umożliwić pisanie wyrażeń regularnych pasujących dokładnie do tego, czego potrzebujesz. Mam problem z wymyśleniem prostego przykładu :), ale napisanie wyrażenia regularnego za pomocą kwantyfikatorów dzierżawczych i zachłannych może dać ci różne dopasowania, a jedno lub drugie może być bardziej odpowiednie.

nie pozostawiając nic, co zaspokoi „foo” na końcu wyrażenia. Użyj kwantyfikatora dzierżawczego w sytuacjach, w których chcesz przejąć wszystko bez wycofywania się ( co oznacza wycofanie? ); osiągnie lepsze wyniki

„Wycofanie się” w tym kontekście oznacza „wycofanie się” - odrzucenie niepewnego dopasowania częściowego w celu wypróbowania kolejnego dopasowania częściowego, które może się powieść lub nie.

równoważny chciwy kwantyfikator w przypadkach, gdy dopasowanie nie zostanie natychmiast znalezione.

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

Nie jestem pewien, czy to najlepsze wytłumaczenie w Internecie, ale jest dość dobrze napisane i odpowiednio szczegółowe i wciąż do niego wracam. Może będziesz chciał to sprawdzić.

Jeśli potrzebujesz wyższego poziomu (mniej szczegółowych wyjaśnień), dla prostych wyrażeń regularnych, takich jak to, na które patrzysz, silnik wyrażeń regularnych działa poprzez cofanie się. Zasadniczo wybiera („zjada”) sekcję łańcucha i próbuje dopasować wyrażenie regularne do tej sekcji. Jeśli pasuje, to świetnie. Jeśli nie, silnik zmienia wybór sekcji ciągu i próbuje dopasować wyrażenie regularne do tej sekcji itd., Dopóki nie zostanie wypróbowany każdy możliwy wybór.

Ten proces jest wykorzystywany rekurencyjnie: podczas próby dopasowania łańcucha do danego wyrażenia regularnego silnik podzieli wyrażenie regularne na części i zastosuje algorytm do każdego elementu osobno.

Różnica między kwantyfikatorami zachłannymi, niechętnymi i zaborczymi pojawia się, gdy silnik wybiera, z którą częścią łańcucha próbować dopasować, i jak zmodyfikować ten wybór, jeśli nie zadziała za pierwszym razem. Reguły są następujące:

• Chciwy kwantyfikator nakazuje silnikowi rozpoczęcie od całego łańcucha (a przynajmniej od tego, który nie został jeszcze dopasowany przez poprzednie części wyrażenia regularnego) i sprawdzenie, czy pasuje on do wyrażenia regularnego. Jeśli tak, to świetnie; silnik może kontynuować z resztą wyrażenia regularnego. Jeśli nie, spróbuje ponownie, ale przycina jeden znak (ostatni) z odcinka ciągu, który ma zostać sprawdzony. Jeśli to nie zadziała, przycina inną postać itp. 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 możliwie najkrótszego kawałka łańcucha. Jeśli pasuje, silnik może kontynuować; jeśli nie, dodaje jeden znak do sekcji sprawdzanego ciągu i próbuje tego, i tak dalej, aż znajdzie dopasowanie lub cały ciąg zostanie wykorzystany. Niechętny kwantyfikator sprawdza możliwe dopasowania w kolejności od najkrótszego do najdłuższego.

• Kwantyfikator dzierżawczy jest jak chciwy kwantyfikator przy pierwszej próbie: nakazuje silnikowi rozpoczęcie od sprawdzenia całego łańcucha. Różnica polega na tym, że jeśli to nie działa, kwantyfikator dzierżawczy zgłasza, że ​​dopasowanie zakończyło się niepowodzeniem. Silnik nie zmienia sekcji oglądanego ciągu i nie podejmuje już żadnych prób.

Właśnie dlatego dopasowanie kwantyfikatora dzierżawczego kończy się niepowodzeniem w twoim przykładzie: .*+ sprawdzany jest cały ciąg, do którego pasuje, ale potem silnik kontynuuje wyszukiwanie dodatkowych znaków foo- ale oczywiście nie znajduje ich, ponieważ ty są już na końcu ciągu. Gdyby był chciwym kwantyfikatorem, cofnąłby się i próbował .*dopasować jedyne dopasowanie do znaku od następnego do ostatniego, następnie do znaku od trzeciego do ostatniego, a następnie do znaku od czwartego do ostatniego, co się udaje, ponieważ tylko wtedy jest istnieje foolewo po .*został „zjedzony” wcześniejszej części łańcucha.

Oto moje ujęcie przy użyciu pozycji komórki i indeksu (patrz schemat tutaj aby odróżnić komórkę od indeksu).

Chciwy - Dopasuj jak najwięcej do chciwego kwantyfikatora i całego wyrażenia regularnego. Jeśli nie ma dopasowania, cofnij się na chciwym kwantyfikatorze.

Ciąg wejściowy: xfooxxxxxxfoo
Regex * Foo

Powyższy Regex składa się z dwóch części:
(i) „. *”
Oraz (ii) „foo”

Każdy z poniższych kroków przeanalizuje dwie części. Dodatkowe komentarze dotyczące dopasowania do „Pass” lub „Fail” wyjaśniono w nawiasach klamrowych.

Krok 1:
(i). * = Xfooxxxxxxfoo - PASS ('. *' Jest zachłannym kwantyfikatorem i użyje całego ciągu wejściowego)
(ii) foo = Brak znaku do dopasowania po indeksie 13 - FAIL
Matching nie powiodło się.

Krok 2:
(i). * = Xfooxxxxxxfo - PASS (powrót do chciwego kwantyfikatora „. *”)
(Ii) foo = o - FAIL
Dopasowanie nie powiodło się.

Krok 3:
(i). * = Xfooxxxxxxf - PASS (powrót do chciwego kwantyfikatora „. *”)
(Ii) foo = oo - FAIL
Dopasowanie nie powiodło się.

Krok 4:
(i). * = Xfooxxxxxx - PASS (powrót do chciwego kwantyfikatora „. *”)
(Ii) foo = foo - PASS
Report MATCH

Wynik: 1 dopasowanie (
-a ) 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łe wyrażenie regularne. jeśli nie ma dopasowania, dodaj znaki do kwantyfikatora niechętnego.

Ciąg wejściowy: xfooxxxxxxfoo
Regex :. *? Foo

Powyższe wyrażenie regularne składa się z dwóch części:
(i) „. *?” oraz
(ii) „foo”

Krok 1:.
*? = '' (puste) - PASS (Dopasuj jak najmniej do opornego kwantyfikatora „. *?”. Indeks 0 mający „” jest dopasowany.)
foo = xfo - FAIL (komórka 0,1,2 - tj. indeks między 0 i 3)
Dopasowanie nie powiodło się.

Krok 2:.
*? = x - PASS (Dodaj znaki do niechętnego kwantyfikatora „. *?”. Komórka 0 mająca „x” jest zgodna.)
foo = foo - PASS
Report MATCH

Krok 3:.
*? = '' (puste) - PASS (Dopasuj jak najmniej do opornego kwantyfikatora „. *?”. Indeks 4 mający „” jest dopasowany.)
foo = xxx - FAIL (komórka 4,5,6 - tj. indeks między 4 i 7)
Mecz nieudany.

Krok 4:.
*? = x - PASS (Dodaj znaki do kwantyfikatora niechętnego „. *?”. Komórka 4.)
foo = xxx - FAIL (Komórka 5,6,7 - tj. indeks między 5 a 8)
Dopasowanie nie powiodło się.

Krok 5:.
*? = xx - PASS (Dodaj znaki do niechętnego kwantyfikatora „. *?”. Komórka 4 do 5.)
foo = xxx - FAIL (Komórka 6,7,8 - tzn. indeks między 6 a 9)
Dopasowanie nie powiodło się.

Krok 6:.
*? = xxx - PASS (dodaj znaki do niechętnego kwantyfikatora „. *?”. Komórka 4 do 6.)
foo = xxx - FAIL (komórka 7,8,9 - tj. indeks między 7 a 10)
Dopasowanie nie powiodło się.

Krok 7:.
*? = xxxx - PASS (dodaj znaki do kwantyfikatora niechętnego „. *?”. Komórka 4 do 7.)
foo = xxf - FAIL (komórka 8,9,10 - tzn. indeks między 8 a 11)
Dopasowanie nie powiodło się.

Krok 8:.
*? = xxxxx - PASS (dodaj znaki do kwantyfikatora niechętnego „. *?”. Komórka 4 do 8.)
foo = xfo - FAIL (komórka 9,10,11 - tzn. indeks między 9 a 12)
Dopasowanie nie powiodło się.

Krok 9:.
*? = xxxxxx - PASS (dodaj znaki do kwantyfikatora niechętnego „. *?”. Komórka 4 do 9.)
foo = foo - PASS (komórka 10,11,12 - tj. indeks między 10 a 13)
Zgłoś MATCH

Krok 10:.
*? = '' (puste) - PASS (Dopasuj jak najmniej do opornego kwantyfikatora '. *?'. Indeks 13 jest pusty.)
foo = Brak znaku do dopasowania - FAIL (Po indeksie 13 nic nie pasuje)
Dopasuj nie powiodło się

Wynik: 2 dopasowania (e)
Znalazłem tekst „xfoo” zaczynający się od indeksu 0 i kończący się na indeksie 4.
Znalazłem tekst „xxxxxxfoo” rozpoczynający się od indeksu 4 i kończący się na indeksie 13.

Obsesyjnie - dopasuj jak najwięcej do kwantyfikatora dzierżawczego i dopasuj całe wyrażenie regularne. NIE wycofuj się.

Ciąg wejściowy: xfooxxxxxxfoo
Regex: * + Foo

Powyższe wyrażenie regularne składa się z dwóch części: „. * +” I „foo”.

Krok 1
:. * + = Xfooxxxxxxfoo - PASS (Dopasuj jak najwięcej do kwantyfikatora dzierżawczego „. *”)
Foo = Brak znaku do dopasowania - FAIL (Brak dopasowania po indeksie 13)
Dopasowanie nie powiodło się.

Uwaga: Cofanie jest niedozwolone.

Wynik: 0 meczów

Chciwy: „dopasuj najdłuższą możliwą sekwencję znaków”

Niechętnie: „dopasuj możliwie najkrótszą sekwencję znaków”

Obsesyjne: Jest to trochę dziwne, ponieważ NIE (w przeciwieństwie do chciwych i niechętnych) próbuje znaleźć dopasowanie dla całego wyrażenia regularnego.

Nawiasem mówiąc: Żadna implementacja dopasowywania wzorca wyrażenia regularnego nigdy nie będzie używać śledzenia wstecznego. Wszystkie wzorce rzeczywistych wzorców są niezwykle szybkie - prawie niezależne od złożoności wyrażeń regularnych!

Chciwa kwantyfikacja polega na dopasowaniu wzorca przy użyciu wszystkich pozostałych nieważnych znaków ciągu podczas iteracji. Nieważne znaki rozpoczynają się w aktywnej sekwencji . Za każdym razem, gdy dopasowanie nie nastąpi, znak na końcu jest poddawany kwarantannie i sprawdzanie jest wykonywane ponownie.

Gdy aktywna sekwencja spełnia tylko wiodące warunki wzoru wyrażenia regularnego, podejmowana jest próba sprawdzenia pozostałych warunków względem kwarantanny. Jeśli ta weryfikacja zakończy się powodzeniem, dopasowane znaki w kwarantannie są sprawdzane, a pozostałe niedopasowane znaki pozostają nieważne i zostaną użyte, gdy proces rozpocznie się od nowa w następnej iteracji.

Przepływ znaków odbywa się z aktywnej sekwencji do kwarantanny. Wynikowe zachowanie polega na tym, że jak najwięcej oryginalnej sekwencji znajduje się w dopasowaniu.

Niechętna kwantyfikacja jest w większości taka sama, jak chciwa kwalifikacja, z tym wyjątkiem, że przepływ znaków jest odwrotny - to znaczy, że zaczynają się w kwarantannie i przechodzą do aktywnej sekwencji . Wynikowe zachowanie polega na tym, że jak najmniej części oryginalnej sekwencji jest zawartych w dopasowaniu, jak to możliwe.

Kwantyfikacja dzierżawcza nie obejmuje kwarantanny i obejmuje wszystko w ustalonej aktywnej sekwencji .