ROZDZIAŁ 1.
Wyrażenia regularne
Brian Kernighan
Wyrażenia regularne to notacje służące do opisu wzorców tekstowych. Tworzą one w efekcie specjalistyczny język do dopasowywania wzorców. Mimo że istnieje niezliczona liczba możliwości, wszystkie z nich opierają się na jednym założeniu, że większość znaków we wzorcu dokładnie pasuje do ich wystąpień. Są jednak metaznaki o specjalnym znaczeniu. Na przykład symbol * oznacza jakiegoś rodzaju powtórzenia, a zapis [...] — którykolwiek znak ze zbioru zawartego w nawiasach.
W praktyce większość wyszukiwań w programach takich jak edytory tekstowe dotyczy konkretnych słów. W związku z tym wyrażenia regularne często są całymi łańcuchami, jak druk, który może zostać dopasowany do słów drukuj, wydruk albo papier do drukarki. W tak zwanych symbolach wieloznacznych, używanych do określania nazw plików w systemach takich jak Unix i Windows, symbol * oznacza dowolną liczbę znaków. A zatem wzorzec *. c pasuje do wszystkich plików, których nazwa kończy się ciągiem . c. Istnieje bardzo wiele wariantów wyrażeń regularnych, nawet w kontekstach, w których mogą wydawać się takie same. Wyczerpującym źródłem wiedzy na ten temat jest książka Wyrażenia regularne autorstwa Jeffreya Friedla[1].
Wyrażenia regularne wynalazł Stephen Kleene w połowie lat 50. ubiegłego stulecia jako notację do automatów skończonych. W rzeczywistości są one równoznaczne z automatami skończonymi, biorąc pod uwagę to, co reprezentują. W programie pojawiły się po raz pierwszy w połowie lat 60. Użył ich Ken Thompson w swojej wersji edytora tekstu QED. W 1967 roku programista ten złożył podanie o patent mechanizmu szybkiego dopasowywania tekstu na podstawie wyrażeń regularnych. Patent został mu przyznany w 1971 roku i był jednym z pierwszych patentów dotyczących oprogramowania[2].
Wyrażenia regularne zostały przeniesione z edytora QED do uniksowego edytora o nazwie ed, a następnie do charakterystycznego dla tego systemu narzędzia o nazwie grep utworzonego przez Thompsona na bazie edytora ed. Dzięki tym często używanym programom wyrażenia regularne stały się znane w całym wczesnym środowisku uniksowym.
Pierwotny mechanizm dopasowujący Thompsona był bardzo szybki, ponieważ łączył w sobie dwie niezależne idee. Pierwsza z nich to generowanie instrukcji maszynowych w locie podczas dopasowywania, dzięki czemu odbywało się ono z prędkością maszyny, a nie interpretacji. Druga polegała na przenoszeniu dalej wszystkich możliwych dopasowań na każdym etapie, dzięki czemu nie trzeba było wracać w poszukiwaniu alternatywnych potencjalnych dopasowań. W późniejszych edytorach tekstu pisanych przez Thompsona, takich jak ed, w kodzie dopasowującym był stosowany prostszy algorytm, który nawracał w razie konieczności. Teoretycznie jest to wolniejsza metoda, ale w praktyce znajdowane wzorce rzadko wymagały nawracania. Dzięki temu algorytmy ed i grep oraz kod były wystarczająco wydajne dla większości zastosowań.
W następnych algorytmach dopasowujących, jak egrep i fgrep, dodano bardziej rozbudowane klasy wyrażeń regularnych i skoncentrowano się na szybkim wykonywaniu bez względu na wzorzec. Bardziej wyszukane wyrażenia regularne stały się popularne i zostały włączone nie tylko do bibliotek w języku C, ale także wcielone w składnię języków skryptowych, takich jak Awk i Perl.
Programowanie w praktyce
W 1998 roku razem z Robem Pike’em pisaliśmy książkę pod tytułem Lekcja programowania[3]. Jej ostatni rozdział zawierał zbiór przykładów, kiedy dobra notacja prowadzi do powstania lepszych programów i do lepszego programowania. Znalazły się tam między innymi użycie prostych specyfikacji danych (na przykład printf) i generowanie kodu z tabel.
Ze względu na nasze uniksowe korzenie i prawie trzydzieści lat doświadczenia w pracy z narzędziami opartymi na notacji wyrażeń regularnych uznaliśmy za naturalne dołączenie opisu wyrażeń regularnych. Ponadto wydawało nam się, że nie może się obejść bez implementacji. Biorąc pod uwagę naszą orientację na narzędzia, najlepszym wyborem wydawało się także skupienie się na klasie wyrażeń regularnych znanych z narzędzia grep zamiast na przykład wyrażeń regularnych z symboli wieloznacznych powłoki, ponieważ dzięki temu mogliśmy także omówić sam projekt narzędzia grep.
Problem polegał na tym, że wszystkie istniejące pakiety wyrażeń regularnych były o wiele za duże. Lokalny grep zajmował około 500 wierszy (około 10 stron książki) i zawierał dodatkowy kod. Otwarte pakiety wyrażeń regularnych były z reguły ogromne — miały rozmiar mniej więcej całej książki — ponieważ zostały utworzone do ogólnych zastosowań i muszą być elastyczne oraz szybkie. Żaden z nich nie nadawał się do celów dydaktycznych.
Zaproponowałem, abyśmy znaleźli najmniejszy pakiet wyrażeń regularnych ilustrujący podstawowe koncepcje i jednocześnie zawierający użyteczną i niebanalną klasę wzorców. Idealnie by było, gdyby kod mieścił się na jednej stronie.
Rob zniknął w swoim biurze. Jeśli dobrze pamiętam, po czasie nie dłuższym niż godzina lub dwie pojawił się z powrotem z 30 wierszami kodu w języku C, który następnie został wykorzystany w rozdziale 9. książki Lekcja programowania. Kod ten implementuje mechanizm dopasowujący wyrażeń regularnych, obsługujący następujące konstrukcje:
Znak
Znaczenie
c
Dopasowuje każdą literę c
. (kropka)
Dopasowuje każdy pojedynczy znak
Dopasowuje początek łańcucha wejściowego
$
Dopasowuje koniec łańcucha wejściowego
*
Dopasowuje zero lub więcej wystąpień poprzedniego znaku
Jest to bardzo przydatna klasa. Z mojego doświadczenia w codziennym używaniu wyrażeń regularnych wynika, że można ją z powodzeniem stosować w 95 procentach przypadków. Niejednokrotnie kluczem do napisania pięknego programu jest rozwiązanie właściwego problemu. Robowi należy się wielkie uznanie za wyselekcjonowanie bardzo małego, lecz ważnego i dobrze zdefiniowanego rozszerzalnego zestawu właściwości z obszernego zbioru opcji.
Implementacja Roba sama w sobie jest doskonałym przykładem pięknego kodu. Jest elegancka, zwięzła, wydajna i przydatna. Jest to jeden z najlepszych przykładów rekurencji, jakie w życiu widziałem, a na dodatek doskonale pokazuje możliwości wskaźników w języku C. Mimo że wtedy staraliśmy się pokazać, jak ważną rolę w tworzeniu łatwego w użyciu programu odgrywa zastosowanie dobrej notacji (która ponadto ułatwia samo pisanie), kod wyrażeń regularnych był także doskonałym sposobem na zilustrowanie algorytmów, struktur danych, testowania, technik zwiększania wydajności i innych ważnych zagadnień.
Implementacja
W Lekcji programowania mechanizm dopasowujący wyrażeń regularnych stanowi część samodzielnego programu naśladującego narzędzie grep. Jednak kod wyrażeń regularnych jest całkowicie odseparowany od otaczającego go kodu. Program główny nie interesuje nas tutaj. Jak wiele narzędzi systemu Unix wczytuje on dane ze standardowego wejścia lub plików i drukuje z nich wiersze, które zawierają łańcuchy pasujące do wyrażenia regularnego.
Oto kod dopasowujący:
/* match: wyszukuje wyrażenie regularne w tekście. */ int match(char *regexp, char *text)
{
if (regexp[0] == 1"')
return matchhere(regexp+1, text); do { /* Musi szukać, nawet jeśli łańcuch jest pusty. */
if (matchhere(regexp, text)) return 1;
} while (*text++ != '\0'); return 0;
}
/* matchhere: szuka wyrażenia regularnego na początku tekstu. */ int matchhere(char *regexp, char *text)
if (regexp[0] == '\0') return 1; if (regexp[1] == '*')
return matchstar(regexp[0], regexp+2, text);
if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0'; if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text)) return matchhere(regexp+1, text+1); return 0;
/* matchstar: szuka wyrażenia c*regexp na początku tekstu. */ int matchstar(int c, char *regexp, char *text)
do { /* Symbol * dopasowuje zero lub więcej wystąpień. */
} while (*text != '\0' && (*text++ == c || c == '.')); return 0;
Omówienie
Funkcja match(regexp, text) sprawdza, czy w tekście występuje wyrażenie regularne. Jeśli tak, zwraca wartość 1, jeśli nie — 0. Jeżeli jest więcej niż jedno wystąpienie szukanego łańcucha, zwraca pierwsze od lewej i najkrótsze.
Zasada działania funkcji match jest prosta. Jeśli pierwszy znak wyrażenia regularnego to ", dopasowanie następuje tylko wtedy, gdy szukany łańcuch znajduje się na początku łańcucha. To znaczy wyrażenie regularne "xyz dopasuje łańcuch xyz, tylko jeśli znajduje się on na samym początku innego łańcucha, a nie gdzieś w środku. Sprawdzanie tego odbywa się poprzez dopasowanie reszty wyrażenia regularnego do początku tekstu i nigdzie indziej. W przeciwnym przypadku wyrażenie regularne mogłoby znaleźć dopasowanie w dowolnym miejscu łańcucha. Jest to sprawdzane poprzez dopasowanie wzorca względem położenia każdego znaku tekstu. Jeśli zostanie znalezionych wiele dopasowań, zostanie uwzględnione tylko pierwsze z nich. To znaczy wyrażenie regularne xyz zostanie dopasowane do pierwszego łańcucha xyz bez względu na to, gdzie się on znajduje.
Zauważmy, że łańcuch wejściowy jest badany za pomocą pętli do-while — struktura dość niezwykła w języku C. Pojawienie się pętli do-while zamiast while powinno zawsze rodzić pytanie, czemu warunek końcowy pętli nie jest sprawdzany na początku jej działania, kiedy nie jest jeszcze za późno, tylko na końcu, kiedy coś już zostało zrobione. Ale tutaj jest to właściwy wybór: jako że operator * zezwala na dopasowania zerowej długości, najpierw musi sprawdzić, czy dopasowanie zerowe jest możliwe.
Znaczna część pracy jest wykonywana w funkcji matchhere(regexp, text), która sprawdza, czy wyrażenie regularne pasuje do tekstu, który zaczyna się dokładnie w tym miejscu. Funkcja ta sprawdza, czy pierwszy znak wyrażenia regularnego pasuje do pierwszego znaku tekstu. Negatywny wynik oznacza brak dopasowania w tym miejscu w tekście i funkcja zwraca wartość 0. Jeśli natomiast wynik jest pozytywny, następuje przejście do drugiego znaku wyrażenia regularnego i tekstu. Jest to wykonywane poprzez rekurencyjne wywoływanie funkcji matchhere.
Sytuację komplikuje kilka specjalnych przypadków i oczywiście konieczność zatrzymania rekuren- cji. Najprostszym przypadkiem jest sytuacja, w której został osiągnięty koniec wyrażenia regularnego (regexp[0] == ' \0'), wszystkie sprawdzenia zakończyły się powodzeniem, a więc wyrażenie regularne pasuje do tekstu.
Jeśli wyrażenie regularne ma postać znaku z dołączoną gwiazdką, wywoływana jest funkcja matchstar szukająca dopasowań dla tego znaku. Funkcja matchstar(c, regexp, text) dopasowuje wystąpienia w tekście znaku c, zaczynając od zera powtórzeń i doliczając kolejne, aż znajdzie dopasowanie reszty tekstu lub zakończy się niepowodzeniem, co oznacza, że nic nie pasuje. Algorytm ten znajduje „najkrótsze dopasowanie”, które jest dobre dla prostych dopasowań wzorców, jak w narzędziu grep, w którym jedyne, co się liczy, to jak najszybsze znalezienie dopasowania. Inny rodzaj dopasowania to „najdłuższe dopasowanie”, które lepiej sprawdza się w edytorach tekstu, gdzie dopasowany tekst jest zastępowany innym. Najnowocześniejsze biblioteki wyrażeń regularnych udostępniają obie metody. W książce Lekcja programowania przedstawiliśmy prosty wariant funkcji matchcase dla takiego przypadku, który przedstawiono poniżej.
Jeśli wyrażenie regularne zawiera na końcu znak $, tekst jest dopasowywany, tylko jeśli również znajduje się na końcu:
if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0';
W przeciwnym przypadku, jeśli nie znajdujemy się na końcu łańcucha tekstu (czyli *text ! = '\0...
coralclub