17
Iun
2008

Expresiile regulate permit procesarea textelor intr-un mod mult mai eficient decat prin cod procedural, intrucat descrierea procesarii e mutata din cod in expresia regulata. Pana la TR1 in STL nu exista suport pentru expresii regulate. Acum acesta exista si este modelat dupa cel existent in biblioteca boost. In acest articol voi incerca sa fac putina lumina in ce exista nou in TR1.

Expresiile regulate din TR1, (clasa regex), poate lucra cu oricare din urmatoarele sase gramatici:

  • ECMAScript, gramatica implicita si cea mai bogata
  • basic, POSIX Basic Regular Expressions
  • extended, POSIX Extended Regular Expressions
  • awk, POSIX awk
  • grep, POSIX grep
  • egrep, POSIX grep -E

Dintre acestea, asa cum am mentionat anterior, cea mai bogata in posibilitati de exprimare este ECMAScript (care practic contine tot ce ofera oricare din celelalte gramatici). Standardul spune ca gramatica recunoscuta de clasa basic_regex este (cu exceptiile de rigoare) cea specificata de ECMA-262. Aceasta este ECMAScript Language Specification a carei expresii regulate sunt modelate dupa expresiile regulate din Perl 5.

In acest articol nu voi intra in detaliile de exprimare ale acestor gramatici. Acest articol din MSDN explica gramatica si semantica expresiilor regulate. Ce as dori insa sa mentionez inainte de a merge mai departe sunt asa numitele "grupuri de captura" (sau capture groups in limba engleza). O expresie regulata poate contine astfel de grupe de captura (numite si subexpresii), a carui rol este indentificarea unor parti ale unei expresii regulate pentru a fi folosite mai tarziu. Grupurile de captura sunt introduse prin paranteze; de exemplu: (ab+|cd?).

In headerul <regex> sub namespace-ul std::tr1 sunt disponibili tipuri, algoritmi si iteratori.

Tipuri

  • basic_regex: Este o clasa template care contine o expresie regulata; implementeaza practic o masina de stari finita, construita in baza unei expresii regulate. Exista doua typedef-uri pentru aceasta clasa, unul pentru char si unul pentru wchar_t.
    typedef basic_regex<char> regex;
    typedef basic_regex<wchar_t> wregex;
    

    De remarcat ca aceasta clasa nu are un constructor implicit, ci doar explicit, datorita faptului ca instantierea unui astfel de obiect este consumatoare de timp.

  • match_results: O clasa care contine o secventa de potriviri; fiecare element pointeaza catre subsecventa care s-a potrivit grupului de captura corespunzator elementului. Atunci cand empty() returneaza true sau size() returneaza 0, un obiect de acest tip nu contine nici o potrivire. Altfel, daca empty() returneaza false, atunci size() returneaza 1 sau o valoare mai mare, astfel ca:
    • match[0] - reprezinta intreaga protrivire
    • match[1] - reprezinta prima potrivire (sub_match)
    • match[2] - reprezinta a doua potrivire, etc.
    • prefix() - returneaza string-ul care precede potrivirea
    • suffix() - returneaza string-ul care urmeaza potrivirii

    Exista mai multe typedef-uri pentru std::tr1::match_results:

    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;
    
  • sub_match: reprezinta o secventa de caractere care se potrivesc unui grup de captura; un obiect de tipul match_results poate contine un sir de obiecte de acest tip. Daca pentru un grup de captura nu a existat o potrivire, cei doi iteratori pentru un obiect de acest tip sunt egali. Exista mai multe typedef-uri pentru aceasta clasa template.
    typedef sub_match<const char*> csub_match;
    typedef sub_match<const wchar_t*> wcsub_match;
    typedef sub_match<string::const_iterator> ssub_match;
    typedef sub_match<wstring::const_iterator> wssub_match;
    
  • regex_constants: contine o serie de constante pentru reguli de sintaxa, reguli de potrivire si formatare, si identificatori de eroare.
  • regex_error: exceptie aruncata pentru a indica o eroare in constructia sau folosirea unui obiect basic_regex
  • regex_traits: descrie diferite caracteristici ale elementelor pentru potriviri; exista doua specializari ale acestei clase template, pentru char si wchar_t:
    template <>
        class regex_traits<char>
        
    template <>
        class regex_traits<wchar_t>
    

