Środowisko programisty/Wyrażenia regularne

Po co są wyrażenia regulrane?

Częstym zadaniem, które wykonuje się podczas pracy z komputerem jest wyszukiwanie danego fragmentu tekstu w jakimś pliku, zmienianie go, sprawdzanie, czy dany tekst się w tym pliku znajduje. Generalnie potrzebujemy narzędzi do znajdywania wzorca o zadanej charakterystyce w jakimś większym tekście. Tą charakterystykę musimy jakoś podawać. W najprostszym przypadku podajemy po prostu tekst, jaki chcemy znaleźć. Na przykład, aby znaleźć wszystkie linie w pliku tekst.txt, w których znajduje się fragment est, wystarczy wykonać polecenie

grep est tekst.txt

Wtedy dla pliku tekst.txt o zawartości

To jest plik tekstowy.
Testujemy narzędzie grep.
Trzecia linia.
A to czwarta linia.
To jest piąta linia.

w wyniku otrzymamy

To jest plik tekstowy.
Testujemy narzędzie grep.
To jest piąta linia.

Zamiast wyszukiwać daną frazę, możemy chcieć znaleźć bardziej skomplikowane wzorce, jak na przykład wszystkie adresy email, które znajdują się w danym tekście, czy też wszystkie formy słowa pies. W tych celach potrzebne są bardziej zaawansowane możliwości podawania charakterystyki frazy, której chcemy szukać. Taką możliwość dają właśnie wyrażenia regularne.

Składnia

Znaki

Najprostsze wyrażenia regularne składają się z ciągu znaków. Niektóre znaki są specjalne, więc aby rozpoznać któryś z nich, trzeba poprzedzać go backslashem. Następujące znaki są specjalne: . ^ $ * ? [ ] \. Na przykład, aby wyszukać w tekście frazę \abc[?] używamy wyrażenia \\abc\[\?\].

Klasy znaków

Przypuśćmy, że chcemy znaleźć wystąpienie jednego z łańcuchów psa, psu i psy. Zatem pierwsze dwa znaki są ustalone i są to ps. Natomiast przy trzecim znaku mamy pewną dowolność. Chcemy, aby trzeci znak mógł być równy a, u lub y. Do tego służą klasy znaków. Listę znaków, którą chcemy rozpoznać, umieszczamy pomiędzy nawiasami kwadratowymi: [auy]. Nasze wyrażenie wygląda więc tak: ps[auy].

bashtest@host:~$ grep ps[auy] <<KONIEC
> psami
> psom
> psu
> ps
> KONIEC
psami
psu
bashtest@host:~$

W klasach możemy podawać przedziały znaków używając myślnika. Na przykład [0-9] rozpoznaje dowolną cyfrę. Możemy podawać kilka przedziałów: [a-zA-Z] rozpozna dowolną literę angielską.

Jeśli umieścimy znak ^ na początku opisu klasy, będzie to oznaczać rozpoznawanie wszystkich znaków nie znajdujących się na liście. Na przykład [^xX] oznacza dowolny znak różny od x i X. Oczywiście możemy podawać też przedziały.

Jeśli chcemy umieścić na liście znak ], należy go podać jako pierwszy na liście. Aby umieścić ^, należy go umieścić w dowolnym miejscu, byle nie na początku. Wreszcie, aby umieścić -, należy go umieścić na końcu listy.

Ponadto mamy możliwość kojarzenia dowolnego znaku oprócz znaku końca linii. Do tego służy znak specjalny . (kropka).

Powtórzenia

Znak specjalny * próbuje dopasować poprzedzający go element zero lub więcej razy w szukanym tekście. Na przykład =* dopasowuje się do ciągu znaków równości (być może ciągu pustego).

Inny przykład, wyrażenie [a-zA-Z][a-zA-Z0-9_]* reprezentuje identyfikator, tzn. niepusty łańcuch znaków zaczynający się od litery i składający się z liter, cyfr oraz znaków podkreślenia.

Znak specjalny + jest podobny do * z tym, że próbuje on dopasować poprzedzający go element jeden lub więcej razy.

