RegExp – kwantyfikatory zachłanne i niezachłanne

Dzisiaj przyjrzymy się bliżej kwantyfikatorom wyrażeń regularnych obsługiwanych w JavaScript (a dokładniej w standardzie ECMAScript). Omówimy także różnicę między kwantyfikatorami zachłannymi (chciwymi) i niezachłannymi.

Na początek przypomnimy sobie podstawowe rodzaje kwantyfikatorów obsługiwanych przez silnik wyrażeń regularnych ECMAScript. Generalnie kwantyfikatory oznaczają określoną ilość wystąpienia danego wzorca i oznacza się je przy użyciu nawiasów klamrowych {min, max}.

Wewnątrz nawiasów podajemy minimalną i maksymalną dopuszczalną liczbę wystąpień danego wzorca, który znajduje się tuż przed kwantyfikatorem. Aby lepiej to zrozumieć spójrzmy na poniższy przykład:

/^a{1,7}$/.test('aaaaa'); //true
/^a{1,5}$/.test('aaaaa'); //true
/^a{1,3}$/.test('aaaaa'); //false

/^a{5,1}$/.test('aaaaa') ;//StyntaxError

Pierwsze dwa trzy wywołania określają minimalną ilość wystąpienia litery a (jeden, czyli co najmniej raz litera „a” musi znaleźć się w ciągu znakowym) oraz maksymalną ilość równą 7, 5 oraz 3. Jak widać dwa pierwsze dopasowania mieszczą się w podanym zakresie więc metoda test zwraca true. Trzecie wywołanie określa górną granicę na maksymalnie trzykrotne wystąpienie litery a, więc otrzymujemy wartość false.

Zwróć jednak uwagę, że w każdym z przykładów stosujemy granicę początku i końca ciągu znakowego. Gdybyśmy tego nie zrobili to trzecie wywołanie zwróciłoby wynik true, gdyż dopasowałoby w ciągu sekwencję składającą się z kolejno występujących po sobie liter „a”. Do tego zagadnienia powrócimy za chwilę omawiając kwantyfikatory zachłanne i niezachłanne.

Kolejne wywołanie a{5,1} zgłasza błąd SyntaxError. Nie zostanie wykonana automatyczna zamiana parametrów min i max co uważam, że jest dobrym rozwiązaniem gdyż wymusza bardziej uważne i przemyślane tworzenie wzorców dopasowań.

/^a{3}$/.test('aaaaa'); //false
/^a{5}$/.test('aaaaa'); //true

/^a{3,}$/.test('aaaaa'); //true
/^a{6,}$/.test('aaaaa'); //false

Wartość minimalna powinna być podana zawsze. Jeśli w nawiasach klamrowych podamy tylko jedną wartość to będzie to oznaczało kwantyfikator precyzyjny, czyli dopasowujący dokładnie 3 lub 5 wystąpień litery „a”.  W przypadku pominięcia drugiej wartości, ale z pozostawieniem znaku przecinka stworzymy kwantyfikator bez górnej granicy liczby dopasowań lecz z ilością minimalną.

Nie należy nigdy stosować zapisów pomijających wartość minimalną, czyli {,5}. Co prawda niektóre środowiska JavaScript obsłużą to poprawnie lecz w innych możemy uzyskać dopasowanie zupełnie inne od oczekiwanego. Kwantyfikatory nie mogą przyjmować wartości ujemnych (co jest chyba oczywiste) więc gdy chcemy pominąć dolną granicę to zalecam zapis {0,max}. W takiej sytuacji zawsze uzyskamy oczekiwany rezultat niezależnie od środowiska w jakim uruchomimy nasz skrypt.

Kwantyfikatory w zapisie skróconym

Podane wcześniej kwantyfikatory były stworzone w tzw. zapisie ogólnym. W czasie pisania wzorców RegExp najczęściej stosuje się kwantyfikatory w formie skróconej, a zapis pełny pozostawia się dla konkretnych przypadków nie objętych zapisem skróconym. Osobiście również preferuję takie podejście do stosowania kwantyfikatorów.

W standardzie ECMAScript mamy do dyspozycji trzy kwantyfikatory jedno znakowe w postaci znaku zapytania (?), gwiazdki (*) oraz znaku plusa (+). Oznaczają one odpowiednio:

  • znak „?”: jedno lub brak wystąpień, równoważny zapisowi {0,1}
  • znak ‚*”: zero lub dowolnie dużo dopasowań, czyli równoważny zapisowy {0,}
  • znak „+”: co najmniej jedno dopasowanie, czyli równoważny zapisowy {1,}.

Stosujemy je tak samo jak kwantyfikatory w zapisie ogólnym i odnoszą się one do elementu znajdującego się tuż przed kwantyfikatorem.

