(Non)Greedy Quantification

Znaki * oraz + to tak zwane kwantyfikatory, oznaczają ilość wystąpień. Dla przypomnienia C* oznacza dowolną ilość znaków C, również 0 znaków C, zaś C+ to 1 lub więcej wystąpień C. Dla przypomnienia + to kwantyfikator wprowadzony w ERE, zaś * to "uniwersalny" kwantyfikator, występuję zarówno w BRE jak i ERE.

Bywa, że wyszukiwanie za pomocą kwantyfikatorów nie działa tak, jak tego oczekuje programista. Przykład:

Zdanie z biografii Andy Warhola. Biografia jest zapisana w pliku plik.txt, zadaniem jest zamiana <autor1> oraz <autor2> na Andy Warhol. Pozornie wydaje się to proste, wystarczy wykonać polecenie:

• sed -n -e 's/<.*>/Andy Warchol/gp' plik.txt

jednak po wykonaniu tego polecenia otrzymamy:

a nie o to chodziło, przecież!

Dzieje się tak ponieważ kwantyfikator * jest zachłanny. Stara się znaleźć jak najdłuższe dopasowanie. W tym przypadku jest to dopasowanie od pierwszego znaku < do ostatniego znaku >. Aby poprawie wykonać zadanie wystarczy nieco zmodyfikować polecenie:

• sed -n -e 's/<[^>]*>/Andy Warchol/gp' plik.txt

[^<]* oznacza dowolną ilość wystąpień każdego znaku z wyłączeniem znaku <.

UWAGA: Standardowe kwantyfikatory POSIX (* oraz +) są zachłanne.

NON-GREEDY QUANTIFICATION

Powyższe problemy spowodowały wprowadzenie tzn. niezachłannych kwantyfikatorów (non-greedy quantyfication). Niezachłanne (non-greedy) kwantyfikatory są oznaczone bardzo podobnie do ich zachłannych (greedy) odpowiedników.

sed nie wspiera niezachłannych kwantyfikatorów. Aby pokazać ich działanie skorzystamy z perl. Najpierw sprawdźmy jak działa w perl zachłanna *. Po wykonaniu polecenia:

• perl -p -e 's/<.*>/Andy Warchol/gp' plik.txt

otrzmamy wynik analogiczny do pierwszego z powyższych wywołań sed.

Natomiast gdy zmodyfikujemy * poprzez ?, czyli uczynimy * niezachłanną, to w efekcie wywołania

• perl -n -e 's/<.*?>/Andy Warchol/gp' plik.txt

otrzymujemy