Algoritmi

  • regex_match(): potriveste exact un string cu o expresie regulata, construind sub-potriviri pentru grupurile de captura;
  • regex_search(): potriveste parti ale unui string cu o expresie regulata, construind sub-potriviri pentru grupurile de captura;
  • regex_replace(): inlocuieste toate potrivirile dintr-o expresie regulata conform unui format; optional se poate inlocui doar prima potrivire sau elimina din string partile care nu au dat potrivire;
  • swap(): inverseaza doua obiecte de tipul basic_regex sau match_result.

Iteratori

  • regex_iterator: un iterator constant de tip forward pentru iterarea printre rezultatele unei potriviri. Exista mai multe typedef-uri pentru aceasta clasa template:
    typedef regex_iterator<const char*> cregex_iterator;
    typedef regex_iterator<const wchar_t*> wcregex_iterator;
    typedef regex_iterator<string::const_iterator> sregex_iterator;
    typedef regex_iterator<wstring::const_iterator> wsregex_iterator;
    
  • regex_token_iterator: un iterator constant de tip forward pentru iterarea peste grupurile de captura ale tuturor potrivirilor unei expresii intr-un string. In mod conceptual, acesta contine un iterator regex_iterator folosit pentru a cauta potriviri intr-o secventa de caractere. Exista mai multe typedef-uri pentru aceasta clasa template:
    typedef regex_token_iterator<const char*> cregex_token_iterator;
    typedef regex_token_iterator<const wchar_t*> wcregex_token_iterator;
    typedef regex_token_iterator<string::const_iterator> sregex_token_iterator;
    typedef regex_token_iterator<wstring::const_iterator> wsregex_token_iterator;
    

Potrivire

Acest paragraph contine exemple despre folosirea expresiilor regulate pentru a potrivi exact un string.

Exemplu 1

Functia is_email_valid returneaza true daca o adresa de email-ul este intr-un format valid (expresia folosita nu este neaparat cea mai cuprinzatoare).

#include <regex>
#include <iostream>
#include <string>

bool is_email_valid(const std::string& email)
{
   // defineste o expresie regulata
   const std::tr1::regex pattern("(\\w+)(\\.|_)?(\\w*)@(\\w+)(\\.(\\w+))+");

   // incearca sa potriveasca exact string-ul cu expresia regulata
   return std::tr1::regex_match(email, pattern);
}

int main()
{
   std::string email1 = "marius.bancila@domain.com";
   std::string email2 = "mariusbancila@domain.com";
   std::string email3 = "marius_b@domain.co.uk";
   std::string email4 = "marius@domain";

   std::cout << email1 << " : " << (is_email_valid(email1) ? "valid" : "invalid") << std::endl;
   std::cout << email2 << " : " << (is_email_valid(email2) ? "valid" : "invalid") << std::endl;
   std::cout << email3 << " : " << (is_email_valid(email3) ? "valid" : "invalid") << std::endl;
   std::cout << email4 << " : " << (is_email_valid(email4) ? "valid" : "invalid") << std::endl;

   return 0;
}

Acest program va afisa:

marius.bancila@domain.com : valid
mariusbancila@domain.com : valid
marius_b@domain.co.uk : valid
marius@domain : invalid

Folosirea unui obiect match_results permite acesul la grupurile de captura, introduse, asa cum am specificat mai sus prin paranteze. Daca exista potrivire, atunci match[0] reprezinta intreaga potrivire, iar match[i] (unde i > 0) reprezinta potrivirea i.

Exemplul 2

Exmplul urmator identifica si afiseaza partile individuale ale unei adrese IP.

#include <regex>
#include <iostream>
#include <string>

void show_ip_parts(const std::string& ip)
{
   // expresia regulata cu 4 grupuri de captura, delimitate de paranteze (...)
   const std::tr1::regex pattern("(\\d{1,3}):(\\d{1,3}):(\\d{1,3}):(\\d{1,3})");

   // obiect ce va contine o secventa de sub-potriviri
   std::tr1::match_results<std::string::const_iterator> result;

   // potriveste adresa IP cu expresia regulata
   bool valid = std::tr1::regex_match(ip, result, pattern);

   std::cout << ip << " \t: " << (valid ? "valid" : "invalid") 
             << std::endl;
             
   // daca adresa a fost potrivita, afiseaza sub-potrivirile
   if(valid)
   {
      std::cout << "b1: " << result[1] << std::endl;
      std::cout << "b2: " << result[2] << std::endl;
      std::cout << "b3: " << result[3] << std::endl;
      std::cout << "b4: " << result[4] << std::endl;
   }
}

