Automaty i języki formalne
Wyrażenia regularne na przykładzie języka Perl
Zanim o Perlu...
Automatyczne przetwarzanie tekstu jest — skromnym zdaniem autora — najwygodniejsze w systemie Linux (i w innych systemach wywodzących się z Uniksa). Wynika to z niezwykle elastycznych mechanizmów powłoki, przede wszystkim przetwarzania potokowego.
Oto lista najważniejszych poleceń linuksowych związanych z przetwarzaniem tekstu:
- echo NAPIS - wypisuje podany napis (i znak końca wiersza),
- cat nazwa_pliku - wypisuje na ekranie zawartość pliku,
- head nazwa_pliku - wypisuje kilka pierwszych wierszy pliku,
- head -n N nazwa_pliku - wypisuje N pierwszych wierszy pliku,
- tail nazwa_pliku - wypisuje kilka ostatnich wierszy pliku,
- tail -n N nazwa_pliku - wypisuje N ostatnich wierszy pliku,
- less nazwa_pliku - pokazuje zawartość pliku, można przewijać używając np. PgDown/PgUp,
- less -S nazwa_pliku - jak wyżej, nie zawija wierszy,
- wc nazwa_pliku - zlicza wiersze, wyrazy, bajty,
- sort nazwa_pliku - sortuje wiersze alfabetycznie,
- sort -k 1rn nazwa_pliku - sortuje wiersze numerycznie (n) w odwróconej kolejności (r) wg pierwszej kolumny (1),
- uniq nazwa_pliku - usuwa powtarzające się wiersze (jeśli są obok siebie),
- uniq -c nazwa_pliku - jak wyżej, dodatkowo wypisuje liczbę powtórzeń przy każdym wierszu.
- shuf nazwa_pliku - wypisuje wiersze w losowej kolejności,
- egrep REGEXP - wypisuje wiersze pasujące do zadanego wyrażenia regularnego (my raczej będziemy używać Perla, p. dalej)
Większość poleceń domyślnie używa standardowego wejścia, jeśli pominięto nazwę pliku. Wyniki wypisywane są na standardowe wyjście (chyba że użyto przekierowania > nazwa_pliku). Oznacza to, że polecenia można łączyć w potok używając znaku |, przykłady:
- head -n 100 | sort - wypisuje pierwsze sto wierszy w kolejności alfabetycznej,
- sort | uniq | wc - zlicza wiersze bez powtórzeń,
- tail -n 5 | shuf - wyświetla 5 ostatnich wierszy z pliku w losowej kolejności,
- shuf | head -n 5 - wyświetla 5 losowych wierszy z pliku,
- sort | uniq | shuf | head -n 10 - wyświetla 10 losowych wierszy bez powtórzeń,
- sort | uniq -c | sort -k 1rn - tworzy listę frekwencyjną wierszy, tzn. wyświetla wiersze według liczby powtórzeń począwszy od najczęstszych.
skąd potok pobiera dane?
Potok pobiera dane ze standardowego wejścia, domyślnie po prostu czeka na wpisanie danych, np. jeśli wydamy polecenie:
head -n 5 | shuf
będzie można wprowadzać kolejne wiersze, aż nie naciśniemy CTRL+d, w tym momencie powłoka wypisze pięć ostatnich wierszy w losowej kolejności i zakończy wykonywanie potoku.
Jeśli chcemy, aby potok działał na konkretnym pliku, powiedzmy blabla.txt, jego nazwa powinna pojawić się przy pierwszym poleceniu potoku:
head -n 5 blabla.txt | shuf
Można użyć też przekierowania:
head -n 5 < blabla.txt | shuf
Albo dołożyć do potoku polecenie cat:
cat blabla.txt | head -n 5 | shuf
Ćwiczenie 1 Napisać potok, który wypisze jeden losowy wiersz.
Ćwiczenie 2 Napisać potok, który wypisze ostatni wiersz wg kolejności alfabetycznej.
jeszcze kilka wskazówek...
- klawisze strzałka w górę/w dół przywołują wcześniejsze polecenia,
- można napisać część nazwy pliku i nacisnąć klawisz TAB — powłoka spróbuje odgadnąć nazwę pliku
- CTRL-R pozwala wyszukiwać "online" polecenia w historii poleceń,
- dobrze zmienić sobie kolory terminala na czarne tło/białe znaki...
- ... i powiększyć czcionkę,
- warto zaprzyjaźnić się z programem Midnight Commander (polecenie mc), efektywnością bije na głowę wszelkie okienkowo-myszowe programy do zarządzania plikami i katalogami,
- najszybsza przeglądarka to links...
Wikipedia
Proponuję przeprowadzać eksperymenty na zrzucie z Wikipedii (http://meta.wikimedia.org/wiki/Data_dumps). Przygotowałem plik tekstowy składający się z wszystkich artykułów polskiej Wikipedii. Jest on dostępny pod adresem http://150.254.77.22/~daut/plwiki.txt.bz2. Plik trzeba pobrać, używając np. programu wget:
wget 'http://150.254.77.22/~daut/plwiki.txt.bz2'
(Uwaga! Proszę sobie ściągnąć do katalogu /media/Poligon, żeby nie zapchać sobie konta.)
Plik jest skompresowany programem bzip2. Aby go rozpakować, należy użyć następującego polecenia:
bzip2 -d plwiki.txt.bz2
Ćwiczenia 3 Sprawdź, z ilu wierszy składa się zrzut polskiej Wikipedii.
Ćwiczenia 4 Z ilu unikatowych (niepowtarzających się) wierszy składa się zrzut polskiej Wikipedii?
Ćwiczenia 5 Gdyby posortować alfabetycznie Wikipedię, jaki wiersz byłby ostatni?
lista polskich nazwisk
Innym ciekawym plikiem jest lista frekwencyjna wszystkich polskich nazwisk. Lista jest dostępna pod adresem http://150.254.77.22/~daut/nazwiska.txt. W każdym wierszu jest inne nazwisko, przed nazwiskiem podano liczbę osób o danym nazwisku.
Ćwiczenia N1 Sprawdź, ile jest różnych polskich nazwisk.
Podstawy Perla
Perl jest popularnym językiem programowania, mającym wiele zastosowań m.in.: przetwarzanie plików tekstowych, tworzenie narzędzi administratora systemu, programowanie stron WWW, obsługa baz danych.
uruchamianie
Perl jest językiem interpretowanym (skryptowym), aby wykonać program potrzebny jest program-interpreter. Interpreter Perl jest standardowo dostępny w systemach wywodzących się z Uniksa (np. w Linuksie).
Zwykle program perlowy (skrypt) zapisywany jest w osobnym pliku, my będziemy wywoływać Perla w prostszy sposób, bezpośrednio z wiersza poleceń, oto przykład:
perl -e 'print "Hello world!\n"'
Ćwiczenia 6 Kurs dolara kanadyjskiego wynosi 2.67 złotego. Policz, używając Perla, ile dostaniesz złotych za 290 dolarów kanadyjskich.
Wyjaśnienie:
- polecenie perl wywołuje interpreter Perla,
- opcja -e (od ang. explicit) oznacza, że program (skrypt) nie będzie wczytywany z osobnego pliku, lecz zostanie wczytany z argumentu polecenia
- print "Hello world!\n" jest tym skryptem,
- perlowa funkcja print wypisuje podane argumenty na ekranie,
- \n oznacza koniec wiersza.
przetwarzanie pliku tekstowego w Perlu
Aby przetwarzać plik tekstowy korzystając ze skryptu zapisanego w wierszu poleceń, najprościej użyć dodatkowej opcji -n. Opcja ta sprawia, że Perl niejawnie wczytuje każdy wiersz ze standardowego wejścia, zapisuje taki wiersz do zmiennej specjalnej $_ (wszystkie zmienne w Perlu zaczynają się od znaku $) i dla każdego wiersza wywołuje podany skrypt. Oto przykład programu działającego jak cat (po prostu przepisuje wejście na wyjście):
perl -ne 'print $_'
Wiele funkcji perlowych działa w ten sposób, że jeżeli pominiemy argument, działają one domyślnie na zmiennej specjalnej $_, możemy więc równoważnie napisać:
perl -ne 'print'
Inna ciekawa zmienna specjalna to $., jest w niej przechowywany numer bieżącego wiersza. Na przykład poniższy skrypt ponumeruje wiersze:
perl -ne 'print "$. $_"'
Zmiennej $. możemy użyć do prostego filtrowania wejścia, np. poniższy skrypt wypisze czterdziesty drugi wiersz wejścia:
perl -ne 'print if $. == 42'
Wyjaśnienie:
- słowo kluczowe if i warunek może w Perlu następować po instrukcji,
- == to operator równości numerycznej, większość operatorów w Perlu ma taki sam kształt i sens jak w C/Javie.
Ćwiczenie 7 Napisać skrypt perlowy, który będzie działał tak samo jak head -n 5.
Znaki końca wiersza
Należy pamiętać (niekiedy może to mieć znaczenie), że przy normalnym wczytywaniu wiersza wczytywany jest też znak końca wiersza, stąd np. dla polecenia:
echo "foo" | perl -ne 'print $_, length($_)'
na ekranie zostanie wypisane:
foo 4
($_ zawiera znak końca wiersza, więc 4 znajdzie się w osobnym wierszu; 4 a nie 3, bo length - funkcja, która liczy długość napisu - bierze pod uwagę znak końca wiersza).
Znak końca wiersza najprościej można usunąć za pomocą polecenia chomp (domyślnie działa na $_), np. dla polecenia:
echo "foo" | perl -ne 'chomp; print $_, length($_)'
na ekranie zostanie wypisane:
foo3
Unicode (UTF8)
Aby Perl przy wczytywaniu i zapisywaniu używał kodowania UTF8 (np. dla polskich znaków diakrytycznych), należy użyć opcji -CS.
Jeśli w samym kodzie perlowym (np. w argumencie opcji -e) używamy kodowania UTF8, musimy użyć specjalnej instrukcji use utf8; na początku kodu.
Wyrażenia regularne
Perl w dużym stopniu zawdzięcza swoją popularność potężnemu mechanizmowi wyrażeń regularnych (ang. regular expression, w skrócie regexp). Perlowe wyrażenia regularne są podobne do tzw. rozszerzonych Posiksowych wyrażeń regularnych, są jednak pewne różnice.
konstrukcje specjalne reprezentujące pojedyncze znaki
| konstrukcja | co reprezentuje |
|---|---|
| . | dowolny znak (z wyjątkiem znaku końca wiersza) |
| \w | litery, cyfry i znak _ |
| \W | znak niebędący literą, cyfrą ani znakiem _ |
| \s | znak "biały" (spacja i znak tabulacji) |
| \S | znak niebędący znakiem "białym" |
| \d | cyfra |
| \D | znak niebędący cyfrą |
| \n | znak nowego wiersza |
| \t | znak tabulacji |
| \xXY | znak o kodzie szesnastkowym XY |
| \znak specjalny | znak specjalny rozumiany dosłownie |
początek i koniec napisu
Normalnie wyrażenie regularne służy do wyszukiwania pasującego podciągu. Jeśli chcemy "zakotwiczyć" wyrażenie regularne na początku lub na końcu tekstu, należy użyć specjalnych konstrukcji:
| konstrukcja | znaczenie |
|---|---|
| ^ | początek napisu |
| $ | koniec napisu (przy czym znaki końca wiersza na końcu napisu nie są brane pod uwagę) |
klasa znaków
Fragment wyrażenia zaczynający się znakiem [ i kończący się znakiem ] reprezentuje klasę znaków. Przykłady:
| klasa znaków | jakie znaki | uwagi |
|---|---|---|
| [def] | znak a, b lub c | |
| [aąeęioóuyAĄEĘIOÓUY] | polska samogłoska | |
| [IVXLCDM] | cyfra rzymska | |
| [^qvx] | wszystkie znaki z wyjątkiem znaków q, v i x | znak ^ na początku klasy oznacza dopełnienie (negację) |
| [0-9] | to samo co \d | X-Y oznacza wszystkie znaki od X do Y |
| [a-zA-Z0-9_] | to samo co \w |
postać wyrażenia regularnego
Zwykle wyrażenie regularne jest w Perlu ujęte w parę znaków /. Alternatywnie można używać konstrukcji mXwyrażenieX, gdzie X to pewien znak (może być nawias otwierający, wówczas wyrażenie kończy odpowiedni nawias zamykający).
przykłady wyrażeń
| wyrażenie regularne | co reprezentuje |
|---|---|
| /dom/ | dowolny napis zawierający podnapis dom |
| /^\d\d-\d\d\d$/ | kod pocztowy |
| m|^\d\d-\d\d\d$| | to samo co wyżej |
| m<^\d\d-\d\d\d$> | to samo co wyżej |
| /\S$/ | napis, którego ostatni znak nie jest spacją (ani tabulacją) |
użycie wyrażeń regularnych w programie
Do działania na wyrażeniach regularnych służy operator =~. Poniżej podano przykłady użycia:
| konstrukcja | znaczenie |
|---|---|
| $kod =~ /^61-\d\d\d/ | wyrażenie jest prawdziwe, jeśli wartość zmiennej $kod pasuje do podanego wyrażenia |
| if ($kod =~ /^61-\d\d\d/) { print "To Poznań\n";} | przykład użycia w instrukcji warunkowej |
| if (/X/) { print "Jest X\n"} | to samo co if ($_ =~ /X/) { print "Jest X\n"} - wyrażenie domyślnie stosuje się do zmiennej $_ |
| $napis =~ /^ab/i | to samo co $napis =~ /^[aA][bB]/i - dodatkowy specyfikator i oznacza, że wielkość liter ma nie być brana pod uwagę |
| if ($napis !~ /kot/) | to samo co if (not $napis =~ /kot/) - !~ to negacja operatora =~ |
| while ($napis =~ /\d/g) { print "Cyfra: $&\n";} | użycie specyfikatora g ("g" jak "globalny") - pętla zostanie wywołana tyle razy, ile jest w niej podnapisów pasujących do wzorca, zmienna $& zawiera dopasowany za każdym razem fragment |
My będziemy stosować wyrażenie regularne do zmiennej $_ możemy więc operator =~ pominąć. Na przykład, jeśli chcemy wypisać wiersze z Wikipedii zawierające napis Czesio, możemy napisać:
perl -ne 'print $_ if $_ =~ /Czesio/' < plwiki.txt
lub krócej:
perl -ne 'print if /Czesio/' < plwiki.txt
Ćwiczenie 8 Lech Poznań czy Legia Warszawa? Co częściej występuje w Wikipedii?
Jeśli chcemy szybko przetestować wyrażenie regularne możemy użyć następującej konstrukcji:
perl -e 'print "PASUJE!\n" if "1234" =~ /^\d\d\d\d$/'
Ćwiczenie N2 Ile jest osób noszących takie nazwisko jak Ty?
Ćwiczenie N3 Ile jest nazwisk zakończonych na ski, ile na cki, ile na owy, ile na icz, ile na szwili?
Ćwiczenie N4 Jakie jest pierwsze nazwisko w kolejności alfabetycznej? Jakie ostatnie?
Ćwiczenie 9 Napisać wyrażenie, które reprezentuje liczbę pięciocyfrową (w systemie dziesiętnym).
Ćwiczenie 10 Napisać wyrażenie, które reprezentuje liczbę czterocyfrową zapisaną w systemie szesnastkowym.
Ćwiczenie 11 Napisać wyrażenie, które reprezentuje numer dowodu osobistego.
Ćwiczenie 12 Napisać skrypt wypisujący wiersze Wikipedii zaczynające się od a więc.
Ćwiczenie 13 Napisać wyrażenie, które reprezentuje pięciocyfrową liczbę podzielną przez 2.
Ćwiczenie 14 Napisać wyrażenie reprezentujące napis, którego przedostatnim znakiem jest znak \.
Ćwiczenie 15 Napisać skrypt wypisujący wiersze Wikipedii zawierające numer NIP.
Ćwiczenie 16 Na wyjściu wypisz te wiersze pobrane z wejścia, które nie zawierają spacji.
Ćwiczenie 17 Na wyjściu wypisz te wiersze pobrane z wejścia, które zawierają znak niebędący spacją.
kwantyfikatory
Kwantyfikatory specyfikują, ile razy dany znak (lub szerzej - fragment) powinien wystąpić w napisie. Poniżej podano listę niektórych kwantyfikatorów:
| kwantyfikator | znaczenie |
|---|---|
| * | dowolna liczba razy (w tym zero) |
| + | dowolna niezerowa liczba razy |
| ? | raz lub ani razu |
| {n} | dokładnie n razy |
| {n,} | co najmniej n razy |
| {n,m} | co najmniej n razy, ale nie więcej niż m razy |
użycie nawiasów
Nawiasy okrągłe pełnią dwie funkcje: po pierwsze pozwalają grupować części wyrażenia regularnego , po drugie fragmenty napisu reprezentowane przez fragmenty wyrażenia regularnego są "przechwytywane" i można się do nich dalej odwoływać używając specjalnych zmiennych $1, $2,... ($1 oznacza fragment napisu przechwycony przez pierwsze nawiasy).
Przykład użycia (nawiasów i kwantyfikatorów):
$naglowek = "Zielona Góra, 2003-03-08";
if ($naglowek =~ /^([^,]+),\s+(20\d\d)-(\d\d)-(\d\d)$/) {
$miasto = $1;
$rok = $2;
$miesiac = $3;
$dzien = $4;
print "miasto: $miasto\n";
print "rok: $rok\n";
}
else {
print "Tutaj nie możemy trafić, bo przecież napis pasuje do wzorca!\n";
}
alternatywa
Znak specjalny | w wyrażeniu regularnym oznacza alternatywę. Zwykle używany jest z nawiasami okrągłymi. Np. wyrażenie regularne /(ASIA|BASIA|KASIA)/ oznacza ASIA, BASIA lub KASIA.
Ćwiczenie 18 Zapisz powyższe wyrażenie (/(ASIA|BASIA|KASIA)/) bez użycia nawiasów i znaków |.
Ćwiczenie 19 DNA człowieka to sekwencja czterech możliwych zasad oznaczonych literami A, T, G i C. Napisz wyrażenie reprezentujące sekwencję DNA. Znajdź w Wikipedii wiersze zawierające takie napisy.
Ćwiczenie 20 Napisać wyrażenie reprezentujące numer PESEL. Wyszukaj w Wikipedii wiersze zawierające numer PESEL.
Ćwiczenie 21 Zapisz wyrażenie, które reprezentuje liczbę zapisaną szesnastkowo.
Ćwiczenie 22 Napisać wyrażenie reprezentujące datę w formacie dzień.miesiąc.rok (np. 24.12.2011).
Ćwiczenie 23 Napisać wyrażenie reprezentujące czas w formacie godzina:minuta.sekunda (np. 15:30.12).
Ćwiczenie 24 Napisać wyrażenie reprezentujące numer tablicy rejestracyjnej.
Ćwiczenie 25 Napisać skrypt wypisujący wulgaryzmy zawarte w Wikipedii. Zaproponować wyrażenie regularne wyłapujące wulgaryzmy (w miarę możliwości także "zaciemnione", np. przy użycia zamiany "w" na "v"), tak aby "niewinne" słowa nie były wyłapywane. Za najciekawszą propozycję - 3 punkty.
Ćwiczenie 26 Jaki jest najdłuższy wyraz użyty w zrzucie Wikipedii? Kto pierwszy znajdzie najdłuższy taki sensowny polski wyraz, otrzyma 3 punkty.
Ćwiczenie 27 Jaki jest najdłuższy wyraz użyty w Wikipedii zawierający co najwyżej 4 samogłoski? Kto pierwszy znajdzie najdłuższy taki sensowny polski wyraz, otrzyma 2 punkty.
Ćwiczenie 28 Wyszukaj w Wikipedii kwoty wyrażone w dolarach.
Ćwiczenie 29 Zapisz wyrażenie, które reprezentuje identyfikator w C (czyli dowolny ciąg liter, liczb i znaków podkreślenia nie zaczynający się liczbą).
Ćwiczenie 30 Zapisz wyrażenie, które reprezentuje datę w formacie 5 marca 2003. Wypisz wiersze z Wikipedii zawierające takie daty.
Ćwiczenie 31 Zaproponuj wyrażenie, które reprezentuje adres poczty elektronicznej. Czy Wikipedia zawiera adresy e-mailowe?
Ćwiczenie 32 Na wejściu podawane są ścieżki do plików (w standardzie dosowym lub uniksowym). Napisać program, który na wyjściu wypisze same nazwy plików (bez ścieżki i bez rozszerzenia). Np. jeśli na wejściu jest:
C:\WINDOWS\SYSTEM\OBRAZEK.BMP /usr/bin/perl ../muzyka.mp3 krajobraz.gifto na wyjściu powinno pojawić się:
OBRAZEK perl muzyka krajobraz
Ćwiczenie N5 Jakie jest najkrótsze polskie nazwisko?
Ćwiczenie N6 Jakie jest najdłuższe polskie nazwisko (bez spacji i minusów)? Kto pierszy znajdzie to nazwisko, otrzyma 1 punkt
Ćwiczenie N7 Jakie nazwisko zawiera najwięcej znaków diakrytycznych Kto pierszy znajdzie to nazwisko, otrzyma 2 punkty
operator s///
Operator s/W/N/ zamienia pierwsze wystąpienie podnapisu pasującego do wyrażenia W napisem N. Jeśli chcemy zastąpić wszystkie podnapisy pasujące do wyrażenia używamy konstrukcji s/W/N/g. Po prawej stronie można używać zmiennych $1, $2... (odwołań do fragmentów przechwyconych w nawiasach).
Przykłady użycia:
| $zdanie =~ s/błond/błąd/g | każde wystąpienia napisu błond w zmiennej $zdanie zamienia na błąd |
| $napis =~ s/ +/ /g; | wszystkie ciągi spacji zastępuje pojedynczą spacją |
| $data =~ s/^(\d\d)\/(\d\d)\/(\d\d\d\d)$/$3-$2-$1/ | zamienia datę z formatu 21/03/2002 na 2002-03-21 |
Ćwiczenie 35 Napisać skrypt, który usuwa "ogonki" polskich znaków diakrytycznych z tekstu podanego na wejściu.
Ćwiczenie 36 Napisać skrypt, który każde wystąpienie daty w formacie 12 maja 2011 zastąpi datą w postaci 12 maja br. (jeśli rok=2011).
funkcja split
Funkcja split(/W/, $napis) dzieli napis na pola, przy czym separatorami są podnapisy pasujące do wyrażenia regularnego /W/. Funkcja zwraca listę (tablicę) pól.
Ćwiczenie 37 Napisać funkcję, która dla pełnej nazwy pliku (ścieżki) danej jako argument zwraca listę nazw kolejnych katalogów składających się na nazwę pliku. Ścieżka może być podana w konwencji dosowej lub uniksowej. Np. dla argumentu /usr/bin/perl funkcja powinna zwrócić listę złożoną z dwóch elementów: usr i bin.