Jesteś tutaj: Główna → Wyrażenia regularne → Zachłanność

Zachłanność

Mechanizm dopasowywania wzorców jest zachłanny.

Jest również chciwy i nienasycony.

W terminach informatycznych oznacza to, że mechanizm dopasowywania wzorców dopasowuje tak dużo, jak mu się uda. Nie mniej.

Najprostszy przykład to wzorzec dopasowujący znaczniki HTML, który zaleciłem napisać czytelnikowi pod koniec rozdziału o powtórzeniach.

Dla ustalenia uwagi rozważmy następujący fragment kodu:

<p>To jest kod <abbr>HTML</abbr> taki sobie <em>tam</em>.</p>

Narzucające się wyrażenie <.+> (dopasuj znak <, dowolną – acz niepustą – treść za nim, wszystko zakończone znakiem >) działa niezgodnie z zamierzeniami. A jak ono działa?

Najpierw dopasowywany jest znak <, otwierający znacznik <p>. Następnie, kropka z plusem dopasowuje literkę p, a chwilę później znak >. Myślisz, że na tym mechanizm kończy swoje działanie? Otóż nie! Bo i czemuż miałby? > przecież pasuje przecież do wzorca .+! Mechanizm jest zachłanny - nie rezygnuje z dopasowania, jeśli może dopasować. I tak wędruje kropka z plusikiem przez cały nasz kod, aż natrafiając na koniec wiersza. W tym momencie dopasowany tekst to <p>To jest kod <abbr>HTML</abbr> taki sobie <em>tam</em>.</p>, a mechanizm orientuje się, że troszkę się zagalopował, bowiem został mu jeszcze jeden znak wyrażenia do dopasowania, a mianowicie >. Mechanizm w tym momencie skraca dopasowany tekst do <p>To jest kod <abbr>HTML</abbr> taki sobie <em>tam</em>.</p, jednocześnie zaczynając, zamiast kropki, dopasowywać znak większości. Et voila, ostatni znak przeszukiwanego przez nas tekstu pasuje; mamy więc dopasowany ciąg od jego początku aż do samego końca.

Jeden obraz mówi więcej niż tysiąc słów, przyjrzyjmy się więc jak takie dopasowywanie wygląda w Crimson Editorze:

Wprowadzamy wyrażenie i po kliknięciu na Find next w wyniku otrzymujemy zaznaczoną całą frazę:

Nie jest to jednak to, o co nam chodziło.

Rozwiązanie pierwsze - negacja

Wyrażenie .+ przeszukające „wnętrze” znaczników HTML dopasowuje zbyt dużo; gdyby zakazać mu (?) reagować na znak <, który otwiera nowy znacznik, wówczas wyrażenie działałoby zgodnie z naszymi oczekiwaniami, prawda?

Ponieważ znamy już znak negacji, zadanie jest proste: wystarczy napisać <[^<]+>, by zawęzić zakres znaków, na które wyrażenie reaguje. Teraz wszystko działa, jak trzeba:

Otrzymujemy:

Działa!

Rozwiązanie drugie - leniwe znaki powtórzeń

Niepoprawne Niezgodne z oczekiwaniami działanie wyrażenia <.+> wynika z zachłanności znaków powtórzeń. Szczęśliwie, mechanizm dopasowywania wzorców udostępnia nam możliwość przeinaczenia go – tego mechanizmu – w prawdziwego lenia, który, po odwaleniu swojej roboty, idzie na fajrant.

Efekt ten uzyskuje się poprzez postawienie znaku zapytania ? po znaku powtarzania. Można go postawić po wszystkich kwantyfikatorach wymienionych w rozdziale o powtórzeniach, to jest po asterisku *, plusie +, znaku zapytania ?, klamerkach {zakres dolny,} i {zakres dolny, zakres górny} (dostawianie ? po {liczba powtórzeń} nie ma, przyznasz, sensu).

Leniwe znaki powtórzeń nazywamy również kwantyfikatorami minimalistycznymi.

Przykłady

Przykład pierwszy

Wyrażenie <.+?> dopasuje znaczniki HTML. Dlaczego?

Przyjrzyjmy się dokładnie sposobowi, w jaki powyższe wyrażenie działa. Dla ustalenia uwagi przyjmijmy, że znacznikiem jest <EM>. Oczywiście < dopasowuje się do znaku mniejszości <, otwierającego znacznik. Następnie jest kropka, po której użyliśmy leniwego plusa. Plus dopasowuje co najmniej jedno wystąpienie poprzedzającego go znaku, w tym przypadku może to być znak dowolny. W naszym przypadku jest to E. Świetnie, plus może skończyć swoją robotę, gdyż już dopasował, co miał dopasować (przynajmniej jeden dowolny znak). Wyrażenie regularne sięga po znak następujący po E, czyli M, chcąc go dopasować do >. Dopasowanie nie udaje się, więc do pracy musi znowu przystąpić leniwy plus, poprzedzony kropką; mechanizm dopasowywania znaków w tym momencie cofa się w przeglądaniu wzorca. Kropka dopasowuje M, plus ponownie kończy swoją robotę (uff), mechanizm dopasowywać będzie teraz >. Tak się składa, że dopasowanie teraz się uda, gdyż > jest po świeżo znalezionym M. Mechanizm kończy pracę.

Przykład drugi

Rozważmy tekst Lorem ipsum dolor sit amet oraz wyrażenie regularne m.*m.

W tej formie działa ono następująco: dopasowuje m, następnie powtarza dopasowanie do momentu, aż natrafi na znak końca wiersza, ponownie orientując się, że został mu jeszcze jeden element wzorca do dopasowania – m. Dopasowany tekst w tym momencie to m ipsum dolor sit amet. Mechanizm cofa się w dopasowaniu, zmniejszając tekst najpierw do m ipsum dolor sit ame, następnie, po nieudanej próbie dopasowania m do m ipsum dolor sit am, na czym kończy pracę, gdyż ostatnia litera dopasowanego tekstu pasuje do dopasowywanego fragmentu wzorca. Finito!

W przypadku wyrażenia m.*?m sprawa wygląda inaczej. Mechanizm, po dopasowaniu litery m zaczyna dopsowywać fragment m wzorca, bo przecież * oznacza zero lub więcej znaków. Dodając ? rozleniwiliśmy asterisk, przez co ten, dopasowawszy zero dowolnych znaków, kończy swoją pracę. Mechanizmowi, oczywiście, nie uda się dopasować wzorca m; gwiazdka znowu będzie musiała zacząć pracę, dopasowując jeden znak. Dopasowany wzorzec w tym momencie to m , czyli ostatnia litera słowa Lorem i następująca po nim spacja. Mechanizm znowu próbuje dopasować m, znowu mu się nie udaje i znowu gwiazdka z kropką dopasowują kolejny znak. Dzieje się tak aż do dopasowania m ipsu; mechanizm chce teraz dopasować m do kolejne znaku w tekście i tym razem mu się to uda, osiagając ostateczną formę dopasowanego tekstu m ipsum.

Tuszę, że powyższe przykłady pozwalają lepiej zrozumieć mechanizm dopasowywania wzorców. Jeśli nie rozumiesz czegoś do końca, to przeczytaj tekst ponownie, gdyż rzeczy omawiane w tym rozdziale są naprawdę ważne.

• ← Powtórzenia
• Pozycje →