Wersja robocza

W życiu każdego programisty przychodzi czas, w którym musi poznać wyrażenia regularne (z różnych przyczyn), a znając już je, używa ich chętnie i bez oporów, przynajmniej w skryptach shellowych (a de facto w programach typu AWK, grep czy sed) i w interpretowanych językach jak PHP, Perl, Ruby oraz innych.

Ogromne możliwości przetwarzania tekstu, jakie dają nam potocznie nazywane regexpy, można też wykorzystać w językach, w których nie wbudowano obsługi wyrażeń regularnych, czyli np. w języku C++. Nie mówię tu o własnoręcznej implementacji np. niedeterministycznego automatu skończonego Thompsona, choć to też byłoby pewne wyjście. Programiści, z natury jednostki leniwe, często lubią korzystać z gotowych komponentów do budowy własnego oprogramowania. Niestety, brak obsługi wyrażeń regularnych w standardowej bibliotece C++ w standardzie C++98 (ISO/IEC 14882:1998) czy ostatnim C++03 (ISO/IEC 14882:2003). Sytuację poprawia dopiero TR1, który będzie częścią standardu C++0x, a którego ostateczne ujęcie i ratyfikacja nastąpią w najbliższych latach, optymistycznie: już w przyszłym roku.

Co więc trafiło do przestrzeni std::tr1? To, co dziś znamy jako biblioteka Boost.Regex, której autorem jest John Maddock.

Oczywiście nie jest to jedyna biblioteka implementująca wyrażenia regularne w języku C++, ale tym razem PCRE, QRegExp (część Qt) i inne rozwiązania zostaną świadomie przemilczane, choć kiedyś na pewno jeszcze o nich wspomnę…

Mamy do zrealizowania mały program, który na wejściu przyjmuje maile, a na wyjściu podaje ich tematy, przy czym ewentualny przedrostek Re: nie należy do wyświetlanego tematu.

Tak mogłoby wyglądać rozwiązanie imperatywne:

std::string line;
while (std::getline(std::cin, line))
{
    if (line.compare(0, 9, "Subject: ") == 0)
    {
        std::size_t offset = 9;
        if (line.compare(offset, 4, "Re: "))
            offset += 4;
        std::cout << line.substr(offset);
    }
}

Korzystając z wyrażeń regularnych, a w naszym przypadku z Boost.Regex, „wyłuskiwanie” tematu jesteśmy w stanie zrealizować deklaratywnie (pomijając istnienie niezbędnej pętli), a więc opisując czego szukamy, a nie jak:

std::string line;
 
// Asercja ^ jest zbędna gdy wyrażenie jest używane w funkcji boost::regex_match,
// ale jej obecność pozwala także na ewentualne zastosowanie funkcji
// boost::regex_search. Wyjaśnienie pojawi się w dalszej części...
boost::regex pat("^Subject: (Re: )?(.*)");
boost::smatch what;
 
while (std::getline(std::cin, line))
{
    if (boost::regex_match(line, what, pat))
        std::cout << what[2];
}

Rozwiązanie deklaratywne jest lepsze, ponieważ:

• opisuje to co chcemy osiągnąć (a nie przy użyciu jakiego algorytmu),
• jest bardziej zwięzłe,

przez co jest też łatwiejsze w utrzymaniu.

Wyobraźmy sobie teraz, że mamy maile wygenerowane przez program Outlook Express, który lubi dodawać więcej przedrostków Re:, aniżeli jest to potrzebne w dłuższych konwersacjach. Dodatkowo weźmy pod uwagę, że niektóre OE mogły być w polskiej wersji językowej i dodawały Odp: zamiast Re:.
Poprawione wyrażenie regularne będzie wówczas wyglądać np. tak „^Subject: (Re: |Odp: )*(.*)” i to jedyna zmiana niezbędna w rozwiązaniu deklaratywnym. Czytelnik zapewne z wielkim zapałem samodzielnie usprawni rozwiązanie imperatywne…

