Wyrażenie regularne - Polski Serwis Naukowy

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.

Symbol – odpowiednik pojęcia postrzegany zmysłowo. Najbardziej ogólnie jest to zastąpienie jednego pojęcia innym, krótszym, bardziej wyrazistym lub najlepiej oddającym jego naturę, albo mniej abstrakcyjnym. Jest to znak odnoszący się do innego systemu znaczeń, niż do tego do którego bezpośrednio się odnosi. Przykładowo symbol lwa oznacza nie tylko dany gatunek zwierzęcia, lecz często także siłę lub władzę. Symbole są pewnymi znakami umownymi, które w różnych kulturach mogą mieć różne znaczenia - to odróżnia symbol od jednoznacznej alegorii. Znaczenia szczególne to między innymi:
Determinizacją automatu skończonego nazywamy proces tworzenia deterministycznego automatu skończonego (DAS) z niedeterministycznego automatu skończonego (NAS). Transformacja taka jest zawsze możliwa i otrzymany w jej procesie automat akceptuje dokładnie ten sam język (zbiór słów), co automat wejściowy. Jakkolwiek, gdy NAS ma n stanów, wynikowy DAS może mieć do 2^n stanów, wykładniczo więcej, co czyni proces niepraktycznym dla dużych NAS.

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.

Tcl (Tool Command Language) jest językiem skryptowym o składni częściowo podobnej do języków skryptowych powłok, oraz częściowo do Lispu. Jest znany z pakietu Tk (Tk Toolkit), który pozwala na pisanie przenośnych graficznych interfejsów użytkownika (GUI) dla wielu systemów operacyjnych oraz pakietu Expect, który pozwala na automatyzację zadań.
grep – jeden z podstawowych programów wchodzących w skład systemu Unix. Służy do znajdowania w strumieniu wejścia (plik, lub po prostu wpisywany tekst) ciągów znaków pasujących do danego wyrażenia regularnego. Został napisany przez Kena Thompsona.

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.

Rozdzielność działań jest własnością pierścienia (a więc i ciała) określającą powiązanie dwóch operatorów: addytywnego (nazywanego zwykle dodawaniem) i multiplikatywnego (zwykle mnożenie).
Język regularny (ang. regular language) to język formalny taki, że istnieje automat o skończonej liczbie stanów potrafiący zdecydować, czy dane słowo należy do języka.

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:

$\varnothing, \epsilon$ (słowo puste) są wyrażeniami regularnymi;
wszystkie symbole $a_i \in \Sigma$ są wyrażeniami regularnymi;
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)
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.

sed (ang. Stream EDitor – edytor strumieniowy) – program służący do przetwarzania plików tekstowych. Mimo prostoty, program dysponuje dużymi możliwościami.
Kwantyfikator – termin przyjęty w matematyce i logice matematycznej na oznaczenie zwrotów: dla każdego, istnieje takie i im pokrewnych, a także odpowiadającym im symbolom wiążacym zmienne w formułach. Są podstawowym elementem w rozwoju logiki pierwszego rzędu.

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.

Automat skończony (ang. finite state machine, FSM) to abstrakcyjny, matematyczny, iteracyjny model zachowania systemu dynamicznego oparty o tablicę dyskretnych przejść między jego kolejnymi stanami (diagram stanów).
Język formalny – jest to podzbiór zbioru wszystkich słów nad skończonym alfabetem. Język formalny jest kluczowym pojęciem w informatyce, logice matematycznej i językoznawstwie. Język formalny nie jest uściśleniem pojęcia języka naturalnego i nie powinien być z nim mylony.

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$ .

Unix Time-Sharing System (pisane również jako UNIX, choć nie jest to skrót – nazwa „UNIX” jest kalamburem określenia MULTICS, który był wzorem dla Uniksa) – system operacyjny napisany w 1969 r. w Bell Labs (UNIX System Laboratories, USL) przez Dennisa Ritchie i Kena Thompsona. Rozwijany później w bardzo dynamiczny sposób, co zaowocowało powstaniem wielu odmian i implementacji.
Ruby to interpretowany, w pełni obiektowy i dynamicznie typowany język programowania stworzony w 1995 roku przez Yukihiro Matsumoto (pseudonim Matz). W języku angielskim ruby oznacza rubin.

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:

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

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.

Zbiór (niegdyś mnogość, wielość) – jedno z fundamentalnych pojęć współczesnej matematyki, w teorii mnogości (teorii zbiorów) przyjmowane jako pojęcie pierwotne. Intuicyjnie: kolekcja, zestaw niepowtarzających się obiektów bez wyróżnionej kolejności nazywanych elementami.
Język programowania – zbiór zasad określających, kiedy ciąg symboli tworzy program (czyli ciąg symboli opisujący obliczenia) oraz jakie obliczenia opisuje.

czytaj dalej: [2], [3]

w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)