Tekst źródłowy strony Wyrażenie regularne

'''Wyrażenie regularne''' ({{ang.|regular expression}}, w skrócie {{K|en|regex}} lub {{K|en|regexp}}) – wzorzec opisujący łańcuch [[symbol]]i. Teoria wyrażeń regularnych jest związana z teorią [[język regularny|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 [[algorytm]]y 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 (program)|sed]], [[grep]], wielu [[edytor tekstu|edytorów tekstu]], [[język programowania|języków programowania]] przetwarzających tekst [[AWK]] i [[Perl]], a także są dostępne jako odrębne [[biblioteka programistyczna|biblioteki]] dla wszystkich języków używanych obecnie.

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

== Wyrażenie regularne w informatyce teoretycznej ==
=== Definicja wyrażeń regularnych ===
Wyrażeniem regularnym nad alfabetem <math>\Sigma</math> nazywamy ciąg znaków składający się z symboli <math>\varnothing,\ \epsilon,\ +,\ \text{*},\ ),\ (</math> oraz symboli <math>a_i</math> z alfabetu <math>\Sigma</math> następującej postaci:

# <math>\varnothing, \epsilon</math> (słowo puste) są wyrażeniami regularnymi;
# wszystkie symbole <math>a_i \in \Sigma</math> są wyrażeniami regularnymi;
# jeśli <math>e_1, e_2</math> są wyrażeniami regularnymi, to są nimi również:
#* <math>e_1^*</math> ([[domknięcie Kleene’ego]])
#* <math>e_1e_2</math> (konkatenacja)
#* <math>e_1+e_2</math> (suma)
#* <math>(e_1)</math> (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 [[język regularny|regularny]].

=== Definicja języka określanego przez wyrażenie regularne ===
Język definiowany przez wyrażenie regularne jest definiowany indukcyjnie. Niech {{Mvar|L}}({{Mvar|w}}) oznacza język definiowany przez {{Mvar|w}}. Wtedy baza indukcji jest następująca:

* <math>L(\epsilon) = \{\epsilon\}</math> (zbiór zawierający tylko słowo puste)
* <math>L(\varnothing) = \varnothing</math> ([[zbiór pusty]])
* <math>L(a) = \{a\}</math> dla dowolnego <math>a</math> z alfabetu

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

* <math>L(w+v) = L(w) \cup L(v)</math> ([[suma zbiorów|suma języków]])
* <math>L(w^*) = (L(w))^*</math> (domknięcie Kleene’ego)
* <math>L(wv) = \{xy : x\in L(w) \wedge y \in L(v) \}</math> ([[konkatenacja|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:
<math>e_1 = e_2 \iff L(e_1)=L(e_2)</math>

* <math>e + e = e</math>
* <math>e_1 + e_2 = e_2 + e_1</math> – suma jest [[Przemienność|przemienna]]
* <math>\epsilon e = e \epsilon = e</math> – łańcuch pusty jest [[element neutralny|elementem neutralnym]] konkatenacji
* <math>(e_1 + e_2) + e_3 = e_1 + (e_2 + e_3)</math> – suma jest [[łączność (matematyka)|łączna]]
* <math>(e_1 e_2) e_3 = e_1 (e_2 e_3)</math> – konkatenacja również jest łączna
* <math>(e_1 + e_2) X = e_1 X + e_2 X</math> – konkatenacja jest [[rozdzielność|rozdzielna]] względem sumy
* <math>X (e_1 + e_2) = X e_1 + X e_2</math>
* <math>e^* e = e e^*</math>
* <math>(e^*)^* = e^*</math> – domknięcie Kleene’ego jest [[idempotentność|idempotentne]]
* <math>e^* e^* = e^*</math>

; Przykład 1
Wyjaśnienie reguł:

* <math>e_1^*</math> – dowolny ciąg składający się z <math>e_1,</math> np. <math>e_1 e_1,</math> <math>e_1 e_1 e_1 e_1,</math> a także pusty
* <math>e_1e_2</math> – sekwencja, najpierw <math>e_1,</math> następnie <math>e_2</math>
* <math>e_1+e_2</math> – alternatywa, albo <math>e_1,</math> albo <math>e_2</math>

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

; Przykład 3
Wyrażenie <math>(a+b)^*baba(a+b)^*</math> definiuje język wszystkich słów nad alfabetem <math>\{a, b\},</math> które zawierają [[podsłowo]] baba.

=== Wyrażenia regularne a automaty skończone ===
{{sekcja stub}}
Języki regularne można opisać również za pomocą [[automat skończony|automatów skończonych]]:
# [[niedeterministyczny automat skończony|niedeterministycznego automatu skończonego]] (NAS) z <math>\epsilon</math>-przejściami (automat może zmienić swój stan bez podania symbolu wejściowego),
# niedeterministycznego automatu skończonego bez <math>\epsilon</math>-przejść, oraz
# [[deterministyczny automat skończony|deterministycznego automatu skończonego]] (DAS).

{| class="wikitable"
! Automat skończony
! Wyrażenie regularne
|-
| align="center"| [[Plik:FA regexp accept none.svg]]
| automat dla pustego języka, nie zawierającego żadnego słowa; <math>L(\varnothing) = \varnothing</math>
|-
| align="center"| [[Plik:FA regexp accept null.svg]]
| automat dla języka akceptującego tylko słowo puste; <math>L(\epsilon) = \{\epsilon\}</math>
|-
| align="center"| [[Plik:FA regexp accept singlesymbol.svg]]
| automat dla języka akceptującego tylko jeden symbol; <math>L(a) = \{a\}</math>
|-
| align="center"| [[Plik:NFA regexp concat.svg]]
| NAS dla konkatenacji dwóch wyrażeń regularnych: <math>\alpha\ \beta</math>
|-
| align="center"| [[Plik:NFA regexp sum.svg]]
| NAS dla sumy dwóch wyrażeń regularnych: <math>\alpha + \beta</math>
|-
| align="center"| [[Plik:NFA regexp kleene.svg]]
| NAS dla domknięcia Kleene’ego wyrażenia regularnego: <math>\alpha^*</math>
|}

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 <math>\epsilon</math>-przejściami zgodnie ze schematem pokazanym wyżej, następnie usuwane są <math>\epsilon</math>-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 (język programowania)|Tcl]], a także biblioteki dla [[Haskell|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.

{| class="wikitable"
! Informatyka teoretyczna
! Praktyka
! Komentarz
|-
| <math>\varnothing, \epsilon</math> || brak, ""
| w praktyce zbioru pustego nie podaje się wprost, w większości języków programowania słowo puste jest oznaczane przez <code>""</code> (parę cudzysłowów)
|-
| <math>(,\;)</math>
| <code>(</code>, <code>)</code> lub <code>\(</code>, <code>\)</code>
| w niektórych implementacjach symbole specjalne poprzedza się backslashem
|-
| <math>+</math> || <code><nowiki>|</nowiki></code> lub <code><nowiki>\|</nowiki></code>
| jw.
|-
| <math>0 + 1 + 2 + 3 + a + b + c + d + e + f + g + h</math>
| <code>[0123abcdefgh]</code> lub krócej <code>[0-3a-h]</code>
| zakres znaków (dokładny opis – patrz niżej)
|-
| <math>a + b + \ldots + z + A + B + \ldots + Z</math>
| <code>.</code>
| 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
|-
| <math>^*</math> || <code>*</code> lub <code>\*</code>
| 0 lub więcej wystąpień
|-
| <math>e + \epsilon</math> || <code>e?</code>
| wyrażenie <code>e</code> występuje 0 lub 1 raz
|-
| <math>e e^*</math> || <code>e+</code>
| wyrażenie <code>e</code> występuje 1 lub więcej razy
|-
| brak || [[Kareta (znak)|^]]
| 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 [^<code>e</code>] oznacza negację <code>e</code>
|-
| brak || $
| metaznak oznaczający koniec łańcucha
|-
| <math>e e e e</math> || <code>e{4}</code>
| określona liczba powtórzeń (tutaj 4); rozszerzenie Perla
|-
| <math>e e e e (e + \epsilon) (e + \epsilon) (e + \epsilon)</math>
| <code>e{4,7}</code>
| określony zakres liczby powtórzeń wyrażenia <code>e</code> (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. <code>a</code> określa łańcuch złożony ze znaku <code>a</code>.
* Kolejne symbole oznaczają, że w łańcuchu muszą wystąpić dokładnie te symbole w dokładnie takiej samej kolejności, np. <code>ab</code> oznacza że łańcuch musi składać się z litery <code>a</code> poprzedzającej literę <code>b</code>.
* Kropka <code>.</code> oznacza dowolny znak z wyjątkiem znaku nowego wiersza (zależnie od ustawień i rodzaju wyrażeń).
* Znaki specjalne poprzedzone odwrotnym ukośnikiem <code>\</code> powodują, że poprzedzanym znakom nie są nadawane żadne dodatkowe znaczenia i oznaczają same siebie, np. <code>\.</code> oznacza znak kropki (a nie dowolny znak).
* Zestaw znaków między nawiasami kwadratowymi oznacza jeden dowolny znak objęty nawiasami kwadratowymi, np. <code>[abc]</code> oznacza a, b lub c. Można używać także przedziałów: <code>[a-c]</code>. Między nawiasami kwadratowymi:
** Daszek <code>^</code> na początku zestawu oznacza wszystkie znaki oprócz tych z zestawu.
** Aby uniknąć niejasności, znaki <code>-</code> (łącznik) i <code>]</code> (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 <code>(</code> i <code>)</code> grupuje się symbole do ich późniejszego wykorzystania.
* Gwiazdka <code>*</code> po symbolu (nawiasie, pojedynczym znaku) nazywana jest [[Domknięcie Kleene’ego|domknięciem Kleene’a]] i oznacza zero lub więcej wystąpień poprzedzającego wyrażenia.
* Znak zapytania <code>?</code> po symbolu oznacza najwyżej jedno (być może zero) wystąpienie poprzedzającego wyrażenia.
* Plus <code>+</code> po symbolu oznacza co najmniej jedno wystąpienie poprzedzającego go wyrażenia.
* Daszek <code>^</code> oznacza początek wiersza, dolar <code>$</code> oznacza koniec wiersza.
* Pionowa kreska (ang. {{K|en|pipeline}}) <code>|</code> to operator OR np., jeśli napiszemy <code>a|b|c</code>, oznacza to, że w danym wyrażeniu może wystąpić <code>a</code> lub <code>b</code> lub <code>c</code>.
* Znaki <code>\<</code>, <code>\></code> oznaczające początek i koniec wyrazu (w niektórych implementacjach występuje pełniący podobną funkcję metaznak <code>\b</code>). Np. <code>\<al</code> znajdzie wszystkie wyrazy zaczynające się na <code>al</code>. <code>et\></code> znajdzie wyrazy które kończą się na <code>et</code>.

; Przykład 1
Polski [[kod pocztowy]] składa się z sekwencji następujących elementów:
* dwóch cyfr (<code>[0-9][0-9]</code>),
* dywizu (<code>-</code>),
* trzech cyfr (<code>[0-9][0-9][0-9]</code>).

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

; Przykład 2
Anglosaski napis reprezentujący liczbę rzeczywistą składa się z następujących elementów:
* opcjonalnego znaku (<code>[+-]?</code>);
* przynajmniej jednej cyfry (<code>[0-9]+</code>);
* opcjonalnej części ułamkowej (<code>?</code>), która składa się z kolei z:
** kropki dziesiętnej (<code>\.</code>);
** przynajmniej jednej cyfry (<code>[0-9]+</code>).

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

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

=== Rozszerzenia Perla ===
Rozszerzenia [[Perl]]a 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.:
** <code><nowiki>[:digit:]</nowiki></code> oznacza dowolną cyfrę
** <code><nowiki>[:alpha:]</nowiki></code> literę
** <code><nowiki>[:alnum:]</nowiki></code> literę lub cyfrę
* Możliwość precyzyjnego określenia liczby wystąpień danego wyrażenia
** wyrażenie <code>{N}</code> oznacza dokładnie {{Mvar|N}} wystąpień
** wyrażenie <code>{N,}</code> co najmniej {{Mvar|N}} wystąpień wyrażenia
** wyrażenie <code>{,M}</code> co najwyżej {{Mvar|M}} wystąpień wyrażenia
** wyrażenie <code>{N,M}</code> od {{Mvar|N}} do {{Mvar|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 <code><nowiki>(.*)\1</nowiki></code> referencją wsteczną jest „<code>\1</code>” 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 ===
[[Kwantyfikator]]y w wyrażeniach regularnych dopasowują tak wiele znaków, jak to możliwe, są to więc tzw. wyrażenia zachłanne ({{K|en|greedy}} – z [[język angielski|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 <code><nowiki>[[Tajwan]]ie, [[26 stycznia]] [[1990]]</nowiki></code>.''

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

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 <nowiki>]</nowiki> jest znakiem niepożądanym, więc wyrażenie miałoby postać <code><nowiki>(\[\[[^\]]*\]\])</nowiki></code>. 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 „{{J|en|greedy}}”, poprzez dopisanie za nim znaku zapytania <code>(\[\[.*?\]\])</code>. Są to tak zwane „leniwe” (ang. {{K|en|lazy}}) odmiany kwantyfikatorów.

=== Wady wyrażeń regularnych ===
Wyrażenia regularne obecnie nie wspierają<ref>{{Cytuj |tytuł = Dlaczego w Regexach nie ma permutacji? (Nawet jeśli wydaje się, że zwykłe języki to potrafią) |data dostępu = 2021-10-21 |opublikowany = qa-stack.pl |url = https://qa-stack.pl/cs/100206/why-is-there-no-permutation-in-regexes-even-if-regular-languages-seem-to-be-ab}}</ref> obsługi [[Permutacja|permutacji]] (wedle obecnych definicji i implementacji), tzn. nie ma mechanizmu, który w zwięzły sposób pozwoliłby dopasować np. ciągi znaków „ABC”, „ACB”, „BAC”, „BCA”, „CAB” i „CBA” (potrzebne jest explicite dopasowanie poszczególnych ciągów)

== Zobacz też ==
* [[gramatyka formalna]]
* [[gramatyka kontekstowa]]
* [[gramatyka regularna]]
* [[hierarchia Chomskiego]]
* [[wieloznacznik]]
* [[pomoc:Wyrażenia regularne]]

== Przypisy ==
{{Przypisy}}

== Bibliografia ==
* {{Cytuj książkę |nazwisko= Friedl |imię= Jeffrey E.F. |tytuł= Wyrażenia regularne |rok= 2001 |wydawca= Helion O'Reilly|miejsce= Gliwice |isbn = 83-7197-351-9 |język = pl}}
* {{Cytuj książkę |nazwisko= Stubblebine |imię= Tony |autor link= |tytuł= Wyrażenia regularne leksykon kieszonkowy Wydanie I |url= |rok=2003 |miesiąc= 12 |wydawca= Helion O'Reilly |miejsce= Gliwice |isbn = 83-7361-075-8 |strony=}}
* {{Cytuj książkę |nazwisko= Stubblebine |imię= Tony |autor link= |tytuł= Wyrażenia regularne leksykon kieszonkowy Wydanie II |url= |rok=2008 |miesiąc= 01 |wydawca= Helion O'Reilly |miejsce= Gliwice |isbn = 978-83-246-1392-2 |strony=}}
* {{Cytuj książkę |autor= Hopcroft, John E; Ullman, Jeffrey D; Konikowska, Beata |tytuł= Wprowadzenie do teorii automatów, języków i obliczeń |data=2003 |wydawca=Wydawnictwo Naukowe PWN |miejsce=Warszawa |isbn=83-01-14090-9}}

== Linki zewnętrzne ==
{{Wikibooks|PHP/Podstawy wyrażeń regularnych}}
* {{cytuj stronę|url=http://swtch.com/~rsc/regexp/regexp1.html|tytuł=Regular Expression Matching Can Be Simple And Fast|język=en|data dostępu=2008-10-11}}
* [http://regexpal.com Tester wyrażeń regularnych w JavaScripcie] {{lang|en}}
* [http://gskinner.com/RegExr Tester wyrażeń regularnych we Fleksie] {{lang|en}}
* [http://doc.cat-v.org/bell_labs/structural_regexps Structural Regular Expressions by Rob Pike] {{lang|en}}
* [https://regex101.com Tester wyrażeń regularnych (JS, PHP, Python)] {{lang|en}}
* [https://www.cheatography.com/davechild/cheat-sheets/regular-expressions Wyrażenia regularne – ściągawka] {{lang|en}}
* {{Cytuj stronę | url = http://office.microsoft.com/en-ca/word-help/find-and-replace-text-by-using-regular-expressions-advanced-HA102350661.aspx | tytuł = Znajdowanie i zamienianie tekstu za pomocą wyrażeń regularnych (zaawansowane) | opublikowany = office.microsoft.com | archiwum = https://web.archive.org/web/20140209231503/http://office.microsoft.com/en-ca/word-help/find-and-replace-text-by-using-regular-expressions-advanced-HA102350661.aspx | zarchiwizowano = 2014-02-09}} – wyrażenia regularne w Microsoft Word – zarchiwizowana strona internetowa oficjalnej pomocy technicznej {{lang|en}}

{{Kontrola autorytatywna}}
{{SORTUJ:Wyrażenie Regularne}}
[[Kategoria:Języki formalne]]
[[Kategoria:Konstrukcje programistyczne]]
[[Kategoria:Teoria automatów]]