Wyrażenie regularne

Wyrażenie regularne (ang. regular expression, w skrócie regex lub regexp) – wzorzec opisujący łańcuch symboli. Teoria wyrażeń regularnych jest związana z teorią języków regularnych. Wyrażenia regularne mogą określać zbiór pasujących łańcuchów, jak również wyszczególniać istotne części łańcucha.

W informatyce teoretycznej wyrażenia regularne są ciągami znaków pozwalającymi opisywać języki regularne. W praktyce znalazły bardzo szerokie zastosowanie, pozwalają bowiem w łatwy sposób opisywać wzorce tekstu, natomiast istniejące algorytmy w efektywny sposób określają, czy podany ciąg znaków pasuje do wzorca lub wyszukują w tekście wystąpienia wzorca. Wyrażenia regularne w praktycznych zastosowaniach są zapisywane za pomocą bogatszej i łatwiejszej w użyciu składni niż ta stosowana w rozważaniach teoretycznych. Co więcej, opisane niżej powszechnie wykorzystywane wsteczne referencje (czyli użycie wcześniej dopasowanego fragmentu tekstu jako części wzorca), powodują, że wyrażenie regularne je zawierające może nie definiować języka regularnego.

Wyrażenia regularne stanowią integralną część narzędzi systemowych takich jak sed, grep, wielu edytorów tekstu, języków programowania przetwarzających tekst AWK i Perl, a także są dostępne jako odrębne biblioteki dla wszystkich języków używanych obecnie.

Dwie najpopularniejsze składnie wyrażeń regularnych to składnia uniksowa i składnia perlowa. Składnia perlowa jest znacznie bardziej rozbudowana. Jest ona używana nie tylko w języku Perl, ale także w innych językach programowania: Ruby, bibliotece PCRE do C i w narzędziu powłoki o nazwie pcregrep (znanym też jako pgrep). Perlową składnię stosuje się również w maskach przepisań mod rewrite.

Historia

Pojęcie wyrażeń regularnych wprowadził w 1951 roku amerykański matematyk Stephen Cole Kleene, który opisał języki regularne za pomocą notacji nazwanej „zdarzeniami regularnymi” (regular events); notacja powstała przy próbie matematycznego opisu wczesnych modeli sieci neuronowych McCullocha i Pittsa.

Do praktyki programistycznej wyrażenia regularne trafiły w 1968 roku za sprawą Kena Thompsona, który wbudował notację Kleene’ego w edytor tekstu QED jako mechanizm wyszukiwania wzorców; w opublikowanym wówczas artykule opisał także sposób przekształcania wyrażenia w niedeterministyczny automat skończony, znany dziś jako konstrukcja Thompsona, a jego implementacja dla szybkości kompilowała wyrażenia bezpośrednio do kodu maszynowego komputera IBM 7094, co uchodzi za wczesny przykład kompilacji JIT. Mechanizm ten Thompson przeniósł następnie do uniksowego edytora ed, z którego wywodzi się narzędzie grep – jego nazwa pochodzi od polecenia edytora g/re/p (global/regular expression/print). W latach 70. w Bell Labs powstały kolejne korzystające z wyrażeń regularnych narzędzia, m.in. sed, AWK, generator analizatorów leksykalnych lex oraz edytor vi.

Składnię narzędzi uniksowych ujednolicono w 1992 roku w standardzie POSIX, który definiuje podstawowe (BRE) i rozszerzone (ERE) wyrażenia regularne oraz klasy znaków takie jak [:digit:]. Równolegle rozwinęła się znacznie bogatsza linia perlowa: Perl pod koniec lat 80. przejął i rozbudował bibliotekę Henry’ego Spencera, a w 1997 roku Philip Hazel opracował zgodną z Perlem bibliotekę PCRE, wykorzystywaną m.in. przez PHP i serwer Apache. Wyrażenia regularne weszły także do składni języka ECMAScript (JavaScript) i bibliotek standardowych większości współczesnych języków programowania, m.in. Javy i Pythona. W 2010 roku Google opublikowało otwartą bibliotekę RE2, gwarantującą liniowy czas dopasowania kosztem rezygnacji z referencji wstecznych.

