To jest stara wersja strony!
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 dość 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, w naszym przypadku poprzez Boost.Regex, „wyłuskiwanie” tematu jesteśmy w stanie zrealizować deklaratywnie (pomijając istnienie niezbędnej pętli), a więc opisując to, 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ż:
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 jest 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:
egrep
czy awk
),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 "słowny" (alfanumeryczny lub _) \D <=> [^[:digit:]] | nie: cyfra \L <=> [^[:lower:]] | nie: mała litera \S <=> [^[:space:]] | nie: spacja \U <=> [^[:upper:]] | nie: duża litera \W <=> [^[:word:]] | nie :znak "słowny" (?#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 (ang. greedy), 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, dzięki którym możemy jeszcze bardziej złożone wyrażenia regularne budować. Wyrażenie regularne odpowiedzialne za wyszukiwanie powtórzeń w tekście mogłoby wyglądać tak:
(\w) \1
Do skorzystania z dobrodziejstw Boost.Regex niezbędne jest dołączenie pliku nagłówkowego:
#include <boost/regex.hpp>
Tak jak w przypadku innych bibliotek Boosta, wszystkie stałe, klasy i funkcje zewnętrzne znajdują się przestrzeni nazw boost
i dla przejrzystości nie będę tego pisał przy przytaczaniu fragmentów definicji podstawowych elementów Boost.Regex.
Wyrażeniu regularnemu odpowiada szablon klasy boost::basic_regex
, który parametryzowany jest typem znaku i klasą cech tego typu (która domyślnie jest definiowana poprzez szablon regex_traits
parametryzowany wcześniej podanym typem znaku).
template < class charT, class traits = regex_traits<charT> > class basic_regex { /*...*/ };
Dla wygody zdefiniowane są nasŧepujące typy:
typedef basic_regex<char> regex; typedef basic_regex<wchar_t> wregex;
Ważniejsze metody tego szablonu to:
bool empty() const; // zwraca true jeżeli 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
Najważniejszy jest jednak konstruktor:
explicit basic_regex(const charT* p, flag_type f = regex_constants::normal);
który przyjmuje sekwencję znaków zawierającą wyrażenie regularne oraz tryb przetwarzania tego wyrażenia.
W przypadku niepoprawnego wyrażenia regularnego rzucany jest wyjątek boost::regex_error
(dawniej boost::bad_expression
lub boost::bad_pattern
, które są teraz aliasami do boost::regex_error
dla wstecznej kompatybilności), chyba że przekazano flagę regex_constants::no_except
.
Mamy następujące podstawowe (nieuzależnione od wybranej składni) tryby przetwarzania):
namespace regex_constants { typedef implementation-specific-bitmask-type syntax_option_type; static const syntax_option_type normal; // Domyślna składnia RE języka Perl static const syntax_option_type ECMAScript = normal; // i jej aliasy... static const syntax_option_type JavaScript = normal; static const syntax_option_type JScript = normal; static const syntax_option_type perl = normal; static const syntax_option_type basic; // Składnia POSIX podstawowa static const syntax_option_type sed = basic; // i jej najpopularniejszy alias static const syntax_option_type grep; // oraz odmiana. static const syntax_option_type extended; // Składnia POSIX rozszerzona static const syntax_option_type awk; // z dwiema odmianami. static const syntax_option_type egrep; static const syntax_option_type icase; // Ignorowanie wielkości liter // w dopasowaniach static const syntax_option_type nosubs; // Zaniechanie tworzenia podwyrażen // w dopasowaniach static const syntax_option_type optimize; // Optymalizacja poźniejszego dopasowywania // nawet kosztem dłuższego tworzenia obiektu. static const syntax_option_type collate; // Zakresy znaków przekazywane w nawiasach // kwadratowych powinny uwzględniać lokalizm. }
Dla wygody powyższe stałe zdefiniowane są także w obrębie szablonu klasy basic_regex
.
Oprócz klasy reprezentującej wyrażenie regularne potrzebujemy także klasy przechowującej znalezione dopasowania w zadanym tekście. Służy do tego szablon klasy boost::match_results
parametryzowany typem iteratora obsługującego sekwencję wejściową:
template < class BidirectionalIterator, class Allocator = std::allocator<sub_match<BidirectionalIterator> > class match_results { /*...*/ };
Podobnie jak wcześniej, zdefiniowano następujące typy dla wygodniejszego użycia:
typedef match_results<const char*> cmatch; typedef match_results<const wchar_t*> wcmatch; typedef match_results<string::const_iterator> smatch; typedef match_results<wstring::const_iterator> wsmatch;
Dopasowania to tak naprawdę kolekcje poddopasowań boost::sub_match
, do których dostęp mamy jedynie poprzez operator[]
klasy boost::match_results
.
Same szablony klas boost::basic_regex
oraz boost::match_results
byłyby nic nie warte bez funkcji, które na nich operują realizując podstawowe przypadki użycia wyrażen regularnych.
Poniżej omówione szablony funkcji parametryzowane są różnymi elementami w zajemności od wersji (pominę dokładne deklaracje tych szablonów), ale zawsze jest to m.in. typ znaku.
// Wersja bez zapisywania odnalezionych dopasowań. template </* */> bool regex_match(const basic_string</* */>& s, const basic_regex</* */>& e, match_flag_type flags = match_default); // Wersja zapisująca odnalezione dopasowania w obiekcie klasy match_results. template </* */> bool regex_match(const basic_string</* */>& s, match_results</* */>& m, const basic_regex</* */>& e, match_flag_type flags = match_default); // Wersja główna, wołana także przez powyższe template <class BidirectionalIterator, class Allocator, class charT, class traits> bool regex_match(BidirectionalIterator first, BidirectionalIterator last, match_results<BidirectionalIterator, Allocator>& m, const basic_regex<charT, traits>& e, match_flag_type flags = match_default);
// Wersja bez zapisywania odnalezionych dopasowań. template </* */> bool regex_search(const basic_string</* */>& s, const basic_regex</* */>& e, match_flag_type flags = match_default); // Wersja zapisująca odnalezione dopasowania w obiekcie klasy match_results. template </* */> bool regex_search(const basic_string</* */>& s, match_results</* */>& m, const basic_regex</* */>& e, match_flag_type flags = match_default); // Wesja główna, wołana także przez powyższze template <class BidirectionalIterator, class Allocator, class charT, class traits> bool regex_search(BidirectionalIterator first, BidirectionalIterator last, match_results<BidirectionalIterator, Allocator>& m, const basic_regex<charT, traits>& e, match_flag_type flags = match_default);
// Wersja wygodna template </* */> basic_string</* */> regex_replace(const basic_string</* */>& s, const basic_regex</* */>& e, const basic_string</* */>& fmt, match_flag_type flags = match_default); // Wersja główna template <class OutputIterator, class BidirectionalIterator, class traits, class charT> OutputIterator regex_replace(OutputIterator out, BidirectionalIterator first, BidirectionalIterator last, const basic_regex<charT, traits>& e, const basic_string<charT>& fmt, match_flag_type flags = match_default);
boost::regex_token_iterator
to już nie funkcja a szablon klasy będącej adapterem iteratora.
template <class BidirectionalIterator, class charT = iterator_traits<BidirectionalIterator>::value_type, class traits = regex_traits<charT> > class regex_token_iterator { /* ... */ regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b, const basic_regex<charT, traits>& re, int submatch = 0, match_flag_type m = match_default); regex_token_iterator(BidirectionalIterator a, BidirectionalIterator b, const basic_regex<charT, traits>& re, const std::vector<int>& submatches, match_flag_type m = match_default); /* ... */ }
Ważne innowacje:
Regex | Spirit | Xpressive | |
---|---|---|---|
Dopasowywanie wzorców ad-hoc, języki regularne | tak | tak | tak |
Ustrukturalizowane parsowanie, gramatyki bezkontekstowe | - | tak | tak |
Manipulowanie tekstem | tak | tak | tak |
Akcje semantyczne, manipulowanie stanem programu | - | tak | - |
Dynamiczność - nowe deklaracje w trakcie działania | tak | - | tak |
Statyczność - brak nowych deklaracji w trakcie działania | tak | tak | tak |
Wyczerpujące przeszukiwanie z nawrotami | tak | - | tak |
Małego komentarza może wymagać wyczerpujące przeszukiwanie z nawrotami (ang. exhaustive backtracking). Chodzi o to, że przymiotnik „wyczerpujące” nie opisuje samego procesu przeszukiwania z nawrotami, które w istocie jest wyczerpujące, a konsekwencję w jego stosowaniu, która jest wymagana od wyrażeń regularnych. Boost.Spirit stosuje backtracking, jednak gdy znajduje jakieś częściowe dopasowanie, to nie „cofa się”, żeby możliwe było zrealizowanie reszty reguły, tylko uznaje, że dopasowanie się nie powiodło. Dlatego poniższy przykład nigdy nie zadziała:
*chlit_p('a') >> chlit_p('a');