Wyrażeniami regularnymi nazywamy pewne wzorce, którymi możemy opisać łańcuchy symboli. Znalazły one bardzo szerokie zastosowanie i są wykorzystywane, nie tylko przy analizie składniowej podczas budowy kompilatorów, ale wszędzie tam, gdzie istnieje potrzeba szybkiego wyszukania w dokumencie określonego łańcucha znaków i porównania go ze wzorcem. Można oczywiście przeprowadzać tego typu procesy bez udziału wyrażeń regularnych, stosując tradycyjne funkcje i procedury, ale wydłuża to znacznie kod programu oraz czas obliczeń, choć pozornie programy mogą się wydawać prostsze do napisania. Przykładem zastosowania wyrażeń regularnych jest analiza kodu HTML strony internetowej, w celu wyodrębnienia z niego czystego tekstu, który jest widoczny w przeglądarce.
Niech ∑ będzie alfabetem. Wyrażenia regularne nad ∑ i zbiory przez nie reprezentowane definiujemy rekursywne w następujący sposób:
Ø jest wyrażeniem regularnym reprezentującym zbiór pusty
ε jest wyrażeniem regularnym reprezentującym zbiór {ε}
Dla każdego a z ∑, a jest wyrażeniem regularnym reprezentującym zbiór {a}
Jeżeli r i s są wyrażeniami regularnymi reprezentującymi, odpowiednio, języki R i S, to (r + s), (rs) i (r*) są wyrażeniami regularnymi reprezentującymi, odpowiednio, zbiory R∪S, RS i R*
Z reguły 4 wynika, że:
Przykładowo, wyrażenie regularne mo(ż + rz)e definiuje język, zawierający dwa słowa: "może" i "morze". To samo możemy zapisać w postaci: może+morze
W praktyce wyrażenia regularne zapisywane są za pomocą bogatszej składni, niż ta stosowana w informatyce teoretycznej. Obecnie są one częścią niektórych narzędzi systemowych oraz języków programowania, przetwarzających tekst, takich jak np. Pearl, a także stanowią osobne biblioteki znacznej większości języków programowania. Aktualnie dwiema najczęściej stosowanymi składniami są uniksowa i pearlowa. Ta ostatnia używana jest nie tylko w Perlu, ale także np. w C.
Podstawową składnię wyrażeń regularnych przedstawiono poniżej.
Klasy znaków:
| . | dowolny znak |
| [abc] | dowolny znak ze wskazanego zbioru |
| [^abc] | dowolny znak oprócz tych ze zbioru |
| [a-z0-9] | dowolny znak z zakresu od a do z lub od 0 do 9 |
| \w | dowolny znak z klasy word (litera, cyfra, podkreślnik) |
| \W | dowolny znak spoza klasy word |
| \s | dowolny biały znak (np. spacja) |
| \S | dowolny znak inny niż biały |
| \d | dowolna cyfra |
| \D | dowolny znak inny niż cyfra |
W poniższej znajdują się symbole, przy pomocy których można określić miejsce w tekście, w którym ma się pojawić dopasowanie do wzorca:
| ^ | dopasowanie musi się pojawić na początku tekstu |
| $ | dopasowanie musi się pojawić na końcu tekstu |
| \b | dopasowanie musi się znajdować na początku lub końcu słowa |
| \B | dopasowanie nie może się znajdować na początku lub końcu słowa |
Bardzo często istnieje potrzeba określenia ilości powtórzeń danego znaku lub ciągu znaków. Można to określić za pomocą symboli przedstawionych poniżej:
| * | zero lub więcej razy |
| + | jeden lub więcej razy |
| ? | zero lub jeden raz |
| {n} | dokładnie n razy |
| {n, } | co najmniej n razy |
| {n, m} | co najmniej n razy, ale nie więcej niż m razy |
Istnieje jeszcze wiele elementów składni wyrażeń regularnych. Wybrane z nich (często przydatne) przedstawiono poniżej:
| \ | Ukośnik pełni również funkcję znaku ucieczki Przykładowo wyrażenie \. oznacza po prostu kropkę |
| \0x20 | kod szesnastkowy znaku ASCII |
| \u0020 | kod szesnastkowy znaku Unicode |
| ( ) | nawiasy zwykłe używane są do grupowania symboli |
| | | pionowa kreska oznacza alternatywę |
Jak wynika z powyższych tabel, składnia praktyczna wyrażeń regularnych różni się od składni teoretycznej. Ze względu na uproszczenie i niekiedy znaczne skrócenie zapisu, wprowadzenie składni praktycznej było naturalną koniecznością. Przykładowe różnice pokazują przykłady umieszczone poniżej:
|
|
| 0+1+2+3+4+5+d+e+f+g+h+i+j+k | [012345defghijk] lub [0-5d-k] |
| + | | |
| kkkkkkk | k{7} |
| kk* | k+ |
| k+ε | k? |
Jak widać z powyższej tabeli składnia praktyczna znacznie upraszcza zapis wyrażeń regularnych, a ponadto daje więcej możliwości, ponieważ występują w niej elementy, których nie ma w składni teoretycznej.
Aby pokazać, jakie możliwości daje stosowanie wyrażeń regularnych, najlepiej odwołać się do konkretnych przykładów.
Załóżmy, że chcemy napisać wyrażenie regularne, sprawdzające poprawność zapisu kodu pocztowego. Ma on postać dwóch cyfr, po których następuje myślnik, a następnie jeszcze trzy cyfry (np. 05-840). Możemy zapisać kilka wyrażeń regularnych, które znajdą zastosowanie w tym przypadku. Poniżej przedstawiono cztery warianty, których wynik działania jest identyczny:
^[0-9][0-9]-[0-9][0-9][0-9]$
^[0-9]{2}-[0-9]{3}$
^\d\d-\d\d\d$
^\d{2}-\d{3}$
Kolejnym przykładem może być sprawdzanie poprawności zapisu liczby rzeczywistej, który składa się ze znaku + lub - (znak ten może wystąpić, ale nie musi), następnie występuje dowolna liczba cyfr, po której opcjonalnie może wystąpić kropka i rozwinięcie dziesiętne (np 3.1415, -25.87 itd.)
^[+-]?[0-9]+(\.[0-9]+)?$
^[+-]?\d{1,}(\.\d{1,})?$
^[+-]?\d+(\.\d+)?$
Jak widzimy na podstawie prostych przykładów, istnieje wiele sposobów na opisanie lub sprawdzenie tego samego ciągu znaków za pomocą wyrażeń regularnych.