Wyrażenie regularne w informatyce teoretycznej

Definicja wyrażeń regularnych

Wyrażeniem regularnym nad alfabetem $\Sigma$ nazywamy ciąg znaków składający się z symboli $\varnothing ,\ \epsilon ,\ +,\ {\text{*}},\ ),\ ($ oraz symboli $a_{i}$ z alfabetu $\Sigma$ następującej postaci:

1. $\varnothing ,\epsilon$ (słowo puste) są wyrażeniami regularnymi;
2. wszystkie symbole $a_{i}\in \Sigma$ są wyrażeniami regularnymi;
3. jeśli $e_{1},e_{2}$ są wyrażeniami regularnymi, to są nimi również:
   • $e_{1}^{*}$ (domknięcie Kleene’ego)
   • $e_{1}e_{2}$ (konkatenacja)
   • $e_{1}+e_{2}$ (suma)
   • $(e_{1})$ (grupowanie)
4. wszystkie wyrażenia regularne są postaci opisanej w punktach 1–3.

Każde wyrażenie regularne definiuje pewien język formalny. Każdy język definiowany przez wyrażenie regularne jest regularny.

Definicja języka określanego przez wyrażenie regularne

Język definiowany przez wyrażenie regularne jest definiowany indukcyjnie. Niech L(w) oznacza język definiowany przez w. Wtedy baza indukcji jest następująca:

• $L(\epsilon )=\{\epsilon \}$ (zbiór zawierający tylko słowo puste)
• $L(\varnothing )=\varnothing$ (zbiór pusty)
• $L(a)=\{a\}$ dla dowolnego $a$ z alfabetu

Natomiast do konstrukcji wyrażeń służą 3 symbole:

• $L(w+v)=L(w)\cup L(v)$ (suma języków)
• $L(w^{*})=(L(w))^{*}$ (domknięcie Kleene’ego)
• $L(wv)=\{xy:x\in L(w)\wedge y\in L(v)\}$ (konkatenacja języków)

Gwiazdka wiąże najsilniej, konkatenacja słabiej, suma najsłabiej.

Własności wyrażeń regularnych

Wyrażenia są równoważne gdy definiują ten sam język: $e_{1}=e_{2}\iff L(e_{1})=L(e_{2})$

• $e+e=e$
• $e_{1}+e_{2}=e_{2}+e_{1}$ – suma jest przemienna
• $\epsilon e=e\epsilon =e$ – łańcuch pusty jest elementem neutralnym konkatenacji
• $(e_{1}+e_{2})+e_{3}=e_{1}+(e_{2}+e_{3})$ – suma jest łączna
• $(e_{1}e_{2})e_{3}=e_{1}(e_{2}e_{3})$ – konkatenacja również jest łączna
• $(e_{1}+e_{2})X=e_{1}X+e_{2}X$ – konkatenacja jest rozdzielna względem sumy
• $X(e_{1}+e_{2})=Xe_{1}+Xe_{2}$
• $e^{*}e=ee^{*}$
• $(e^{*})^{*}=e^{*}$ – domknięcie Kleene’ego jest idempotentne
• $e^{*}e^{*}=e^{*}$

Przykład 1

Wyjaśnienie reguł:

• $e_{1}^{*}$ – dowolny ciąg składający się z $e_{1},$ np. $e_{1}e_{1},$ $e_{1}e_{1}e_{1}e_{1},$ a także pusty
• $e_{1}e_{2}$ – sekwencja, najpierw $e_{1},$ następnie $e_{2}$
• $e_{1}+e_{2}$ – alternatywa, albo $e_{1},$ albo $e_{2}$

Przykład 2

Wyrażenie $(W+w)iki$ definiuje język zawierający dokładnie dwa słowa: „Wiki” i „wiki”. To samo można wyrazić wprost $Wiki+wiki.$

Przykład 3

Wyrażenie $(a+b)^{*}baba(a+b)^{*}$ definiuje język wszystkich słów nad alfabetem $\{a,b\},$ które zawierają podsłowo baba.

Wyrażenia regularne a automaty skończone

Języki regularne można opisać również za pomocą automatów skończonych:

1. niedeterministycznego automatu skończonego (NAS) z $\epsilon$-przejściami (automat może zmienić swój stan bez podania symbolu wejściowego),
2. niedeterministycznego automatu skończonego bez $\epsilon$-przejść, oraz
3. deterministycznego automatu skończonego (DAS).

Automat skończony	Wyrażenie regularne
	automat dla pustego języka, nie zawierającego żadnego słowa; $L(\varnothing )=\varnothing$
	automat dla języka akceptującego tylko słowo puste; $L(\epsilon )=\{\epsilon \}$
	automat dla języka akceptującego tylko jeden symbol; $L(a)=\{a\}$
	NAS dla konkatenacji dwóch wyrażeń regularnych: $\alpha \ \beta$
	NAS dla sumy dwóch wyrażeń regularnych: $\alpha +\beta$
	NAS dla domknięcia Kleene’ego wyrażenia regularnego: $\alpha ^{*}$

Jedne z pierwszych praktycznych implementacji wyrażeń regularnych opierały się właśnie na symulacji programowej automatu skończonego. Najpierw budowany jest NAS z $\epsilon$-przejściami zgodnie ze schematem pokazanym wyżej, następnie usuwane są $\epsilon$-przejścia, kolejnym krokiem jest determinizacja automatu skończonego, czego wynikiem jest otrzymanie DAS, ostatnim zaś etapem jego minimalizacja. Symulowanie DAS jest bardzo proste i szybkie; pierwsze narzędzia systemu Unix używały tej metody, wykorzystuje ją również język AWK, Tcl, a także biblioteki dla języka Haskell. Symulacja automatu niedeterministycznego wymaga czasu proporcjonalnego do iloczynu długości tekstu i rozmiaru wyrażenia, a po determinizacji dopasowanie przebiega w czasie liniowym względem długości tekstu, choć sam automat deterministyczny może mieć wykładniczo więcej stanów.

Wyrażenia regularne w praktyce

Porównanie składni praktycznej z teoretyczną

Na początku zostaną pokazane różnice i części wspólne zapisu teoretycznego i praktycznego.

Informatyka teoretyczna	Praktyka	Komentarz
$\varnothing ,\epsilon$	brak, ""	w praktyce zbioru pustego nie podaje się wprost, w większości języków programowania słowo puste jest oznaczane przez "" (parę cudzysłowów)
$(,\;)$	(, ) lub \(, \)	w niektórych implementacjach symbole specjalne poprzedza się backslashem
$+$	| lub \|	jw.
$0+1+2+3+a+b+c+d+e+f+g+h$	[0123abcdefgh] lub krócej [0-3a-h]	zakres znaków (dokładny opis – patrz niżej)
$a+b+\ldots +z+A+B+\ldots +Z$	.	dowolny znak z alfabetu (tutaj małe i duże litery, w praktyce cały zestaw znaków); w teoretycznym zapisie wymaga wyliczenia wszystkich znaków z alfabetu
$^{*}$	* lub \*	0 lub więcej wystąpień
$e+\epsilon$	e?	wyrażenie e występuje 0 lub 1 raz
$ee^{*}$	e+	wyrażenie e występuje 1 lub więcej razy
brak	^	metaznak oznaczający początek łańcucha (lub początek wiersza, jeśli przetwarzane są wielowierszowe napisy); w teoretycznych rozważaniach dopasowuje się całe słowa, podczas gdy w praktyce zwykle celem jest znalezienie dopasowania wewnątrz dłuższego tekstu, dlatego dopasowanie do całości wymaga dodatkowych oznaczeń w zapisie [^e] oznacza negację e
brak	$	metaznak oznaczający koniec łańcucha
$eeee$	e{4}	określona liczba powtórzeń (tutaj 4); rozszerzenie Perla
$eeee(e+\epsilon )(e+\epsilon )(e+\epsilon )$	e{4,7}	określony zakres liczby powtórzeń wyrażenia e (tutaj od 4 do 7); rozszerzenie Perla

Podstawowe elementy

Podstawowe elementy wyrażeń regularnych:

• Każdy znak, oprócz znaków specjalnych, określa sam siebie, np. a określa łańcuch złożony ze znaku a.
• Kolejne symbole oznaczają, że w łańcuchu muszą wystąpić dokładnie te symbole w dokładnie takiej samej kolejności, np. ab oznacza że łańcuch musi składać się z litery a poprzedzającej literę b.
• Kropka . oznacza dowolny znak z wyjątkiem znaku nowego wiersza (zależnie od ustawień i rodzaju wyrażeń).
• Znaki specjalne poprzedzone odwrotnym ukośnikiem \ powodują, że poprzedzanym znakom nie są nadawane żadne dodatkowe znaczenia i oznaczają same siebie, np. \. oznacza znak kropki (a nie dowolny znak).
• Zestaw znaków między nawiasami kwadratowymi oznacza jeden dowolny znak objęty nawiasami kwadratowymi, np. [abc] oznacza a, b lub c. Można używać także przedziałów: [a-c]. Między nawiasami kwadratowymi:
  • Daszek ^ na początku zestawu oznacza wszystkie znaki oprócz tych z zestawu.
  • Aby uniknąć niejasności, znaki - (łącznik) i ] (zamknięcie nawiasu kwadratowego) zapisywane są na skraju zestawu lub w niektórych systemach po znaku odwrotnego ukośnika, daszek zaś wszędzie z wyjątkiem początku łańcucha. Zasady te mogą być różne w zależności od konkretnej implementacji.
  • Większość znaków specjalnych w tym miejscu traci swoje znaczenie.