/[a-z]+/.test('123'); //false
/[a-z]*/.test('123'); //true
/[0-9]+/.test('123'); //true
/[a-z]?/.test('123'); //true

Kwantyfikatory zachłanne i niezachłanne

Skoro wiemy już czym są i jak działają podstawowe kwantyfikatory w JavaScript to przyszedł czas, żeby nieco skomplikować całą zabawę z wyrażeniami regularnymi. W niektórych książkach i poradnikach można znaleźć informację, że kwantyfikatory w JavaScript domyślnie są „zachłanne”, lecz niestety niewiele poradników odpowiednio dokładnie wyjaśnia co to właściwie znaczy.

Otóż podstawowa różnica między nimi polega na tym, że kwantyfikator zachłanny szuka w ciągu miejsca, które spełnia początek dopasowania, a następnie podąża od górnej granicy kwantyfikatora do dolnej. Brzmi to zapewne nieco skomplikowanie, dlatego najlepiej od razu przejdźmy do przykładu. Tym razem również posłużymy się jakże rozbudowanym ciągiem znakowym „aaaaa….” z użyciem metody match, która zwróci nam wszystkie znalezione dopasowania podanego wzorca.

'aaaaa'.match(/a{1,2}/g); //['aa','aa','a']
'aaaaa'.match(/a{1,2}?/g); //['a','a','a','a','a']

'aaaaa'.match(/a{2,4}/g); //['aaaa']
'aaaa'.match(/a{2,4}?/g); //['aa','aa']

'aaaaa'.match(/a+/g); //['aaaaa']
'aaaaa'.match(/a+?/g); //['a','a','a','a','a']

W pierwszych dwóch przypadkach poszukujemy w ciągu co najmniej jednego i nie więcej niż dwóch wystąpień litery „a”. W przypadku zapisu {….} domyślnie jest stosowany kwantyfikatory typu zachłannego. Oznacza to, że za każdym razem gdy napotka co najmniej jedno wystąpienie litery „a” (czyli spełnia zakres „min”) to próbuje od razu „zagarnąć” maksymalny zakres dopasowania, czyli aż do wartości „max” (u nas „2”). Z tego względu dwa razy mu się to udaje i zwraca elementy „aa”, natomiast po dojściu do końca ciągu zwraca dopasowanie tylko jednej litery „a” gdyż spełnia to warunek „min” (i jednocześnie „max”).

Kwantyfikator niezachłanny (zapisywany z dodatkowym znakiem zapytania po nawiasach klamrowych) próbuje zawsze dopasować jak najmniejszą ilość znaków, czyli dla niego granicą końcową dopasowania jest spełnienie wymagania „min”. Z tego względu metoda match zwraca tablicę z pojedynczymi literami „a”.

Kolejne dwa wywołania metody match wyszukują sekwencji co najmniej dwóch i maksymalnie czterech wystąpień litery „a”. Kwantyfikator zachłanny (domyślny) dopasowuje „ile tylko się da” i zwraca tablicę z jednym elementem „aaaa”. Ostatnia litera „a” nie spełnia warunki minimum dwukrotnego wystąpienia, więc nie zostanie ujęta w wynikach.

Użycie kwantyfikatora niezachłannego powoduje zatrzymanie się za każdym razem, gdy znajdziemy minimalną ilość wystąpień litery „a” (u nas „2”) dlatego zwróci tablicę z dwoma elementami „aa”.

Jeśli uważnie czytałeś omówienie pierwszych czterech wywołań metody match i wcześniejsze akapity artykułu to powinieneś poradzić sobie z rozszyfrowaniem dlaczego ostatnie dwa wywołania metody match dały takie, a nie inne wyniki.

Uwaga na kwantyfikatory dowolnej liczby wystąpień!

W przypadku stosowania minimalnej ilości dopasowania wzorca umieszczonego przed kwantyfikatorem większej od zera to w miarę łatwo można przewidzieć wyniki zwracane przez metodę match.

Zanim jednak zaczniesz stosować kwantyfikatory niezachłanne spójrz proszę na poniższe przykłady, które osobom dopiero uczącym się wyrażeń regularnych wprowadzają nieco zamieszania:

'aaaaa'.length; //5 - za chwilę przy nam się ta informacja

'aaaaa'.match(/a+/g); //['aaaaa']
'aaaaa'.match(/a+?/g); //['a','a','a','a','a'] - 5 elementów

'aaaaa'.match(/a*/g); //['aaaaa',''] - dodatkowy pusty element!
'aaaaa'.match(/a*?/g) //['','','','','',''] - 6 pustych elementów!

'aaaaa'.match(/(aa)*/g); //['aaaa','',''] - dwa puste elementy!
'aaaaa'.match(/(aa)*?/g); //['','','','','',''] - 6 pustych elementów!