Do wyboru mamy trzy główne składnie wyrażeń regularnych:

• Perl (domyślna),
• POSIX rozszerzona (z odmianami używanymi w egrep czy awk),
• POSIX podstawowe (z odmianami używanymi w grep czy emacs).

Omówię pokrótce tylko najważniejsze elementy domyślnej składni.

          Zapis          ^                 Znaczenie
.                        | dowolny znak
^                        | początek linii
$                        | koniec linii
(  )                     | początek i koniec znaczonego grupowania
(?:   )                  | początek i koniec nieznaczonego grupowania
*                        | powtórzenie atomu zero lub więcej razy
+                        | powtórzenie atomu jeden lub więcej razy
?                        | powtórzenie atomu zero lub jeden raz
{n}                      | powtórzenie atomu dokładnie n razy
{n,}                     | powtórzenie atomu n lub więcej razy
{n,m}                    | powtórzenie atomu od n do m razy
|                        | alternatywa
[znaki^odrzuty]          | dopuszczalny znaki i niedopuszczalne odrzuty
\d  <=>  [[:digit:]]     | cyfra
\l  <=>  [[:lower:]]     | mała litera
\s  <=>  [[:space:]]     | spacja
\u  <=>  [[:upper:]]     | duża litera
\w  <=>  [[:word:]]      | znak mogący być elementem wyrazu
\D  <=>  [^[:digit:]]    | nie cyfra
\L  <=>  [^[:lower:]]    | nie mała litera
\S  <=>  [^[:space:]]    | nie spacja
\U  <=>  [^[:upper:]]    | nie duża litera
\W  <=>  [^[:word:]]     | nie znak mogący być elementem wyrazu
(?#komentarz)            | ignorowany (komentarz)
(?:wzorzec)              | "zjada" 0 znaków tylko jeżeli wzorzec się zgadza
(?!wzorzec)              | "zjada" 0 znaków tylko jeżeli wzorzec nie pasuje

Wszystkie operatory powtórzenia są domyślnie zachłanne, czyli starają się pokryć jak największy obszar tekstu. Odwrócenie tego zachowania możemy uzyskać poprzez dodanie ? na końcu takiego operatora, uzyskując np. *? lub {n,}?.

Na koniec nie sposób nie wspomnieć o odwołaniach wstecznych (ang. backreferences), które stosujemy poprzez poprzedzenie znakiem backslash (\) numeru grupy znaczonej,

Do skorzystania z dobrodziejstw Boost.Regex niezbędne jest dołączenie pliku nagłówkowego:

#include <boost/regex.hpp>

Wyrażeniu regularnemu odpowiada szablon klasy boost::basic_regex, który parametryzowany jest m.in. typem znaku. Metody tego szablonu to:

bool empty() const;          // zwraca true jeżeli w obiekt nie zawiera żadnego poprawnego wyrażenia regularnego
unsigned mark_count() const; // zwraca liczbę znaczonych podwyrażeń w wyrażeniu regularnym
flag_type flags() const;     // zwraca maskę bitową zawierającą flagi trybu przetwarzania wyrażenia regularnego

Dla wygody, wewnątrz przestrzeni boost zdefiniowane są nasŧepujące typy:

typedef basic_regex<char> regex;
typedef basic_regex<wchar_t> wregex;

Ważne innowacje:

• obsługa tworzenia (obok dynamicznych, podobnych w zapisie do Boost.Regex) statycznych wyrażeń regularnych, podobnych w zapisie do Boost.Spirit, przez przeciążanie operatorów i zastosowanie techniki zwanej szablonami wyrażeniowymi (ang. expression templates) - owa statyczność daje wiele możliwości, m.in. kontrolę poprawności takiego wyrażenia już w czasie kompilacji,
• możliwość mieszania statycznych i dynamicznych wyrażeń regularnych,
• możliwość osadzania wyrażeń regularnych poprzez referencje.