Znak specjalny ? mówi, że poprzedzający element może wystąpić, bądź też nie. Na przykład wyrażenie -?[0-9]+ oznacza dowolny niepusty ciąg cyfr, być może poprzedzony znakiem -. Czyli takie wyrażenie może służyć do rozpoznawania dowolnej liczby całkowitej (jeżeli dopuścimy to, że zapis dziesiętny liczby może mieć wiodące zera).

Ponadto ilość powtórzeń można podać bardziej w uniwersalny sposób:

symbol powtórzenia	liczba powtórzeń poprzedzającego elementu
{n}	dokładnie n
{n,}	co najmniej n
{,m}	co najwyżej m
{n,m}	co najmniej n i co najwyżej m

Pozycjonowanie

Znaczniki pozycjonujące są takimi symbolami, które nie są kojarzone z żadnym ciągiem znaków, ale z pozycją w tekście spełniającą pewne ustalone warunki.

Jeśli chcemy, aby wzorzec był dopasowywany od początku linii, wyrażenie zaczynamy znakiem ^. Jeśli chcemy, aby wzorzec był dopasowywany do końca linii, wyrażenie kończymy znakiem $. Gdy użyjemy oba znaki, wzorzec będzie dopasowywany do całej linii.

Na przykład, żeby znaleźć linie, w których znajduje się dokładnie jedna kropka, możemy użyć wyrażenia ^[^.]*\.[^.]*$. Użycie ^ na początku i $ na końcu oznacza, że zawsze będzie próba dopasowania całej linii. Następnie [^.]* oznacza dowolny ciąg znaków nie zawierający kropki, a \. oznacza wystąpienie kropki (trzeba użyć \, bo . jest znakiem specjalnym).

Aby znaleźć linię, która zaczyna się od dowolnej liczby spacji, liczby, później kropki, a następnie spacji i dużej litery, używamy wyrażenia ^ *[0-9][0-9]*\. *[A-Z]. Za pomocą tego wyrażenia zostaną znalezione na przykład

1. Wstęp
   2.Wprowadzenie
 13.   Zakończenie

a nie zostaną znalezione takie linie

1 Trafienie
 3. echo - komenda wbudowana
     4 . Punkt czwarty
   2006
^ 1. Wstęp

Oprócz znaczników rozpoznających początek i koniec linii, mamy też szereg znaczników rozpoznających końce słowa:

\<	znacznik mówiący, że w tym miejscu zaczyna się nowe słowo
\>	znacznik mówiący, że w tym miejscu kończy się słowo
\b	znacznik mówiący, że w tym miejscu jest krawędź słowa (nie zaczyna ani nie kończy się żadne słowo)
\B	znacznik mówiący, że w tym miejscu nie znajduje się krawędź słowa

Dokładne definicje, co to jest brzeg słowa, są nieprzyjemnie skomplikowane i je pominiemy. Przyjrzyjmy się przykładowi. Dla frazy Jola jest lojalna następujące wyrażenia zostaną dopasowane do wycinka tej frazy:

• \<jest\>
• \bjest\b
• \Best\b
• \Bes\B

a poniższe wyrażenia nie zostaną dopasowane:

• \<est\>
• \best\b
• \Bes\b
• \>jest\<

Alternatywa

Jeśli chcemy, aby był rozpoznawany jeden z dwóch możliwych napisów, to możemy użyć alternatywy |, na przykład jeden|dwa rozpozna albo słowo jeden albo słowo dwa. Operator | może mieć jako argumenty też inne wyrażenia, na przykład [0-9]*|[a-z]*|[A-Z]* rozpoznaje albo ciąg cyfr, albo ciąg małych liter, albo ciąg dużych liter.

Priorytety i nawiasowanie

Największy priorytet mają operatory powtórzenia. Jeśli chcemy mieć wyrażenie oznaczające powtórzenie większej liczby elementów, to możemy zrobić to poprzez stosowanie nawiasów ( ... ). Na przykład wyrażenie ([a-z][a-z])* oznacza ciąg składający się z parzystej liczby małych literek.

Najmniejszy priorytet ma alternatywa. Jeśli chcemy wpisać wyrażenie, które rozpoznaje wszystkie słowa, które rozpoczynają się od Ta lub od Do, to nie możemy napisać Ta|Do[a-z]*, gdyż takie wyrażenie rozpoznaje albo słowo Ta, albo ciąg literek zaczynający się od Do. Z pomocą przychodzą nawiasy: (Ta|Do)[a-z]*.

