<.+> dla <b>bold</b> and <i>italic</i> nie znajduje <b>. Znajduje cały ciąg, od pierwszego < do samego ostatniego >. Nic nie jest zepsute. To właśnie ma robić zachłanny (greedy) kwantyfikator, i to jest też najczęstszy błąd typu “regex matchuje zbyt dużo”. Gdy już wiesz, co silnik robi podczas czytania wzorca, ten błąd i większość jego krewnych przestają być zagadką.

Jak silnik regex czyta twój wzorzec

Silnik regex nie porównuje wzorca z ciągiem tak, jak porównuje się dwa ciągi pod kątem równości. Silniki, które używasz codziennie (re w Pythonie, RegExp w JavaScript, PCRE, .NET, Java) są regex-directed: przechodzą przez wzorzec od lewej do prawej, token po tokenie, i dla każdego tokenu próbują skonsumować znaki z ciągu w aktualnej pozycji. Gdy token się dopasuje, silnik przesuwa wskaźnik wzorca i wskaźnik ciągu. Gdy token zawodzi, silnik robi backtracking: wraca do ostatniego miejsca, w którym miał wybór, na przykład kwantyfikator, który mógł dopasować mniej znaków, albo gałąź alternatywy, której jeszcze nie spróbował, i wybiera drugą opcję.

Dlatego <.+> zjada całą linię. .+ jest zachłanny, więc najpierw bierze wszystkie pozostałe znaki ciągu, łącznie z < i >. Silnik wciąż potrzebuje dosłownego >, żeby zakończyć, więc oddaje znaki jeden po drugim od końca, aż ostatni > w ciągu go zadowoli. Silnik zwraca pierwsze dopasowanie, które znajdzie w takiej kolejności najpierw-zachłannie. Dla tego wzorca to najdłuższe możliwe dopasowanie, nie to, które wygląda poprawnie na pierwszy rzut oka.

Najpierw spróbuj opcji zachłannej, a po niepowodzeniu wycofaj się o jeden krok: ta jedna zasada wyjaśnia zarówno zwyczajne codzienne dopasowywanie, jak i patologiczne zwolnienia opisane dalej. To ta sama dynamika eksploracji i wycofywania, co w wyszukiwaniu rekurencyjnym bez memoizacji, ten typ eksplozji, który wyjaśnienie rekurencji opisuje z perspektywy wywołań funkcji.

Podstawowa składnia regex: kotwice, kwantyfikatory, grupy, lookaroundy

Kotwice i klasy znaków

^ i $ kotwiczą dopasowanie do początku i końca ciągu (lub linii, z flagą multiline). \d, \w i \s to skróty klas znaków dla cyfry, znaku słowa i białego znaku, a [...] pozwala zapisać klasę bezpośrednio.

1
2
3
4

import re

re.search(r"^\d{3}-\d{4}$", "555-0199")
# <re.Match object; span=(0, 8), match='555-0199'>

Bez kotwic \d{3}-\d{4} dopasowałoby się też wewnątrz "call 555-0199 now". Kotwice zmieniają “zawiera” w “jest dokładnie”.

Klasy znaków operują na tym, co silnik uważa za jeden znak, a poza czystym ASCII to nie zawsze jest to, czego się oczekuje. \w dopasowuje literę, cyfrę lub podkreślenie według pojęcia znaku używanego przez silnik, czyli tego samego rozróżnienia code point kontra bajt, które opisuje co to jest Unicode i jak działa kodowanie UTF-8. Uruchom wzorzec na surowych bajtach UTF-8 zamiast na zdekodowanym tekście, i wielobajtowy znak zostanie podzielony na to, co silnik uważa za osobne znaki.

Kwantyfikatory zachłanne i leniwe

+, * i {m,n} są domyślnie zachłanne: biorą tyle, ile mogą, a potem wycofują się, jeśli to psuje resztę wzorca. Postaw ? po którymkolwiek z nich i kwantyfikator staje się leniwy. Bierze jak najmniej i rozszerza się tylko, gdy musi.

1
2
3

