Expresie regulată

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În informatică, o expresie regulată, denumită pe scurt regex sau regexp (din engleză de la regular expression), reprezintă un șablon care descrie un limbaj regulat, adică o mulțime de șiruri de caractere generată de o gramatică regulată. Majoritatea limbajelor de programare oferă interfețe API pentru tratarea limbajelor regulate, care sunt folosite la validarea formatului unor șiruri de caractere sau la găsirea în porțiuni mai mari de text a unor șiruri de caractere care respectă forma unui limbaj regulat. De asemenea, numeroase aplicații care implică într-un fel sau altul procesarea de text au motoare de expresii regulate ce permit căutări și validări după expresii regulate.

Notație[modificare | modificare sursă]

În lucrările științifice de specialitate, reprezentarea expresiilor regulate se face folosind următoarea notație: | pentru separarea căilor alternative; ? pentru a marca acceptarea prezenței sau nu a simbolului dinaintea sa; * pentru Kleene star; și paranteze pentru gruparea și precedența celorlalți operatori; șirul vid se notează cu ε. Această notație simplă este suficientă pentru notarea exemplelor simple, utilizate în lucrările de specialitate pentru ilustrarea conceptelor matematice din teoria limbajelor și automatelor.

În aplicațiile practice din dezvoltarea software, expresiile regulate bazate pe acest set simplu de operatori ar duce la scrierea unor expresii regulate insuficient de concise. De aceea, s-au elaborat unele notații pentru expresiile regulate speciale pentru utilizarea în practică. Cele mai importante dintre acestea sunt expresiile regulate POSIX, folosite pentru comenzile UNIX ce folosesc expresii regulate, precum și expresiile regulate Perl, sintaxă dezvoltată pentru limbajul de programare Perl, preluată și extinsă și de alte limbaje de programare, cum ar fi Java, JavaScript, Ruby și Python. Aceste sintaxe permit inclusiv secvențe escape, și deci validarea unor limbaje regulate peste alfabete care conțin chiar simbolurile care determină operatorii.

Performanțe și algoritmi[modificare | modificare sursă]

Există mai multe tehnici de identificare ce se pot utiliza pentru validarea unui șir printr-o expresie regulată. Cea mai simplă tehnică este cea backtracking, care însă poate da timpi exponențiali în raport cu lungimea șirului de validat.

O altă metodă o reprezintă așa-numita compilare a expresiei regulate, ceea ce presupune crearea automatului finit determinist (AFD) care validează limbajul regulat definit de expresie, și apoi rularea acestui automat pentru validarea șirului. Deși construirea AFD-ului necesită un timp exponențial în raport cu lungimea expresiei, validarea ei este foarte rapidă, necesitând timp liniar în raport cu lungimea șirului. Soluția este rapidă atunci când se face validarea mai multor șiruri cu aceeași expresie regulată sau căutarea în șiruri de dimensiuni mari.

Ca alternativă, stările automatului se pot construi pe măsură ce se validează șirul, nefiind necesară construirea inițială a întregului automat. Această soluție este mai lentă la căutare, necesitând un timp de ordinul produsului dintre dimensiunea șirului și dimensiunea expresiei regulate, dar, întrucât nu implică construcția automatului la început (în timp exponențial), poate fi mai rapidă la validarea unui număr mic de șiruri cu aceeași expresie sau la căutarea în texte mici.

Bibliografie[modificare | modificare sursă]

Vezi și[modificare | modificare sursă]

Legături externe[modificare | modificare sursă]