int main()
{
   show_ip_parts("1:22:33:444");
   show_ip_parts("1:22:33:4444");
   show_ip_parts("100:200");

   return 0;
}

Programul va afisa:

1:22:33:444     : valid
b1: 1
b2: 22
b3: 33
b4: 444
1:22:33:4444    : invalid
100:200         : invalid

Cautare

In cazul lui regex_match intregul string era potrivit cu o expresie regulata. Pe de alta parte, regex_search() realizeaza o cautare intr-un string, potrivind parti ale string-ului cu o expresie regulata.

Exemplul 1

In exemplul urmator cautam primul cuvant dintr-un text care se termina in 'day'.

int main()
{
   // expresia regulata
   const std::tr1::regex pattern("(\\w+day)");
   
   // textul in care se cauta potrivirea
   std::string weekend = "Saturday and Sunday";
   
   // secventa de potriviri
   std::tr1::smatch result;

   bool match = std::tr1::regex_search(weekend, result, pattern);

   if(match)
   {
      // daca a existat potrivire afiseaza rezultatul
      for(size_t i = 1; i < result.size(); ++i)
      {
         std::cout << result[i] << std::endl;
      }
   }

   return 0;
}

Programul de mai sus va afisa doar:

Saturday

Pentru a gasi toate potrivirile trebuie folosit un token iterator, dupa cum se vede in exemplul urmator.

Exemplul 2

int main()
{
   // definirea expresiei regulate
   const std::tr1::regex pattern("\\w+day");

   // textul in care se cauta
   std::string weekend = "Saturday and Sunday, but some Friday also.";

   const std::tr1::sregex_token_iterator end;
   for (std::tr1::sregex_token_iterator i(weekend.begin(), weekend.end(), pattern);
      i != end; 
      ++i)
   {
      std::cout << *i << std::endl;
   }
   
   return 0;
}

In acest caz se va afisa:

Saturday
Sunday
Friday

In exemplul anterior constructorul lui sregex_token_iterator a primit ca parametrii doi iteratori care delimiteza textul in care se face cautarea si un obiect regex reprezentand expreia regulata. In acest caz interatorul indica doar catre potriviri corespunzatoare unui singur grup de captura. Pentru a itera peste mai multe grupe de captura e necesar un alt constructor, care ia un vector continand indecsii grupurilor de captura care sa fie luate in considerare.

Exemplul 2

In acest exemplu vom extrage dintr-un text o lista de puncte reprezentand varfurile unui poligon.

struct Point
{
    int X;
    int Y;
    Point(int x, int y): X(x), Y(y){}
};

typedef std::vector<Point> Polygon;

int main()
{
    Polygon poly;
    std::string s = "Polygon: (1,2), (3,4), (5,6), (7,8)";

    const std::tr1::regex r("(\\d+),(\\d+)");

    const std::tr1::sregex_token_iterator end;
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);

    for (std::tr1::sregex_token_iterator i(s.begin(), s.end(), r, v);
        i != end;)
    {
        int x = atoi((*i).str().c_str()); ++i;
        int y = atoi((*i).str().c_str()); ++i;
        poly.push_back(Point(x, y));
    }

    for(size_t i = 0; i < poly.size(); ++i)
    {
        std::cout << "(" << poly[i].X << ", " << poly[i].Y << ") ";
    }
    std::cout << std::endl;
    
    return 0;
}

Acest program va afisa:

(1, 2) (3, 4) (5, 6) (7, 8)

Pentru a intelege cum functioneaza acest constructor, putem comenta al doilea apel push_back().

    std::vector<int> v;
    v.push_back(1);
    //v.push_back(2);

In acest caz doar primul grup de captura va fi luat in considerare si se va afisa:

(1, 3) (5, 7)

Daca am comenta al primul apel al psuh_back() atunci doar al doilea grup de captura ar fi luat in considerare si s-ar afisa:

(2, 4) (6, 8)