• Pomiędzy nawiasami okrągłymi ( i ) grupuje się symbole do ich późniejszego wykorzystania.
• Gwiazdka * po symbolu (nawiasie, pojedynczym znaku) nazywana jest domknięciem Kleene’a i oznacza zero lub więcej wystąpień poprzedzającego wyrażenia.
• Znak zapytania ? po symbolu oznacza najwyżej jedno (być może zero) wystąpienie poprzedzającego wyrażenia.
• Plus + po symbolu oznacza co najmniej jedno wystąpienie poprzedzającego go wyrażenia.
• Daszek ^ oznacza początek wiersza, dolar $ oznacza koniec wiersza.
• Pionowa kreska (ang. pipeline) | to operator OR np., jeśli napiszemy a|b|c, oznacza to, że w danym wyrażeniu może wystąpić a lub b lub c.
• Znaki \<, \> oznaczające początek i koniec wyrazu (w niektórych implementacjach występuje pełniący podobną funkcję metaznak \b). Np. \<al znajdzie wszystkie wyrazy zaczynające się na al. et\> znajdzie wyrazy które kończą się na et.

Przykład 1

Polski kod pocztowy składa się z sekwencji następujących elementów:

• dwóch cyfr ([0-9][0-9]),
• dywizu (-),
• trzech cyfr ([0-9][0-9][0-9]).

