Wyrażenia regularne (regex) w Java: operatory zachłanne (greedy) vs. leniwe (lazy, reluctant)

O wyrażeniach regularnych pisać można wiele, a niewiele osób chce o tym czytać, gdyż każdy albo umie albo myśli, że umie tyle ile mu potrzeba.

Jest jednak kilka ciekawych faktów związanych z wyrażeniami regularnymi (nie koniecznie tylko w Javie), o których nie każdy wie, a powinien – taką właśnie kwestią jest podział na operatory zachłanne i leniwe.

Weźmy przykładowy, bardzo prosty string:

  • 1234567890

Do tego weźmy stosunkowo proste wyrażenie regularne:

  • (\d*)(\d*)

Powyższe wyrażenie działa dość prosto – w pierwszej grupie zwraca dowolną (0-N) liczbę cyfr, a w drugiej grupie (również) dowolną liczbę cyfr. Teraz pytanie – w jakiej grupie będą jaki cyfry, skoro dowolny podział spełniałby założenia podanego wyrażenia regularnego?

Powyższe operatory powtórzenia dowolnego (*) działają zgodnie z 3 podstawowymi zasadami dla operatorów (w Javie, ale nie tylko):

  • operatory są uwzględniane od lewej do prawej strony
  • operatory są zachłanne – zabierają tyle znaków ile tylko mogą
  • operatory nie mogą zabrać ponad minimum żadnego znaku, jeżeli powstrzymałoby to pozostały fragment wyrażenia przed spełnieniem

Posługując się powyższymi 3 zasadami, możemy odpowiedzieć na pytanie:

  • 1. grupa: 1234567890
  • 2. grupa:

Tak właśnie wygląda zachłanność operatora. Pierwszy operator zawłaszczył wszystkie znaki. Nie powstrzymał przy tym reszty wyrażenia przed spełnieniem, gdyż drugi w kolejności operator to *(0-N), a nie np. +(1-N).

Możemy jednak wymusić, aby operator nie zachowywał się zachłannie, poprzez dodanie znaku ? do operatora.

  • (\d*?)(\d*)

Teraz wynik jest odmienny:

  • 2. grupa:
  • 1. grupa: 1234567890

Pierwszemu operatorowi nie będącemu już zachłannym (a leniwym) wystarczyło minimum znaków, jakie go spełniają – w tym przypadku żadem znak. Równocześnie dla drugiego operatora pozostały wszystkie kolejne znaki.