s = "<b>bold</b> and <i>italic</i>"
re.findall(r"<.+>", s)    # ['<b>bold</b> and <i>italic</i>']
re.findall(r"<.+?>", s)   # ['<b>', '</b>', '<i>', '</i>']

Jeden znak różnicy, zupełnie inny wynik. Gdy chcesz najkrótszej rzeczy, która spełnia resztę wzorca, użyj formy leniwej. Jeśli dopasowujesz znaczniki, przeczytaj najpierw ostatnią sekcję.

Grupy przechwytujące, nieprzechwytujące i nazwane

(...) przechwytuje to, co dopasuje, żebyś mógł to później wydobyć. (?:...) grupuje dla struktury, na przykład żeby zastosować kwantyfikator do całego podwzorca, bez tworzenia przechwycenia. (?P<name>...) w Pythonie ((?<name>...) w JavaScript, Java i .NET) nazywa grupę, żebyś nie musiał liczyć nawiasów, by ją później znaleźć.

1
2
3

m = re.match(r"(?P<year>\d{4})-(?P<month>\d{2})-(?P<day>\d{2})", "2026-10-28")
m.groupdict()
# {'year': '2026', 'month': '10', 'day': '28'}

1
2
3

const m = "2026-10-28".match(/(?<year>\d{4})-(?<month>\d{2})-(?<day>\d{2})/);
m.groups;
// [Object: null prototype] { year: '2026', month: '10', day: '28' }

Wynik odczytujesz po nazwie, przez groupdict() w Pythonie lub .groups w JavaScript (nazwane grupy trafiły tam w ES2018), a nie przez match[1], match[2]. Gdy wzorzec ma więcej niż dwie grupy, te dodatkowe znaki się opłacają.

Lookahead i lookbehind

Lookaround sprawdza pozycję, nie znaki. Sprawdza, czy coś jest (lub nie jest) obecne, bez konsumowania tego. (?=...) to lookahead pozytywny, (?!...) negatywny; (?<=...) i (?<!...) to odpowiedniki lookbehind.

1
2

"$40 bill".match(/(?<=\$)\d+/);
// [ '40', index: 1, ... ]   -- znajduje "40", nie "$40"

Pythonowe re wymaga, żeby lookbehind miał ustaloną szerokość: (?<=\$) działa, (?<=\$+) wywołuje błąd, bo silnik musi wiedzieć dokładnie, o ile się wycofać, przed sprawdzeniem. JavaScript, który dodał lookbehind w ES2018 razem z nazwanymi grupami, nie ma tego ograniczenia, więc (?<=\$+) tam działa. W Pythonie zewnętrzny pakiet regex z PyPI usuwa to ograniczenie, jeśli potrzebujesz lookbehind o zmiennej szerokości.

Czemu niektóre regexy się zawieszają: catastrophic backtracking

Weź zasadę backtrackingu z początku i daj jej przypadek, z którego nie może się wyratować. Zagnieźdź dwa kwantyfikatory tak, żeby silnik miał wiele sposobów podziału tej samej sekwencji znaków między nimi, a potem spraw, żeby dopasowanie zawiodło na samym końcu. Silnik nie zawodzi szybko. Próbuje każdego podziału, zanim się podda.

1
2
3
4
5
6
7
8

import re, time

pattern = re.compile(r"(a+)+b")
for n in (20, 24, 26, 28):
    s = "a" * n  # bez końcowego "b", więc nigdy się nie dopasowuje
    start = time.perf_counter()
    pattern.match(s)
    print(n, f"{(time.perf_counter() - start) * 1000:.1f} ms")

1
2
3
4

20 41.6 ms
24 525.8 ms
26 2083.6 ms
28 8369.3 ms

Każde dodatkowe a z grubsza podwaja czas: dwa znaki więcej, cztery razy dłużej. To jest wzrost wykładniczy, krzywa, którą notacja Big O stawia po drugiej stronie O(n^2). (a+)+ może podzielić sekwencję 28 a na grupy w 2^27 różnych sposobów, i bez b w ciągu silnik próbuje ich jeden po drugim, zanim może zgłosić “brak dopasowania”. Prowadź tę samą krzywą do 40 znaków i czekasz około dziewięciu godzin.