Ostatecznie wyrażenie regularne, które opisuje kod pocztowy [0-9][0-9]-[0-9][0-9][0-9] lub wykorzystując opisane niżej rozszerzenia perla: [0-9]{2}-[0-9]{3}.

Przykład 2

Anglosaski napis reprezentujący liczbę rzeczywistą składa się z następujących elementów:

• opcjonalnego znaku ([+-]?);
• przynajmniej jednej cyfry ([0-9]+);
• opcjonalnej części ułamkowej (?), która składa się z kolei z:
  • kropki dziesiętnej (\.);
  • przynajmniej jednej cyfry ([0-9]+).

Wyrażenie regularne opisujące taki napis: [+-]?[0-9]+(\.[0-9]+)?.

Przykład 3

Wyrażenie sprawdzające poprawność adresów poczty elektronicznej (w wersji uproszczonej, opisujące adresy w najpopularniejszej formie): ^[_a-zA-Z0-9-]+(\.[_a-zA-Z0-9-]+)*@[a-zA-Z0-9-]+(\.[a-zA-Z0-9-]{1,})*\.([a-zA-Z]{2,}){1}$.

Rozszerzenia Perla

Rozszerzenia Perla to między innymi:

• Negacja zestawu (wszystko, co nie należy do zestawu).
  • cyfry są zastępowane znakami \d (dowolna cyfra) i \D (wszystko co nie jest cyfrą)
  • znaki „białe” \s i \S (przeciwieństwo)
