/Cw5

TI:WTBD/Ćwiczenia 5

Konstruujemy przykładowe wyrażenia regularne.

Przykłady uruchamiamy/sprawdzamy za pomocą polecenia egrep (lub grep -E - na jedno wychodzi).

Częstą trudnością w konstrukcji wyrażeń regularnych w praktyce jest uwzględnienie kontekstu, w jakim szukane napisy mogą się pojawiać -- tj. tego, jak je wyodrębnić z ,,tła". Tutaj na razie pomińmy tę trudność, która ma znaczenie dla paru pierwszych przykładów: np. 69 jako odrębne słowo zdecydowanie wygląda na liczbę, natomiast Hoza69 jest legalnym identyfikatorem w Pythonie, i w kodzie może pełnić rolę nazwy zmiennej lub klasy itp.

1. podaj wzorzec dla zapisu liczby całkowitej lub zmiennoprzecinkowej (bez wykładnika)

   To nie jest takie bardzo proste. Kierujmy się postacią zapisu literalnych liczb w Pythonie: np. 1. i .1 są poprawnymi zapisami liczb zmiennoprzecinkowych.

2. podaj wzorzec dla zapisu czasu w postaci HH:MM, tzn. od 00:00 do 23:59 -- ma nie akceptować niepoprawnych godzin, takich jak 25:63

   ^([01][0-9]|2[0-3]):[0-5][0-9]$

3. podaj wzorzec dla zapisu daty w postaci dd-mm-rrrr, z uwzględnieniem dat z wieku 20 i 21. W pierwszym podejściu -- niech nie dopuszcza dni > 31 ani miesięcy > 12.

   Zaobserwuj, jak to się komplikuje gdy próbujesz uwzględnić różne długości miesięcy. Uwzględnienie różnicy pomiędzy latami przestępnymi a nieprzestępnymi to już zdecydowanie nie jest odpowiednie zastosowanie dla wyrażeń regularnych.

4. w strumieniu tekstowym zlicz linijki nie zawierające znaków niepustych; wyeliminuj (pomiń) takie linijki. Znajdź dwa różne sposoby.

   Można albo wyróżnić te linijki żądając, by zawierały choć jeden znak nie będący spacją albo tabulacją:

   egrep '[^[:blank:]]' ...

   albo użyć wyrażenia, do którego pasują linijki zawierające co najwyżej same znaki puste, i odwrócić działanie egrep używając opcji:

   egrep -v '^[[:blank:]]*$' ...

   Uwaga: egrep niestety nie interpretuje standardowych sekwencji np. \t jako oznaczającej kod tabulacji, itd. Na szczęście w Pythonie one działają.

5. z strumienia rekordów mapy passwd wyodrębnij rekordy tych osób, w których podane jest drugie imię. Jaką część one stanowią?

   Nie ma na to ścisłych reguł, ale często stosowana jest konwencja, że piąte pole (opisowe, określane też nazwą GECOS) powinno zawierać Imie Drugieimie Nazwisko właściciela konta (z tym że nie każdy ma drugie imię), i ewentualnie po przecinku jakieś informacje dodatkowe typu nr gabinetu, telefon służbowy itp. W pierwszym kroku należy odrzucić rekordy, które nie są zgodne z tym szablonem; są to najprawdopodobniej konta w jakimś sensie ,,funkcyjne".

   Jako wzorzec wyróżniający rekordy osób wg. powyższego kryterium można przyjąć

   ^([^:]*:){4}[A-Z][a-z]+ ([A-Z][a-z]+ )?[A-Z][a-z]+[,:]

   (zakładamy tu, że nie należy raczej się spodziewać imion czy nazwisk 1-literowych -- jeśli w miejscu na imię czy nazwisko znajduje się tylko jedna litera, to najprawdopodobniej jest ona czymś innym, i takie konto odrzucamy). Z kolei następujący wzorzec już narzuca wymaganie, by drugie imię występowało:

   ^([^:]*:){4}[A-Z][a-z]+ [A-Z][a-z]+ [A-Z][a-z]+[,:])

6. napisz wyrażenie regularne opisujące konwencję nazw (loginów) kont studenckich na FUW; ustalić, ile kont w passwd nie spełnia tej konwencji, oraz ile z nich ma foldery domowe poza katalogiem mającym public jako drugi człon ścieżki.

   Konwencja o której mowa wyraża się wzorcem

   ^[a-z]{2}[0-9]{6}$

   (chodzi tu o sam login, nie o rekord passwd). Aby policzyć konta nie przestrzegające tej konwencji, należy użyć polecenia

   egrep -v '^[a-z]{2}[0-9]{6}:' | wc -l

   natomiast aby policzyć te, które ponadto mają foldery domowe poza katalogiem public:

   egrep -v '^[a-z]{2}[0-9]{6}:' |egrep -v '^([^:]*:){5}[^:]*/public/'

7. w liście słów angielskich znajdź wszystkie palindromy 6-literowe i 7-literowe

   6-literowe: ^(.)(.)(.)\3\2\1$

   7-literowe: ^(.)(.)(.).\3\2\1$

   Zauważmy, że nie ma sposobu, by za pomocą wyrażenia regularnego zapisać warunek, że napis jest palindromem (niezależnie od jego długości). Co gorsza, wzorce egrep-a dopuszczają tylko do dziewięciu referencji wstecznych (w Pythonie -- do 99). Natomiast bez korzystania z wyrażeń regularnych bardzo łatwo jest napisać program poszukujący palindromów. Proszę napisać program znajdujący wszystkie palindromy w pliku słów i nie korzystający z wyrażeń regularnych.

   W Linuxie listę słów można zazwyczaj znaleźć w folderze /usr/share/dict, może tam być parę list odpowiadających różnym językom.

8. w liście słów angielskich znajdź wszystkie takie, gdzie druga litera to x, a ostatnia i pierwsza są takie same.

   ^(.)x.*\1$

   Ciekawe, że w pliku /usr/share/dict/words na moim komputerze wszystkie słowa pasujące do tego wzorca zaczynają się na literę e -- jest ich nie tak mało, bo 91.

Ad. palindromy:

• wersja simple

#! /usr/bin/python

from sys import argv

for name in argv[1:]:
    for line in open(name):
        word = line.strip()
        if len(word) > 2 and word == word[::-1]:
            print word

• wersja sophisticated

#! /usr/bin/python
from sys import argv
from itertools import chain

files = (open(name) for name in argv[1:])
lines = chain.from_iterable(files)
words = (l.strip() for l in lines)
palindromes = (word for word in words 
                   if len(word) > 2 and word == word[::-1])

for w in palindromes: print w

Żądanie, by palindrom miał długość co najmniej 3 jest dość arbitralne. Zauważmy jednak, że każdy wyraz 1-literowy jest palindromem, a każdy palindrom 2-literowy składa się z 2 identycznych liter -- są więc ,,mało interesujące".