Gdy dane wejściowe pochodzą od użytkownika, a nie z twoich fixtures testowych, to jest podatność do wykorzystania: ReDoS, regular expression denial of service. Typowym wyzwalaczem jest właśnie ten kształt, dwa kwantyfikatory nałożone na siebie, bez niczego pomiędzy, co wymuszałoby unikalny podział.

Trzy sposoby, żeby to zatrzymać, od najtańszego:

  1. Usuń niejednoznaczność. (a+)+b i a+b dopasowują tutaj te same prawidłowe ciągi; zewnętrzny + nic nie daje. Większość katastrofalnych wzorców ma taką nadmiarową warstwę, gdy się jej poszuka.

  2. Zrób wewnętrzny kwantyfikator posesywnym albo zawrzyj go w grupie atomowej. Oba mówią silnikowi “jak to się dopasuje, nie wracaj się już do środka”. To eliminuje wykładniczą eksplozję, kosztem okazjonalnego odrzucenia ciągu, który wersja z backtrackingiem by zaakceptowała. Pythonowe re wspiera obie formy od wersji 3.11:

    1
2
3
4
5
6
7

    pattern = re.compile(r"(?>a+)+b")   # grupa atomowa
# albo: re.compile(r"a++b")         # kwantyfikator posesywny, Python 3.11+
for n in (28, 1_000, 100_000):
    s = "a" * n
    start = time.perf_counter()
    pattern.match(s)
    print(n, f"{(time.perf_counter() - start) * 1000:.3f} ms")

    1
2
3

    28 0.002 ms
1000 0.001 ms
100000 0.026 ms

    To samo nieudane dopasowanie na 100 000 znaków zajmuje 26 mikrosekund. Natywny RegExp w JavaScript nie ma żadnej z tych dwóch funkcji. Pakiet npm regex dodaje grupy atomowe i kwantyfikatory posesywne jako rozszerzoną składnię, jeśli potrzebujesz ich bez zmiany silnika.

  3. Ogranicz nieograniczone kwantyfikatory. {1,50} zamiast + ogranicza, jak źle może wyglądać najgorszy przypadek, nawet bez przepisywania logiki.

Jeśli ciąg może pochodzić z zewnątrz twojego kodu, na przykład z treści żądania albo wartości konfiguracyjnej napisanej przez kogoś innego, traktuj zagnieżdżone kwantyfikatory tak, jak traktowałbyś nieograniczoną pętlę po danych zewnętrznych. Testuj wzorzec na długiej sekwencji znaku, który wywołuje niejednoznaczność, a nie tylko na fixtures z happy path.

Kiedy nie używać regex

Regex nie ma pamięci o tym, jak głęboko jest. To jest w porządku dla płaskiego tekstu o ustalonej formie, jak data albo linia logu ze znanymi polami. To też powód, dla którego <.+> nie może wiarygodnie przeskoczyć jednego znacznika HTML: nie ma pojęcia “ten < otwiera znacznik, który zamyka następny odpowiadający mu >”, tylko “bierz do ostatniego >, jaki znajdziesz”. Zagnieżdżone struktury, takie jak HTML, JSON, kod źródłowy i zbalansowane nawiasy, potrzebują gramatyki, nie wzorca. Typowym niepowodzeniem jest regex, który przechodzi każdy napisany przez ciebie test, a potem trafia na prawdziwy plik z komentarzem zawierającym > i po cichu dopasowuje źle fragment, zamiast zgłosić błąd.

Użyj parsera, który już istnieje: parsera HTML dla HTML, json.loads dla JSON, modułu AST twojego języka dla kodu. Zachowaj regex do walidacji albo wydobywania tekstu o płaskiej formie, i przejdź na parser w momencie, gdy “zbalansowany” albo “zagnieżdżony” pojawi się w opisie tego, co dopasowujesz.

Powiązane artykuły