• Rozszerzony zapis przedziałów, wprowadzenie klas znaków np.:
  • [:digit:] oznacza dowolną cyfrę
  • [:alpha:] literę
  • [:alnum:] literę lub cyfrę
• Możliwość precyzyjnego określenia liczby wystąpień danego wyrażenia
  • wyrażenie {N} oznacza dokładnie N wystąpień
  • wyrażenie {N,} co najmniej N wystąpień wyrażenia
  • wyrażenie {,M} co najwyżej M wystąpień wyrażenia
  • wyrażenie {N,M} od N do M wystąpień wyrażenia
• Referencje wsteczne, czyli możliwość odwoływania się do odnalezionych podciągów zgrupowanych poprzez nawiasy. Np. w wyrażeniu (.*)\1 referencją wsteczną jest „\1” i oznacza powtórzenie ciągu znalezionego w ramach pierwszej grupy nawiasów. To rozszerzenie pozwala definiować języki, które nie są regularne.

Wyrażenia zachłanne

Kwantyfikatory w wyrażeniach regularnych dopasowują tak wiele znaków, jak to możliwe, są to więc tzw. wyrażenia zachłanne (greedy – z ang. zachłanne, łapczywe). Może to być znaczącym problemem. Przykładowo, aby dopasować pierwszy element, znajdujący się w podwójnych nawiasach kwadratowych w tekście:

Kolejna eksplozja wieloryba nastąpiła na [[Tajwan]]ie, [[26 stycznia]] [[1990]].

użytkownik użyłby najchętniej wyrażenia (\[\[.*\]\]), które wygląda poprawnie (nawias kwadratowy powinien być interpretowany jako znak, dlatego poprzedzony jest odwrotnym ukośnikiem), jednak zwróci ciąg [[Tajwan]]ie, [[26 stycznia]] [[1990]] zamiast oczekiwanego [[Tajwan]].

Są dwie metody na uniknięcie tego problemu. Po pierwsze, zamiast określać, co powinno być dopasowane, można określić, co nie powinno być dopasowane. W tym przypadku ] jest znakiem niepożądanym, więc wyrażenie miałoby postać (\[\[[^\]]*\]\]). Jednak nie uda się w ten sposób dopasować ciągu znaków w postaci:

A B C D E F G

Drugą, bardziej współczesną metodą, jest „zmuszenie” kwantyfikatora, aby nie był typu „greedy”, poprzez dopisanie za nim znaku zapytania (\[\[.*?\]\]). Są to tak zwane „leniwe” (ang. lazy) odmiany kwantyfikatorów.

Silniki dopasowywania i wydajność

