Chciwi kontra niechętni kontra kwantyfikatory dzierżawcze

357

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.

Regex Świeżak
źródło
22
Maksymalne kwantyfikatory podoba *, +i ?chciwi. Minimalny kwantyfikatory podoba *?, +?i ??leniwi. Dzierżawcze kwantyfikatorów jak *+, ++i ?+lepkie.
tchrist
6
To pytanie zostało dodane do często zadawanych pytań dotyczących wyrażeń regularnych przepełnienia stosu , w części „Kwantyfikatory> Więcej na temat różnic ...”.
aliteralmind
Interesujące: Poradniki Java ™ - Różnice między kwantyfikatorami chciwymi, niechętnymi i dzierżawczymi - Przewiń w dół, aby zobaczyć sekcję.
Guy Coder

Odpowiedzi:

495

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.

Dezorganizacja
źródło
15
+1 Dobra odpowiedź. Dodałbym tylko: Idź i przeczytaj Mastering Regular Expressions (3. wydanie)
ridgerunner
@Anomie trochę późno, ale w zaborczy sposób myślę, że miałeś na myśli Więc zaczyna się od .*+ (zauważ „+”)
RD
3
co dokładnie robi kwantyfikator dzierżawczy? jeśli to nie pasuje? (Mam na myśli, o co w tym wszystkim chodzi, jeśli nie możesz mieć po nim znaków)
powtórz
4
@relipse: Używałbyś tego w sytuacji, gdy wiesz, że cofanie się nie pomoże, prawdopodobnie nie z .*+tym wszystkim. Na przykład, jeśli masz wzorzec [xyz]*foo, nie ma możliwości, aby cofnięcie x, y i z dopasowanych przez [xyz]*bit kiedykolwiek pozwoliło dopasować następujący foobit, więc możesz przyspieszyć, czyniąc go zaborczym.
Anomie
4
@moodboom, zawsze jest zero przypadków (fakt matematyczny), w których kwantyfikatory dzierżawcze spowodują dopasowanie , które nie zostanie wygenerowane przez proste kwantyfikatory chciwe. Czasami zdarzają się przypadki braku dopasowania, gdy zachłanne kwantyfikatory spowodują dopasowanie. We WSZYSTKICH innych przypadkach (gdzie zachłanne i zaborcze dają takie same wyniki), kwantyfikatory dzierżawcze dają wzrost wydajności.
Wildcard
49

To tylko wynik mojej praktyki wizualizacji sceny

Obraz wzrokowy

SIslam
źródło
3
Z wyjątkiem tego, że uważam, że ostatni przypadek zaborczy nie powinien mieć n przepustek - wystarczy chwycić cały łańcuch naraz.
traktuj swoje mody dobrze
@ phyzome Myślę, że teraz jest w porządku?
SIslam
1
Dzięki za wyjaśnienie wizualne :)
Lars Moelleken,
W EXPRESSION .*?foo(), czy [f] [o] [o]prostokąty nie powinny być żółte w 5th pass?
tonix
1
@tonix tak! Należy wykonać żółte zabarwienie dla dopasowanej części w wyrazie .*?fooi .*+foo.
SIslam,
24

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.

Sarnold
źródło
2
Podejrzewam, że nigdy nie ma przypadku, w którym kwantyfikator dzierżawczy pasuje do czegoś, czego kwantyfikator chciwy nie pasuje. Uważam, że to potwierdza: chciwy kwantyfikator zawsze pasuje tak dużo, jak to możliwe, a następnie cofa się, jeśli nie może znaleźć dopasowania. Kwantyfikator dzierżawczy dopasowuje jak najwięcej, a następnie kończy pracę, jeśli nie może znaleźć dopasowania. Może więc być coś, co zachłanny kwantyfikator pasuje do tego, czego kwantyfikator dzierżawczy nie, ale nie odwrotnie, ponieważ obaj przeszukują „drzewo” w tej samej sekwencji, kwantyfikator dzierżawczy po prostu łatwiej się poddaje. ;)
Wildcard
2
Potwierdzony: „Do tego właśnie służą grupowanie atomowe i kwantyfikatory dzierżawcze: wydajność poprzez niedopuszczanie do cofania się”. z regular-expressions.info Tak więc stwierdzenie w tej odpowiedzi „Ale oprócz potencjalnych przyspieszeń, może to również pozwolić na pisanie wyrażeń regularnych pasujących dokładnie do tego, co musisz dopasować”. w rzeczywistości nie jest całkiem dokładne.
Wildcard,
1
@Wildcard, dzięki za komentarze; to może wyjaśniać, dlaczego miałem problem z wymyśleniem przykładu. Hehe
sarnold
19

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.

David Z
źródło
1
To doskonałe źródło. Uwielbiam diagramy stanu maszyny. :)
Regex Rookie
@Regex Rookie: cieszę się, że ci się podoba :) Po przejrzeniu tej witryny myślę jednak, że powinienem wyjaśnić, że jej celem jest promowanie alternatywnej implementacji silnika wyrażeń regularnych. Algorytm cofania, który opisuję (częściowo) i inne odpowiedzi, jest wolny ; jest to całkowicie odrębny algorytm od idei NFA / DFA opisanej na stronie internetowej. Cofanie jest po prostu łatwiejsze do zrozumienia, dlatego tak zazwyczaj wyrażenia regularne są wyjaśniane początkującym.
David Z
@David Zaslavsky: Dobre wyjaśnienie. Wasze komentarze w nawiasach kwadratowych w „Chciwym kwantyfikatorze nakazują silnikowi rozpoczęcie całego łańcucha (a przynajmniej całego, który nie został jeszcze dopasowany przez poprzednie części wyrażenia regularnego)” są ważne. Odnoszą się one również do kwantyfikatorów niechętnych i zaborczych. To sprawia, że ​​twoje wyjaśnienie jest zgodne z tym, co dzieje się, gdy zmienimy nasze przykładowe wzorce z („. * Foo”; „. *? Foo”; i „. * + Foo”) na („foo. *”; „Foo. *? ”; i„ foo. * + ”).
John Bentley,
W rzeczywistości xfooxxxxxxfoo pasuje. * Foo w normalnym (znaczenie informatyki) wyrażenia regularnego. NFA byłby stanem, w którym zapętlałby się z dowolną postacią, a następnie mógł przeskakiwać do foo. DFA byłoby prostym tłumaczeniem tego NFA. Można to zrobić w 8 stanach.
user4951,
@JimThio tak, ponieważ nie jest to kwantyfikator dzierżawczy.
David Z
12

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

raka
źródło
1

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!

Tilo Koerbs
źródło
O ile mi wiadomo, większość implementacji ogólnego zastosowania jest teraz tak pełna, że ​​nie można było nie używać wstecznego śledzenia. Teoretycznie powinny one być bardzo (wykładniczo) powolne w niektórych przypadkach. Ale w większości przypadków istnieją specjalne optymalizacje wbudowane w moduł dopasowywania wzorców.
Robert,
0

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 .

Chad Philip Johnson
źródło