Wyrażenia podstawowe i rozszerzone

Wyrażenia regularne dzielimy na podstawowe i rozszerzone. W wyrażeniach podstawowych znaki ?, +, {, |, (, ) nie mają specjalnego znaczenia, zamiast nich trzeba używać wersji z backslashem: \?, \+, \{, \|, \(, \). W wyrażeniach rozszerzonych możemy stosować wszystkie wymienione znaki specjalne.

Rozróżnienie takie powstało na skutek różnych narzędzi i zachowania kompatybilności między nimi. Niektóre narzędzia używają składni z podstawowymi, a niektóre z rozszerzonymi wersjami wyrażeń regularnych. Przy omawianiu poszczególnych komend powiemy, które używają jakiej składni.

Przykłady wykorzystania

grep

Polecenie grep jest podstawowym narzędziem do wyszukiwania wzorca w tekście z użyciem wyrażeń regularnych. grep używa podstawowych wyrażeń. Jeśli jest potrzeba użycia rozszerzonych wyrażeń można użyć wtedy w zastępstwie polecenia egrep.

Podstawowe użycie, to

grep wzorzec

gdzie wzorzec jest wyrażeniem regularnym. Wzorzec jest wyszukiwany w standardowym wejściu i na standardowe wyjście są wypisywane linie zawierające wzorzec.

Można podać plik lub pliki jako argumenty:

grep wzorzec plik

lub

grep wzorzec plik1 plik2 ...

W przypadku jednego pliku, działanie jest takie samo jak bez argumentów, z tą różnicą, że dane są czytane z pliku, a nie ze standardowego wejścia.

W wersji z wieloma plikami wzorzec wyszukiwany jest w każdym pliku. Wyświetlane są linie zawierające wystąpienie wzorca poprzedzone nazwą pliku, w którym został on znaleziony.

Ponadto jest wiele opcji kontrolujących sposób szukania i wyświetlane informacje. Omówimy najprzydatniejsze z nich.

-e wzorzec

alternatywny sposób podania wzorca; przydatny, gdy wyrażenie regularne może zaczynać się od znaku -

-i

ignoruje rozróżnianie wielkich liter,

-c

zlicza tylko liczbę wystąpień wzorca,

-w

dopasowuje wzorzec tylko do całych słów,

-x

dopasowuje wzorzec tylko do całych linii,

-v

odwraca sens dopasowania i wyszukuje tylko linie w których nie udało się dopasować wzorca,

-q

nic nie wypisuje na standardowe wyjście i kończy działania na pierwszym dopasowaniu; przydatne, gdy polecenie grep chcemy użyć jako warunku.

grep zwraca zero jako kod wyjścia, gdy wzorzec uda się znaleźć i wartość niezerową w przeciwnym przypadku. Można to wykorzystać w połączeniu z opcją -q w instrukcjach warunkowych. Na przykład

if grep -qw TODO opis_prac.txt; then
  echo "Zostało jeszcze coś do zrobienia"
fi

Jeśli chcemy z pliku usunąć linie, które pasują do wzorca możemy zrobić to w następujący sposób:

TMPFILE=/tmp/xyzabcd
cp plik $TMPFILE
grep -xv wzorzec $TMPFILE >plik
rm -f $TMPFILE

expr

Polecenie expr oprócz obliczania wyrażeń arytmetycznych ma też podstawowe operacje na łańcuchach znakowych. Szczególnie przydatny jest operator :. Jego składnia to

expr łańcuch : wzorzec

Wzorzec jest wyszukiwany na początku łańcucha (czyli tak jakby zawsze na początku wzorca stał ^). Jeśli zostanie on znaleziony, wypisywana jest liczba dopasowanych znaków. W przeciwnym razie liczba dopasowanych znaków wynosi 0.

Jeżeli we wzorcu były używane nawiasy \( i \), zwracany jest łańcuch dopasowany w tym podwyrażeniu.

Status wyjścia jest równy zero tylko wtedy, gdy do wzorca uda się dopasować niepusty ciąg znaków.

Oto kilka przykładów:

• Wyświetlenie rozszerzenia pliku znajdującego się na zmiennej plik:

expr "$plik" : ".*\.\([^.]*\)"

• Zmiana rozszerzenia z tar.gz na tgz pliku na zmiennej plik:

if expr "$plik" : ".*\.tar\.gz$"; then
  mv $plik `expr "$plik" : "\(.*\.\)tar\.gz"`tgz
fi

oczywiście if jest zbędny jeśli wiemy, że nazwa pliku na pewno kończy się na .tar.gz.

sed

Najprościej rzecz ujmując sed jest edytorem strumieniowym. Czyta ze standardowego wejścia lub z pliku, jeśli został podany jako argument, następnie wykonuje operacje podane w komendach edycyjnych i wynik wyrzuca zawsze na standardowe wyjście.

Najczęściej sed jest używany z komendą edycyjną postaci s/wzorzec/zamiennik/, gdzie wzorzec jest podstawowym wyrażeniem regularnym, a zamiennik jest łańcuchem znakowym jakim będzie zastąpiony znaleziony wzorzec. W łańcuchu zamiennik możemy używać specjalnych sekwencji odnoszących się do znalezionego tekstu. \n, gdzie n jest liczbą, oznacza łańcuch skojarzony z n-tą parą nawiasów \( ... \). Znak & kojarzy z całym znalezionym łańcuchem.

Na przykład, aby zamienić każdy ciąg wykrzykników w jeden wykrzyknik można użyć komendy s/!\+/!/:

bashtest@host:~$ echo 'Hej!! Hej!!!! Tutaj!' | sed 's/!\+/!/'
Hej! Hej!!!! Tutaj!
bashtest@host:~$

Domyślnie sed wykonuje zastąpienie tylko przy pierwszym skojarzeniu wzorca w danej linii. Aby szukał wszystkich skojarzeń należy dodać przyrostek g do komendy edycyjnej:

bashtest@host:~$ echo 'Hej!! Hej!!!! Tutaj!' | sed 's/!\+/!/g'
Hej! Hej! Tutaj!
bashtest@host:~$

Aby zamienić znak . na znak , we wszystkich liczbach zmiennopozycyjnych możemy użyć komendy

s/\([0-9]\+\)\.\([0-9]\+\)/\1,\2/g

Użyliśmy tutaj odnośników. \1 oznacza grupę cyfr przed . w znalezionym łańcuchu, a \2 oznacza grupę cyfr po ..

Do rozdzielania komendy s nie trzeba wcale używać znaku /, ale może to być dowolny wybrany znak. Na przykład komenda

s+C:\\+/mnt/win/+g

zamieni wszystkie wystąpienia C:\ na /mnt/win/.

sed może też służyć do filtrowania wejścia. Opcja -n powoduje, że domyślnie nic nie jest wypisywane. Trzeba dodać przyrostek p do komendy, aby wynik został wypisany. Na przykład

sed -n 's/[a-zA-Z0-9]/&/p' opis.txt

wypisze tylko te linie pliku opis.txt, które zawierają znak alfanumeryczny.

Ponadto sed posiada znacznie więcej różnych użytkowych funkcji. Można poprzedzić komendę adresem. Na przykład sed '20s/.../.../' zadziała tylko w 20 linii. Adresem może być numer linii, wyrażenie regularne albo zakres. Są też inne komendy, na przykład sed '/^#/d' usunie wszystkie linie, które zaczynają się od znaku #.

Ćwiczenia

1. Podaj wyrażenie regularne rozpoznające komentarz C: /* ... */.
   Rozwiązanie .

   /\*([^*]|(\*+[^*/]))*\*+/

2. Podaj wyrażenie regularne rozpoznające słowa, w których występuje przysta liczba wystąpień litery a.
   Rozwiązanie .

   [b-z]*(a[b-z]*a[b-z]*)*

3. ^* Podaj wyrażenie regularne, które rozpoznaje ciąg znaków składający się z parzystej liczby wystąpień znaku a i znaku b.

   Rozwiązanie .

   Siłowe:

   (a(bb)*(a|ba(a(bb)*a)*(a(bb)*ba|b))|b(aa)*(b|ab(b(aa)*b)*(b(aa)*ab|a)))*

   Prostsze:

   (aa|bb|(ab|ba)(aa|bb)*(ab|ba))*