//a teraz dodajmy granice przeszukania "^" i "$"
'aaaaa'.match(/^a*$/g); //['aaaaa'] - 5 elementów
'aaaaa'.match(/^a*?$/g); //['aaaaa'] - 5 elementów

Wygląda ciekawie prawda? Spróbujmy przeanalizować dlaczego uzyskaliśmy takie właśnie wyniki.

Otóż dopasowywanie wzorca wyrażeń regularnych w metodzie match działa w taki sposób, że po skutecznym dopasowaniu wynik zostaje zapisany w tablicy i następuje dalsza analiza ciągu skróconego o wcześniejsze dopasowania (jest to dość duże uproszczenie, ale do naszej analizy wystarczy).

Gdy poszukiwaliśmy co najmniej jednego dopasowania litery „a” to gdy metoda match dopasowała ostatni znak naszego ciągu (który składa się wyłącznie z liter „a”) kończy swoją pracę gdyż nie ma już nic więcej, co spełniałoby co najmniej jednokrotne dopasowanie.

Co jednak gdy zastosowaliśmy kwantyfikator gwiazdki (*). Oznacza on dowolną liczbę wystąpień dopasowania, czyli również zerową (czyli brak możliwości dopasowania). W naszym wypadku kwantyfikator a* dopasował skutecznie wszystkie litery „a”, czyli maksymalną możliwą ilość wyciągniętą a naszego ciągu. Skąd jednak wziął się dodatkowy pusty element w tablicy wynikowej?

Otóż stąd, że po zapisaniu w tablicy elementu ‚aaaaa’ metoda match ponownie próbowała dopasować podany wzorzec do ciągu skróconego o poprzednie dopasowanie – czyli de facto do pustego ciągu znakowego. Dokładnie to samo stało się przy użyciu kwantyfikatora „+”, ale tym razem pusty ciąg spełnia wymagania co najmniej zerowej ilości litery „a”, dlatego został on zapisany w tablicy. Dalej nie ma już czego „odciąć” od naszego ciągu, a więc metoda match kończy działanie.

Na podobnej zasadzie należałoby wyjaśnić dlaczego przy zastosowaniu kwantyfikatora niezachłannego uzyskano sześć, a nie pięć pustych elementów. Nie dopasowano żadnej litery „a” gdyż możliwe było dopasowanie ilości minimalnej, czyli zerowej – a kwantyfikator niezachłanny zawsze dąży do dopasowań minimalnych.

Kwantyfikatory niezachłanne w zastosowaniach praktycznych

Na koniec spróbujemy stworzyć nieco bardziej praktyczny przykład niż z wykorzystaniem jakże kreatywnego ciągu ‚aaaaa’.

Załóżmy, że naszym zadaniem jest stworzenie wyrażenia regularnego, które w połączeniu z metodą replace (String.prototype.replace) umożliwi usunięcie wszystkich znaczników html z podanego ciągu znakowego (np. pozyskanego jako innerHTML).

var reg = /<.*>/g;
'<div>test'.replace(reg,''); //'test'
'<p>test</p>'.replace(reg,''); //'' ups...

var reg = /<.*?>/g;
'<div>test'.replace(reg,''); //'test'
'<p>test</p>'.replace(reg,''); //'test' - teraz ok!

Pierwsze wyrażenie regularne z kwantyfikatorem zachłannym (domyślnym w JavaScript) po dopasowaniu pierwszego znaku „<” od razu poszukuje ostatniego takiego znaku w ciągu. W drugim wypadku znajduje go jako ostatni znak ciągu „<p>test</p>” dlatego cały ciąg traktuje jako prawidłowe dopasowanie i w metodzie replace zamienia to na pusty ciąg znakowy.

Z kolei drugie wyrażenie używające kwantyfikatora niezachłannego dokona w naszym przykładzie dwukrotnego dopasowania z zamianą na pusty ciąg znakowy:

  • dopasowanie 1: „<p>” i zamiana na „”,
  • zignorowanie ciągu między „>”, a kolejnym „<„, czyli napisu „test”,
  • dopasowanie 2: „</p>” i zamiana na „”.

Wiele osób praktycznie nigdy nie korzysta z kwantyfikatorów niezachłannych, podobnie jak z tzw. dopasowań wyprzedzających (zapisywanych jako ?! lub ?=). jednakże jeśli dobrze zrozumie się zasadę ich działania to w niektórych sytuacjach pozwalają stworzyć skuteczne wyrażenie regularne zastępujące bardziej rozbudowane własne funkcje.

Oddzielną sprawą jest kwestia wydajności, ale nie przesadzajmy z tym na każdym kroku. Jeśli na przykład walidujemy pojedyncze wartości z pól formularza to jakie praktyczne znaczenie ma fakt czy operacja wykona się o te kilkadziesiąt czy kilkaset milisekund dłużej czy krócej?