Wyrażenie regularne

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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[edytuj | edytuj kod]

Definicja wyrażeń regularnych[edytuj | edytuj kod]

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ż:
  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[edytuj | edytuj kod]

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:

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

Własności wyrażeń regularnych[edytuj | edytuj kod]

Wyrażenia są równoważne gdy definiują ten sam język: e_1 = e_2 \iff L(e_1)=L(e_2)

Przykład 1[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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
FA regexp accept none.svg automat dla pustego języka, nie zawierającego żadnego słowa; L(\varnothing) = \varnothing
FA regexp accept null.svg automat dla języka akceptującego tylko słowo puste; L(\epsilon) = \{\epsilon\}
FA regexp accept singlesymbol.svg automat dla języka akceptującego tylko jeden symbol; L(a) = \{a\}
NFA regexp concat.svg NAS dla konkatenacji dwóch wyrażeń regularnych: \alpha\ \beta
NFA regexp sum.svg NAS dla sumy dwóch wyrażeń regularnych: \alpha + \beta
NFA regexp kleene.svg 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[edytuj | edytuj kod]

Porównanie składni praktycznej z teoretyczną[edytuj | edytuj kod]

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
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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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)[edytuj | edytuj kod]

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.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • 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, 12 2003. ISBN 83-7361-075-8.
  • Tony Stubblebine: Wyrażenia regularne leksykon kieszonkowy Wydanie II. Gliwice: Helion O`REILLY, 01 2008. ISBN 978-83-246-1392-2.
  • 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.

Linki zewnętrzne[edytuj | edytuj kod]