Praktyczne implementacje wyrażeń regularnych dzielą się na dwie rodziny. Silniki oparte na automatach skończonych (m.in. grep, AWK i RE2) przekształcają wzorzec w automat i gwarantują czas dopasowania liniowy względem długości przeszukiwanego tekstu, nie obsługują jednak konstrukcji wykraczających poza języki regularne. Silniki z nawrotami (backtracking), stosowane m.in. w Perlu, PCRE, Javie i Pythonie, przeszukują możliwe dopasowania rekurencyjnie – dzięki temu obsługują referencje wsteczne i inne rozszerzenia, ale w najgorszym przypadku ich czas działania rośnie wykładniczo.

Katastrofalny nawrót i ReDoS

W silnikach z nawrotami niektóre wzorce, zwłaszcza z zagnieżdżonymi kwantyfikatorami w rodzaju (a+)+$, prowadzą do tzw. katastrofalnego nawrotu (catastrophic backtracking): liczba sprawdzanych kombinacji rośnie wykładniczo wraz z długością niepasującego tekstu. Celowe wykorzystanie tej własności przeciwko aplikacji nosi nazwę ReDoS (regular expression denial of service) i stanowi odmianę ataku blokady usług.

Problem ma znaczenie praktyczne: 20 lipca 2016 roku serwis Stack Overflow przestał odpowiadać na 34 minuty, gdy jedno z wyrażeń użytych do formatowania wpisów wpadło w katastrofalny nawrót na spreparowanym poście, a 2 lipca 2019 roku globalna awaria Cloudflare – odcinająca na niemal pół godziny znaczną część ruchu w internecie – została spowodowana wdrożeniem do zapory aplikacyjnej reguły z wyrażeniem powodującym nadmierne nawroty. Do środków zaradczych należą silniki o gwarantowanym liniowym czasie działania (jak RE2), limity czasu dopasowania oraz przepisywanie podatnych wzorców.

Ograniczenia

Choć języki regularne obejmują dowolne skończone zbiory słów, składnia wyrażeń regularnych nie oferuje zwięzłego operatora permutacji – dopasowanie wszystkich ciągów „ABC”, „ACB”, „BAC”, „BCA”, „CAB” i „CBA” wymaga jawnego wyliczenia wariantów. Z lematu o pompowaniu wynika ponadto, że wyrażeniami regularnymi (bez rozszerzeń) nie da się opisać języków wymagających zliczania o nieograniczonej głębokości, takich jak język poprawnie sparowanych nawiasów

Zobacz też

• gramatyka formalna
• gramatyka kontekstowa
• gramatyka regularna
• hierarchia Chomskiego
• wieloznacznik
• pomoc:Wyrażenia regularne

Bibliografia

• Jeffrey E.F. Friedl, Wyrażenia regularne, Gliwice: Helion O'Reilly, 2001, ISBN 83-7197-351-9  (pol.).
• Tony Stubblebine, Wyrażenia regularne leksykon kieszonkowy Wydanie I, Gliwice: Helion O'Reilly, grudzień 2003, ISBN 83-7361-075-8 .
• Tony Stubblebine, Wyrażenia regularne leksykon kieszonkowy Wydanie II, Gliwice: Helion O'Reilly, styczeń 2008, ISBN 978-83-246-1392-2 .
• John E Hopcroft, Jeffrey D Ullman, Beata Konikowska, Wprowadzenie do teorii automatów, języków i obliczeń, Warszawa: Wydawnictwo Naukowe PWN, 2003, ISBN 83-01-14090-9 .

Linki zewnętrzne

• Tester wyrażeń regularnych w JavaScripcie (ang.)
• Tester wyrażeń regularnych we Fleksie (ang.)
• Structural Regular Expressions by Rob Pike (ang.)
• Tester wyrażeń regularnych (JS, PHP, Python) (ang.)
• Wyrażenia regularne – ściągawka (ang.)
• Znajdowanie i zamienianie tekstu za pomocą wyrażeń regularnych (zaawansowane) [online], office.microsoft.com [zarchiwizowane z adresu 2014-02-09] . – wyrażenia regularne w Microsoft Word – zarchiwizowana strona internetowa oficjalnej pomocy technicznej (ang.)