Un aspect care trebuie avut in vedere in exemplul de mai sus este ordinea evaluarii. Daca as fi scris:

poly.push_back(
   Point(
      atoi((*i++).str().c_str()),
      atoi((*i++).str().c_str())));

atunci am fi avut un comportament nedefinit, intrucat iteratorul i era modificat de mai multe ori intre doua puncte de secventa (sequence points), cea ce este ilegal.

Transformari

Se poate inlocui o potrivire intr-un string dupa un anumit format. Acest format poata sa fie un alt string, fie un string continand caractere escape indicand potrivirea unui anumit grup de captura de exemplu.

  • $1 - reprezinta subsirul care se potriveste primului grup de captura
  • $2 - reprezinta subsirul care se potriveste celui de-al doilea grup de captura
  • $& - reprezinta subsirul care se potriveste intregii expresii regulate
  • $` - reprezinta subsirul care apare inaintea subsirului ce se potriveste expresiei regulate
  • $' - reprezinta subsirul care apare dupa subsirul ce se potriveste expresiei regulate
  • $$ - $

Exemplul 1

Exemplul de mai jos inlocuieste articolul nedefinit 'a' cu 'an' pentru un text in limba engleza, atunci cand 'a' precede un cuvant care incepe cu o vocala.

int main()
{
   // textul de transformat
   std::string text = "This is a element and this a unique ID.";
   
   // expresia regulata, continand doua grupuri de captura
   const std::tr1::regex pattern("(\\ba (a|e|i|u|o))+");
   
   // formatul de inlocuire, folosing al doilea grup de captura
   std::string replace = "an $2";

   std::string newtext = std::tr1::regex_replace(text, pattern, replace);

   std::cout << newtext << std::endl;
   
   return 0;
}
This is an element and this an unique ID.

Exemplul 2

In acest exemplu vom inlocui doar prima potrivire cu nou substring.

std::string change_root(const std::string& item, const std::string& newroot)
{
   // expresia regulata
   const std::tr1::regex pattern("\\\\?((\\w|:)*)");
   
   // formatul folosit pentru transformare
   std::string replacer = newroot;
   
   // flag care indica transformarea doar primei potriviri
   std::tr1::regex_constants::match_flag_type fonly = 
      std::tr1::regex_constants::format_first_only;

   // aplica transformarea
   return std::tr1::regex_replace(item, pattern, replacer, fonly);
}

int main()
{
   std::string item1 = "\\dir\\dir2\\dir3";
   std::string item2 = "c:\\folder\\";

   std::cout << item1 << " -> " << change_root(item1, "\\dir1") << std::endl;
   std::cout << item2 << " -> " << change_root(item2, "d:") << std::endl;
   
   return 0;
}

Programul va afisa:

\dir\dir2\dir3 -> \dir1\dir2\dir3
c:\folder\ -> d:\folder\

Exemplul 3

Acest exemplu arata cum se poate transforma un string reprezentand o data in format DD-MM-YYYY in YYYY-MM-DD. Pentru separator se poate folosi unul din caracterele '.', '-' sau '/'.

std::string format_date(const std::string& date)
{
   // expresia regulata
   const std::tr1::regex pattern("(\\d{1,2})(\\.|-|/)(\\d{1,2})(\\.|-|/)(\\d{4})");
   
   // formatul de transformare, inverseaza pozitia tuturor celor cinci grupuri de captura
   std::string replacer = "$5$4$3$2$1";

   // aplica transformarea
   return std::tr1::regex_replace(date, pattern, replacer);
}

int main()
{
   std::string date1 = "1/2/2008";
   std::string date2 = "12.08.2008";

   std::cout << date1 << " -> " << format_date(date1) << std::endl;
   std::cout << date2 << " -> " << format_date(date2) << std::endl;
}
1/2/2008 -> 2008/2/1
12.08.2008 -> 2008.08.12

Concluzii

Acest articol este o privire de ansamblu asupra algoritmilor si a catorva clase din TR1 pentru expresii regulate. Informatii mai detaliate despre acestea pot fi gasite in MSDN. Din pacate, cel putin pentru moment, documentatia TR1 nu este foarte elaborata, motiv pentru care sper ca articolul de fata sa va ajute sa clarificari aspectele de baza ale folosirii acestor facitiliati pentru expresii regulate din TR1.