Wyrażenie regularne

Wyrażenia regularne (ang. regular expressions, w skrócie regex lub regexp) – wzorce, które opisują łańcuchy 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, mogą również wyszczególniać istotne części łańcucha.

Wyrażenia regularne to w informatyce teoretycznej ciągi znaków pozwalające 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 (znanego też jako pgrep). Perlową składnię stosuje się również w maskach przepisań mod rewrite.

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, +, ^*, ), ($ 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_1e_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) = X e_1 + X e_2$
• $e^* e = e e^*$
• $(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ę $e_1$, np. $e_1 e_1$, $e_1 e_1 e_1 e_1$, a także pusty
• $e_1e_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

Ta sekcja jest niekompletna. Jeśli możesz, rozbuduj ją.

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.

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
$($, $)$	(, ) lub \(, \)	w niektórych implementacjach symbole specjalne poprzedza się backslashem
$+$	| lub \|	j.w.
$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
$e e^*$	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
$e e e e$	e{4}	określona liczba powtórzeń (tutaj 4); rozszerzenie Perla
$e e e e (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. 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]),
• myślnika (-),
• 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

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 (ang. greedy)

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.

Bibliografia

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

Zobacz też

• automat skończony
• gramatyka formalna
• gramatyka kontekstowa
• gramatyka regularna
• język formalny
• język regularny
• znaki globalne

Linki zewnętrzne

• Skrypt do sprawdzania poprawności wyrażeń regularnych
• Tester wyrażeń regularnych w JavaScripcie
• Tester wyrażeń regularnych we Fleksie
• Regular Expression Matching Can Be Simple And Fast (ang.). [dostęp 11.10.2008].
• Structural Regular Expressions by Rob Pike (en)