Expresie regulată

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Rezultatele unui match al șablonului 
(?<=\.) {2,}(?=[A-Z]).
Se caută cel puțin două spații sunt potrivite, dar numai dacă apar imediat după un punct (.) și înainte de o literă mare.
Stephen Cole Kleene, care a contribuit la punerea bazelor conceptului

O expresie regulată, regex sau regexp[1] (numită uneori expresie rațională)[2][3] este, în informatica teoretică⁠(d) și în teoria limbajelor formale, un șir de caractere⁠(d) care definesc un șablon⁠(d) de căutare. De obicei, acest șablon este apoi utilizat de către algoritmii de căutare pe șiruri⁠(d) pentru operațiuni de „căutare” sau „căutare și înlocuire” operațiuni pe șiruri de caractere⁠(d).

Conceptul a apărut în anii 1950, când matematicianul american Stephen Cole Kleene a formalizat descrierea unui limbaj regulat. Conceptul a intrat în uz comun împreună cu utilitarele de prelucrare a textului din Unix. Astăzi, există diferite sintaxe pentru scrierea expresiilor regulate, una fiind standardul POSIX⁠(d) și alta, utilizată pe scară largă, fiind sintaxa Perl.

Expresiile regulate sunt folosite în motoarele de căutare⁠(d), de dialogurile de căutare și înlocuire ale procesoarelor și editoarelor de text, în utilitare de prelucrare a textului, cum ar fi sed și AWK și în analiza lexicală. Multe limbaje de programare furnizează capabilități regex fie built-in, fie prin intermediul unor biblioteci⁠(d).

Șabloane[modificare | modificare sursă]

Sintagma expresii regulate (și, în consecință, regexuri) este adesea folosită cu referire la sintaxa standard, textuală (distinctă de notația matematică descrisă mai jos) pentru reprezentarea șabloanelor cărora trebuie să se conformeze textul găsit. Fiecare caracter dintr-o expresie regulată (adică fiecare caracter din șirul care descrie șablonul) este considerat a fi un metacaracter⁠(d) (caracter cu semnificație specială), sau un caracter obișnuit. De exemplu, în regexul a. a este un caracter literal, care se potrivește doar cu litera „a”, iar . este un meta-caracter care se potrivește cu orice caracter, cu excepția sfârșitului de linie. Prin urmare, acest regex ar identifica, de exemplu, șirurile „a” sau „ax” sau „a0”. Împreună, metacaracterele și caracterele literale pot fi utilizate pentru a identifica materialul textual pe anumit șablon, sau să prelucreze o serie de instanțe ale sale. Potrivirile pot varia de la o egalitate precisă la o asemănare foarte generală (controlată de metacaractere). De exemplu, . este un model general, [a-z] (care potrivește toate literele de la „a” la „z”) este mai puțin general și a este un șablon exact (se potrivește doar cu „o”). Sintaxa metacaracterelor este special concepută pentru a reprezenta obiective prescrise într-un mod concis și flexibil pentru a dirija automatizarea procesării de text pe o varietate de date de intrare, într-o formă ușor de introdus folosind o tastatură ASCII standard.

Un caz foarte simplu de expresie regulată în această sintaxă ar fi pentru a localiza același cuvânt scris în două moduri diferite într-un editor de text, expresia regulată p[âî]ine se potrivește atât cu „pâine”, cât și cu „pîine”. Wildcardurile⁠(d) ar putea realiza și ele acest lucru, dar sunt mai limitate în ceea ceea ce pot modela (având mai puține metacaractere și un limbaj de bază simplu).

Contextul obișnuit al caracterelor wildcard⁠(d) îl reprezintă gruparea unor denumiri similare dintr-o listă de fișiere, pe când regexurile sunt de obicei folosite în aplicații care efectuează identificări de șabloane pe șiruri de caractere de text în general. De exemplu, regexul ^[ \t]+|[ \t]+$ identifică excesul de spațiu de la începutul sau de la sfârșitul unei linii. Un regex mai avansat folosit pentru a identifica orice numeral este ^[+-]?(\d+(\.\d+)?|\.\d+)([eE][+-]?\d+)?$ . Vezi secțiunea de Exemple secțiunea pentru mai multe exemple.

Traducerea închiderii Kleene
(s* înseamnă „zero sau mai mulți de s”)

Un procesor regex traduce o expresie regulată scrisă în sintaxa de mai sus într-o reprezentare internă care poate fi executată și comparată cu un șir de caractere⁠(d) reprezentând textul în care se caută. O abordare posibilă este cea a algoritmului de construcție al lui Thompson pentru a construi un automat finit nedeterminist⁠(d) (AFN), care este apoi făcut determinist⁠(d) și AFD⁠(d)-ul rezultat este rulat pe șirul de text pentru a recunoaște cuvinte care se potrivesc cu expresia regulată. Imaginea prezinta schema AFN N(s*) obținută din expresia regulată s*, unde s reprezintă la rândul său o expresie regulată mai simplă, care a fost deja recursiv⁠(d) tradusă în AFN-ul N(s).

Istoria[modificare | modificare sursă]

Expresii regulate își au originea în 1956, când matematicianul Stephen Cole Kleene a descris limbajele regulate cu ajutorul notației sale matematice numită mulțimi regulate.[4] Acestea au apărut în informatica teoretică⁠(d), în subdomenii ale teoriei automatelor (modelelor de calcul) și în descrierea și clasificarea limbajelor formale. O altă implementare timpurie a identificării șabloanelor⁠(d) a fost limbajul SNOBOL⁠(d), care nu folosea expresii regulate, ci propriile sale construcții de identificare a șabloanelor.

Expresiile regulate au intrat în utilizarea populară în 1968 în două moduri: identificarea șabloanelor într-un editor de text[5] și analiza lexicală într-un compilator.[6] Printre primele apariții ale expresiilor regulate sub formă de program a fost atunci când Ken Thompson a integrat notația lui Kleene în editorul QED⁠(d) ca mijloc de a identifica șabloane în fișiere text.[5][7][8][9] Pentru viteză, Thompson a implementat potrivirea expresiilor regulate prin compilare just-in-time⁠(d) (JIT) în cod IBM 7090⁠(d) pe Compatible Time-Sharing System⁠(d), un exemplu important de compilare JIT timpurie.[10] Mai târziu, el a adăugat această capacitate la editorul Unix ed, care a facilitat în cele din urmă ca popularul instrument de căutare grep să utilizeze expresiile regulate („grep” este un cuvânt derivat din comanda de căutare de expresii regulate căutarea în editorul ed: g/re/p înseamnă „Global search for Regular Expression and Print matching lines” - „căutare globală de expresii regulate și tipărire a liniilor rezultate”[11]). Cam în același timp când Thompson dezvolta QED, un grup de cercetători din care făcea parte Douglas T. Ross⁠(d) a implementat un instrument bazat pe expresii regulate, care este utilizat pentru analiza lexicală⁠(d) în proiectarea compilatoarelor.[6]

În programele Unix[9] programe de la Bell Labs au fost utilizate multe variații ale acestor forme inițiale de expresii regulate în anii 1970, de exemplu în vi⁠(d), lex⁠(d), sed, AWK, și expr, și în alte programe, cum ar fi Emacs. Regexurile au fost ulterior adoptate de către o gamă largă de programe, aceste forme incipiente fiind standardizate în standardul POSIX.2 din 1992.

În 1980, au apărut regexuri mai complicate în Perl, care inițial au rezultat dintr-un bibliotecă de regex scrisă de Henry Spencer⁠(d) (1986), care a scris mai târziu o implementare a Advanced Regular Expressions pentru Tcl.[12] Biblioteca Tcl este o implementare hibridă de AFN⁠(d)/AFD⁠(d) cu performanțe îmbunătățite, lăudată de Jeffrey Friedl⁠(d), care a spus, „...pare chiar destul de minunată.”[13] Printre proiectele software care au adoptat implementarea de expresii regulate a lui Spencer din Tcl punerea în aplicare se numără PostgreSQL.[14] Perl a extins ulterior biblioteca inițială a lui Spencer pentru a adăuga mai multe caracteristici noi,[15] dar încă nu avea performanțele sau capabilitățile de manipulare Unicode pe care le avea Advanced Regular Expressions a lui Spencer.[16][17] O parte din efortul de proiectare pentru Perl 6⁠(d) îl reprezintă îmbunătățirea integrării regexurilor în Perl, și de a crește domeniul de aplicare a acestora și a capacităților pentru a permite definirea de gramatici de analiză sintactică⁠(d).[18] Rezultatul a fost un mini-limbaj⁠(d) numit regulile Perl 6⁠(d), utilizate pentru a defini gramatici Perl 6 și de a oferi un instrument pentru programatori ce folosesc acest limbaj. Aceste reguli menține caracteristicile existente ale regexurilor din Perl 5.x, dar permit și definiția în stil Backus-Naur⁠(d) ale unui parser cu coborâre recursivă⁠(d) prin intermediul sub-regulilor.

Utilizarea regexurilor în standardele deinformații structurate pentru modelarea documentelor și bazelor de date a început în anii 1960 și s-a extins în anii 1980, atunci când s-au consolidat standardele din industrie, cum ar fi ISO SGML⁠(d) (cu precursorul ANSI „GCA 101-1983”). Nucleul limbajului de specificare a structurii⁠(d) este format din regexuri. Utilizarea sa este evidentă în sintaxa DTD⁠(d).

Începând cu anul 1997, Philip Hazel⁠(d) a dezvoltat PCRE⁠(d) (Perl Compatible Regular Expressions), care încearcă să imite îndeaproape funcționalitatea regexurilor din Perl și este folosit de multe instrumente moderne, inclusiv de PHP și de Apache HTTP Server.

Astăzi, regexurile sunt suportate pe scară largă în limbaje de programare, în programe de procesare de text (lexere speciale), editoare de text avansate, și alte programe. Suportul pentru regex face parte din biblioteca standard a multor limbaje de programare, inclusiv Java și Python, și este integrată și în sintaxa altora, inclusiv Perl și ECMAScript. Implementările funcționalităților regex sunt adesea numite motoare regex, și există mai multe biblioteci disponibile pentru reutilizare.

Concepte de bază[modificare | modificare sursă]

O expresie regulată, de multe ori numită șablon (pattern), este o expresie folosită pentru a specifica o mulțime de șiruri de caractere necesară pentru un anumit scop. Un mod simplu de a specifica o mulțime finită de șiruri de caractere este de a enumera elementele sale. Cu toate acestea, există de multe ori moduri mai concise de a specifica mulțimea dorită de șiruri de caractere. De exemplu, mulțimea ce conține trei șiruri de caractere "Handel", "Händel", și "Haendel" poate fi specificată de șablonul H(ä|ae?)ndel; spunem că acest șablon se potrivește pe fiecare dintre cele trei șiruri de caractere. În cele mai multe formalisme, dacă există cel puțin o expresie regulată care se potrivește cu o anumită mulțime, atunci există un număr infinit de alte expresii regulată care se potrivesc—specificația nu este unică. Cele mai multe formalisme oferă următoarele operațiuni pentru a construi expresii regulate.

„Sau” logic (alternanța)
O bară verticală⁠(d) separă alternativele. De exemplu, gray|grey se poate potrivi cu „gray” sau cu „grey”.
Gruparea
Parantezele sunt folosite pentru a defini domeniul de aplicare și de precedență a operatorilor (printre alte utilizări). De exemplu, gray|grey și gr(a|e)y sunt șabloane echivalente care ambele descriu mulțimea formată din „gray” și „grey”.
Cuantificarea
Un cuantificator⁠(d) după un token⁠(d) (cum ar fi un caracter) sau un grup specifică de câte ori poate apărea precedentul element. Cei mai frecvenți cuantificatori sunt semnul de întrebare ?, asteriscul * (derivat din închiderea Kleene) și semnul plus⁠(d) + (plus Kleene).
? Semnul de întrebare indică zero sau una apariții ale elementului precedent. De exemplu, colou?r potrivește atât cu „colour”, cât și cu „color”.
* Asteriscul indică zero sau mai multe apariții ale elementului precedent. De exemplu, ab*c se potrivește cu „ac”, „abc”, „abbc”, „abbbc” și așa mai departe.
+ Semnul plus indică unul sau mai multe apariții ale elementului precedent. De exemplu, ab+c se potrivește cu „abc”, „abbc”, „abbbc” și așa mai departe, dar nu cu „ac”.
{n}[19] Elementul precedent apare exact de n ori.
{min} Elementul precedent apare de cel puțin min ori.
{min,max} Elementul precedent apare de cel puțin min ori, dar de cel mult max ori.

Aceste construcții pot fi combinate pentru a forma expresii arbitrar de complexe, așa cum se pot construi expresii aritmetice din numerele și operațiile +, , ×, ÷. De exemplu, H(ae?|ä)ndel și H(a|ae|ä)ndel sunt ambele șabloane valabile care se potrivesc cu aceleași șiruri ca în exemplul anterior, H(ä|ae?)ndel.

Sintaxa exactă a expresiilor regulate variază de la instrument la instrument și de la context la context; mai multe detalii sunt furnizate în secțiunea Sintaxă.

Teoria limbajelor formale[modificare | modificare sursă]

Expresiile regulate descriu limbaje regulate în teoria limbajelor formale. Ele au aceeași putere expresivă ca și gramaticile regulate⁠(d).

Definiție formală[modificare | modificare sursă]

Expresiile regulate constau din constante și operatori care notează mulțimi de șiruri de caractere și, respectiv, operațiuni efectuate pe aceste mulțimi. Următoarea definiție este una standard, găsită ca atare în majoritatea manualelor de limbaje formale.[20][21] Dat fiind un alfabet⁠(d) Σ finit, următoarele constante sunt, prin definiție, expresii regulate:

  • (mulțimea vidă) ∅ care reprezintă mulțimea ∅.
  • (șirul vid⁠(d)) ε care reprezintă mulțimea ce conține numai șirul „vid”, care nu are caractere.
  • (caracter literal⁠(d)) a din Σ care reprezintă mulțimea conținând doar caracterul a.

Date fiind expresiile regulate R și S, următoarele operațiuni efectuate cu ele produc expresii regulate:

  • (concatenare⁠(d)) RS reprezintă mulțimea șirurilor de caractere ce se obțin prin concatenarea unui șir din R cu un șir din S. De exemplu, {"ab", "c"}{"d", "ef"} = {"abd", "abef", "cd", "cef"}.
  • (alternarea⁠(d)) R | S reprezintă reuniunea⁠(d) mulțimilor descrise de R și S. De exemplu, dacă R descrie {"ab", "c"} și S describe {"ab", "d", "ef"}, atunci expresia R | S descrie {"ab", "c", "d", "ef"}.
  • (închiderea Kleene) R* reprezintă cea mai mică supermulțime a mulțimii descrise de R care conține ε și este închisă în raport cu concatenarea de șiruri. Aceasta este mulțimea tuturor șirurilor de caractere ce se pot consturi prin concatenarea de orice număr finit de ori (inclusiv de zero ori) a șirurilor din mulțimea descrisă de R. De exemplu, {"0","1"}* este mulțimea tuturor reprezentărilor binare⁠(d) (inclusiv șirul vid), iar {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", … }.

Pentru a evita parantezele, se presupune că închiderea Kleene are prioritatea cea mai mare, urmată fiind de concatenare și apoi de alternare. Dacă nu există ambiguitate, atunci parantezele se pot omite. De exemplu, (ab)c se poate scrie și ca abc, iar a|(b(c*)) se poate scrie ca a|bc*. Multe manuale folosesc simbolurile ∪, +, or ∨ pentru alternare, în locul barei verticale.

Examples:

  • a|b* reprezintă {ε, "a", "b", "bb", "bbb", ...}
  • (a|b)* reprezintă mulțimea tuturor șirurilor de caractere fără alte simboluri decât "a" și "b", inclusiv șirul vid: {ε, "a", "b", "aa", "ab", "ba", "bb", "aaa", ...}
  • ab*(c|ε) reprezintă mulțimea șirurilor de caractere care încep cu "a", apoi sunt urmate de zero sau mai mulți de "b"și în cele din urmă, opțional, un "c": {"a", "ac", "ab", "abc", "abb", "abbc", ...}
  • (0|(1(01*0)*1))* reprezintă mulțimea numerelor binare multipli de 3: { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }

Puterea expresivă și compactitatea[modificare | modificare sursă]

Definiția formală a expresiilor regulate este intenționat minimală și evită definirea cuantificatorilor redundanți ? și +, care pot fi exprimați după cum urmează: a+ = aa*, și a? = (a|ε). Uneori, se adaugă și operatorul complement⁠(d) pentru a da o expresie regulată generalizată; aici Rc se potrivește cu șirurile de caractere peste Σ* care nu se potrivesc cu R. În principiu, operatorul complement este redundant, deoarece rezultatul lui se poate obține cu ajutorul altor operatori. Cu toate acestea, procesul de calcul al unei astfel de reprezentări este complex, iar rezultatul poate necesita expresii de o dimensiune care este dublu exponențial⁠(d) mai mare.[22][23]

Expresiile regulate în acest sens pot exprima limbajele regulate, mai exact clasa limbajelor acceptate de automate finite deterministe⁠(d). Există, totuși, o diferență semnificativă de compactitate. Unele clase de limbaje regulate pot fi descrise numai prin automate finite deterministe a căror dimensiune crește exponențial în funcție de dimensiunea celei mai scurte expresii regulate echivalente. Exemplul standard îl constituie aici limbajele Lk formate din toate șirurile de caractere peste alfabetul {a,b} al căror literă la indicele k de la dreapta este egal cu a. Pe de o parte, o expresie regulată care descrie L4 este dată de .

Generalizând acest șablon la Lk rezultă expresia:


Pe de altă parte, este cunoscut faptul că fiecare automat finit determinist care acceptă limbajul Lk trebuie să aibă cel puțin 2k membri. Din fericire, există un mod simplu de mapare de la expresii regulate la automatele finite nedeterministe⁠(d) (AFN) mai generale, care nu prezintă o asemenea explozie a dimensiunii; pentru acest motiv, AFN-urile sunt adesea folosite ca reprezentări alternative ale limbajelor regulate. AFN-urile sunt o variație simplă a gramaticilor⁠(d) de tipul 3 din ierarhia Chomsky.

În cele din urmă, este de remarcat faptul că multe motoare de „expresii regulate” din lumea reală implementează caracteristici care nu pot fi descrise prin expresii regulate în sensul teoriei limbajelor formale; mai degrabă, acestea pun în aplicare regexuri. Vezi mai jos pentru mai multe detalii despre aceasta.

Decizia privind echivalența expresiilor regulate[modificare | modificare sursă]

După cum se vede în multe din exemplele de mai sus, există mai multe modalități de a construi o expresie regulată care dă aceleași rezultate.

Este posibil să se scrie un algoritm care, pentru anumite expresii regulate, decide dacă descriu limbaje similare; algoritmul reduce fiecare expresie la automatul finit determinist minimal⁠(d), și determină dacă acestea sunt izomorfe (echivalente).

Redundanța poate fi eliminată prin utilizarea închiderii Kleene și a reuniunii mulțimilor⁠(d) pentru a găsi o submulțime interesantă de expresii regulate care încă este complet expresivă, dar a căror utilizare poate fi limitată.[necesită clarificare] Acest lucru este surprinzător de dificil. Oricât de simple sunt expresiile regulate, nu există nicio metodă sistematică de a le rescrie într-o formă normală. Lipsa de axiome în trecut a condus la problema înălțimii stelei⁠(d). În 1991, Dexter Kozen⁠(d) a axiomatizat expresiile regulate cu algebra Kleene⁠(d).[24]

Sintaxa[modificare | modificare sursă]

Un șablon regex se potrivește cu n șir țintă. Modelul este compus dintr-o secvență de atomi. Un atom este un singur punct în modelul regex care încearcă să se potrivească cu șirul țintă. Cel mai simplu atom este un literal, dar gruparea unor părți din șablon pentru a se potrivi cu un atom necesită folosirea ( ) ca metacaractere. Metacaracterele ajută la formarea: atomilor; cuantificatorilor care spun câți atomi (și dacă cuantificatorul este greedy sau nu); un caracter SAU logic, care oferă un set de alternative, un caracter NU logic, care neagă existența unui atom; și backreferences ca referințe la atomi anteriori ai unui șablon de atomi. Potrivirea se face nu atunci când toți atomii din șir sunt potriviți, ci mai degrabă atunci când toții atomii din șablon s-au potrivit. Ideea este de a face ca șabloane mici de caractere să suporte un număr mare de șiruri de caractere posibile, mai degrabă decât să se compileze o listă lungă a tuturor literalilor posibili.

În funcție de procesorul regex, există aproximativ paisprezece metacaractere, caractere care pot sau nu să aibă sensul lor literal⁠(d), în funcție de context, sau dacă acestea sunt „escapate”, adică precedate de o secvență de escape⁠(d), în acest caz, backslash \. Regexurile moderne și cele cu extensii POSIX utilizează metacaracterele mai des decât sensul literal, astfel încât să se evite inundarea cu backslash-uri, este logic să existe un metacaracter de trecere la un mod literal; dar de la început, are mai mult sens ca cele patru caractere paranteze ( ) și { } să fie în primul rând literale, și să „scape” de acest sens obișnuit pentru a deveni metacaractere. Standardele comune le implementează pe ambele. De obicei, metacaractere sunt {}[]()^$.|*+? și \. Caracterele care devin de obicei devin metacaractere când sunt escapate sunt dsw.DSW și N.

Delimitatori[modificare | modificare sursă]

Atunci când se introduc regexuri într-un limbaj de programare, ele pot fi reprezentate ca șiruri de caractere obișnuite, prin urmare, de obicei, între ghilimele; acest lucru este comun în C, Java, Python, de exemplu, unde regexul re este introdus ca "re". Cu toate acestea, ele sunt adesea scrise cu slash-uri ca delimitatori⁠(d), adică /re/ reprezintă regexul re. Aceasta provine din ed, unde / este comanda de editor pentru căutare, iar expresia /re/ poate fi folosită pentru a specifica o gamă de rânduri (care să se potrivească cu șablonul), care puteau fi combinate cu alte comenzi de fiecare parte, cea mai celebră fiind g/re/p, de unde grep („global regex print”), care este inclusă în majoritatea sistemelor de operare pe bază de Unix, cum ar fi distribuțiile de Linux. O convenție similară este utilizată și în sed, unde căutarea și înlocuirea sunt date de s/re/înlocuire/ și șabloanele pot fi concatenate prin virgulă pentru a specifica mai multe rânduri, ca /re1/,/re2/. Această notație este deosebit de bine-cunoscută datorită utilizării sale în Perl, de unde formează parte a sintaxei diferite de șirurile de caractere literale normale. În unele cazuri, cum ar fi sed și Perl, se pot folosi delimitatori alternativi pentru a evita coliziunea cu conținutul, și pentru a evita necesitatea escapării apariției delimitatorului în conținut. De exemplu, în sed comanda s,/,X, va înlocui un / cu un X, folosind virgula ca delimitator.

Standardele[modificare | modificare sursă]

Standardul IEEE POSIX are trei seturi de conformitate: BRE (Basic Regular Expressions),[25] ERE (Extended Regular Expressions), și SRE (Simple Regular Expressions). SRE este depășit,[26] în favoarea lui BRE, ambele fiind compatibile înapoi. Subsecțiunea de mai jos ce acoperă clasele de caractere se aplică și la BRE și la ERE.

BRE ERE lucrează împreună. ERE adaugă ?, +, și |, și elimină necesitatea de a escapa metacaracterele ( ) și { }, care sunt obligatorii în BRE. În plus, atâta timp cât sintanxa standard POSIX pentru regexuri este respectată, poate exista, și adesea există, sintaxă suplimentară pentru a servi aplicații specifice (și totuși conforme POSIX). Deși POSIX.2 lasă unele aspecte de implementare nedefinite, BRE și ERE oferă un „standard”, care a fost adoptat ca sintaxă implicită de către mai multe instrumente, acolo unde alegerea modului BRE sau ERE este de obicei o opțiune acceptată. De exemplu, GNU grep are următoarele opțiuni: „grep -E” pentru ERE și „grep -G” pentru BRE (implicit), și „grep -P” pentru expresii Perl.

Regexurile Perl au devenit un standard de facto, având un set bogat și puternic de expresii atomice. Perl by are nivele de „bază” sau „extins” separate, unde ( ) și { } să poată avea sau nu sens literal. Ele sunt întotdeauna metacaractere, așa cum sunt și în modul „extins” pentru POSIX. Pentru a obține sensul lor literal, ele trebuie escapate. Alte metacaractere sunt cunoscute a fi literale sau simbolice doar în funcție de context. Perl oferă mult mai multe funcționalități: regexuri „lazy”, backtracking, grupuri de captură cu nume, și șabloane recursive⁠(d), toate completări puternice la POSIX BRE/ERE. (Vezi și potrivirea „lazy” de mai jos.)

POSIX de bază și extins[modificare | modificare sursă]

În standardul POSIX⁠(d), Basic Regular Syntax (BRE) impune ca metacaracterele⁠(d) ( ) și { } să fie notate cu \(\) și \{\}, pe când  Extended Regular Syntax (ERE) nu.

Metacaracter Descriere
. Se potrivește cu orice caracter individual (multe aplicații exclud sfârșiturile de linie⁠(d), și exact care caractere sunt considerate a fi sfârșituri de linie depinde de varianta de interpretor, de codificarea caracterelor și de platformă, dar se poate presupune că caracterul line feed este inclus). În interiorul parantezelor din expresiile POSIX, caracterul „punct” este literal. De exemplu, a.c se potrivește cu "abc" etc., dar [a.c] reprezintă doar "a", ".", sau "c".
[ ] Expresie-paranteză. Se potrivește cu un singur caracter conținut între paranteze. De exemplu, [abc] reprezintă "a", "b", sau "c". [a-z] specifică un interval ce se potrivește cu oricel literă mică între "a" și "z". Aceste forme pot fi amestecate: [abcx-z] reprezintă "a", "b", "c", "x", "y", sau "z", la fel ca [a-cx-z].

Caracterul - este tratat ca literal dacă este primul  (eventual după ^) sau ultimul caracter din paranteze: [abc-], [-abc]. Nu se permit escapări cu backslash. Caracterul ] poate fi inclus într-o expresie-paranteză dacă este primul (după ^) caracter: []abc].

[^ ] Reprezintă un singur caracter care nu este conținut între paranteze. De exemplu, [^abc] se potrivește cu orice caracter altul decât "a", "b", sau "c". [^a-z] se potrivește cu orice caracter unic care nu este o literă mică între "a" și "z". Caracterele literale și intervalele pot fi, la fel ca mai sus, amestecate.
^ Se potrivește cu începutul șirului. În uneltele pe rânduri, se potrivește cu începutul oricărui rând.
$ Se potrivește cu sfârșitul șirului, sau pe poziția de imediat înaintea unui sfârșit de linie de la sfârșitul șirului. În uneltele pe rânduri, se potrivește cu sfârșitul oricărui rând.
( ) Definește o subexpresie. Șirul potrivit în paranteze poate fi referențiat ulterior (vezi mai jos, \n). O subexpresie astfel marcată se numește și „bloc” sau „grup de captură”. Modul BRE necesită \( \).
\n Se potrivește cu ce s-a potrivit și a n-a subexpresie, unde n este o cifră de la 1 la 9. Această construcție este vag definită în standardul POSIX.2. Unele unelte permit referențierea a mai mult de nouă grupuri de captură.
* Se potrivește cu șirul ce cuprinde elementul precedent de zero sau mai multe ori. De exemplu, ab*cse potrivește cu "ac", "abc", "abbbc" etc. [xyz]* se potrivește cu "", "x", "y", "z", "zx", "zyx", "xyzzy", și așa mai departe. (ab)* se potrivește cu "", "ab", "abab", "ababab", și așa mai departe.
{m,n} Se potrivește cu elementul precedent de cel puțin m și cel mult n ori. De exemplu, a{3,5} se potrivește doar cu "aaa", "aaaa", și "aaaaa". Această funcționalitate nu există în instanțe mai vechi de regex. Modul BRE necesită \{m,n\}.

Exemple:

  • .at se potrivește cu orice șir de trei caractere terminat cu "at", inclusiv "hat", "cat", și "bat".
  • [hc]at se potrivește cu "hat" și "cat"
  • [^b]at se potrivește cu toate șirurile care se potrivesc cu .at cu excepția lui "bat".
  • [^hc]at se potrivește cu toate șirurile care se potrivesc cu .at cu excepția lui "hat" și "cat".
  • ^[hc]at se potrivește cu "hat" și "cat", dar numai de la începutul șirului sau rândului.
  • [hc]at$ se potrivește cu "hat" și "cat", dar numai la sfârșitul șirului sau rândului.
  • \[.\] se potrivește cu orice caracter unic, înconjurat de "[" și "]", întrucât parantezele sunt escapate, de exemplu: "[a]" și "[b]".
  • s.* se potrivește cu s urmat de zero sau mai multe caractere, de exemplu: "saw" și "seed".

POSIX extins[modificare | modificare sursă]

Sensul metacaracterelor escapate⁠(d) cu un backslash este inversat pentru unele caractere din sintaxa POSIX Extended Regular Expression (ERE). Cu această sintaxă, un backslash determină ca metacaracterul să fie tratat ca un literal. Astfel, de exemplu, \( \) este acum ( ) și \{ \} este acum { }. În plus, suportul este eliminat pentru backreferences \n și se adaugă următoarele metacaractere:

Metacaracter Descriere
? Se potrivește cu elementul anterior de zero ori sau o singură dată. De exemplu, ab?c se potrivește numai cu "ac" sau "abc".
+ Se potrivește cu elementul precedent de una sau de mai multe ori. De exemplu, ab+c se potrivește cu "abc", "abbc", "abbbc", și așa mai departe, dar nu "ac".
| Alternanța (cunoscută și sub numele de reuniune) se potrivește fie cu expresia dinainte, fie cu cea de după operator. De exemplu, abc|def se potrivește cu "abc" sau cu "def".

Exemple:

  • [hc]+at se potrivește cu "hat", "cat", "hhat", "chat", "hcat", "cchchat", și așa mai departe, dar nu cu "at".
  • [hc]?at se potrivește cu "hat", "cat", și "at".
  • [hc]*at se potrivește cu "hat", "cat", "hhat", "chat", "hcat", "cchchat", "at", și așa mai departe.
  • cat|dog se potrivește cu "cat" sau "dog".

POSIX Extended Regular Expressions pot fi folosite adesea cu utilitarele Unix moderne prin activarea flagului de linie de comandă -E.

Clase de caractere[modificare | modificare sursă]

Clasa de caractere este cel mai de bază concept al regexurilor după cel de literal. El face ca o secvență scurtă de caractere să se potrivească cu un șir mai mare. De exemplu, [A-Z] ar putea reprezenta întreg alfabetul majusculelor, iar \d ar putea însemna orice cifră. Clasele de caractere se aplică la ambele niveluri POSIX.

Atunci când se specifică un interval de caractere, cum ar fi [a-Z] (adică literele mici de la a la z), setările locale ale calculatorului determină conținutul ordonării numerice a codificării caracterelor. S-ar putea stoca simbolurile în ordine lexicografică, sau ordonarea ar putea fi abc...zABC...Z, sau aAbBcC...zZ. Așa că standardul POSIX definește o clasă de caractere, care va fi cunoscută de procesorul regex instalat. Aceste definiții sunt în tabelul următor:

POSIX Nestandard Perl/Tcl Vim Java ASCII Description
\p{ASCII} [\x00-\x7F] ASCII characters
[:alnum:] \p{Alnum} [A-Za-z0-9] Alphanumeric characters
[:word:] \w \w \w [A-Za-z0-9_] Alphanumeric characters plus "_"
\W \W \W [^A-Za-z0-9_] Non-word characters
[:alpha:] \a \p{Alpha} [A-Za-z] Alphabetic characters
[:blank:] \s \p{Blank} [ \t] Space and tab
\b \< \> \b (?<=\W)(?=\w)|(?<=\w)(?=\W) Word boundaries
\B (?<=\W)(?=\W)|(?<=\w)(?=\w) Non-word boundaries
[:cntrl:] \p{Cntrl} [\x00-\x1F\x7F] Control characters
[:digit:] \d \d \p{Digit} or \d [0-9] Digits
\D \D \D [^0-9] Non-digits
[:graph:] \p{Graph} [\x21-\x7E] Visible characters
[:lower:] \l \p{Lower} [a-z] Lowercase letters
[:print:] \p \p{Print} [\x20-\x7E] Visible characters and the space character
[:punct:] \p{Punct} [][!"#$%&'()*+,./:;<=>?@\^_`{|}~-] Punctuation characters
[:space:] \s \_s \p{Space} or \s [ \t\r\n\v\f] Whitespace characters
\S \S \S [^ \t\r\n\v\f] Non-whitespace characters
[:upper:] \u \p{Upper} [A-Z] Uppercase letters
[:xdigit:] \x \p{XDigit} [A-Fa-f0-9] Hexadecimal digits

Clasele de caractere POSIX pot fi utilizate numai în expresii cu paranteze. De exemplu, [[:upper:]ab] se potrivește cu literele mari și cu literele mici "a" și "b".

O clasă suplimentară non-POSIX înțeleasă de către unele instrumente este [:word:], care este de obicei definită ca [:alnum:] plus underscore. Acest lucru reflectă faptul că în multe limbaje de programare, acestea sunt caracterele care pot fi utilizate în identificatori. Editorul Vim distinge și clasele word și word-head (folosind notația \w și \h), deoarece în multe limbaje de programare caracterele ce pot apărea la începutul unui identificator nu sunt aceleași cu cele care pot apărea și în alte poziții în cadrul identificatorului.

Ceea ce standardele POSIX numesc clase de caractere sunt frecvent denumite clase de caractere POSIX în alte variante de regex care le suportă. Majoritatea variantelor de regex, termenul clasă de caractere este utilizat pentru a descrie ceea ce în POSIX se numește expresii cu paranteze.

Perl[modificare | modificare sursă]

Din cauza puterii sale de exprimare și a lizibilității (relativ) ușoare, multe alte utilitare și limbaje de programare au adoptat o sintaxă similară cu Perl—de exemplu, Java, JavaScript, Python, Ruby, Microsoft .NET Framework⁠(d), și XML Schema⁠(d). Unele limbi și instrumente, cum ar fi Boost⁠(en) și PHP suportă mai multe variante de regex. Implementările de regex derivate din Perl nu sunt identice și, de obicei, implementează un subset al facilităților găsite în Perl 5.0, lansat în 1994. Perl încorporează uneori caracteristici găsite inițial și în alte limbaje, de exemplu, Perl 5.10 implementează extensiile sintactice inițial dezvoltate în Perl Compatible Regular Expressions⁠(d) și Python.[27]

Potrivirea lazy[modificare | modificare sursă]

În Python și în alte implementări (de exemplu, Java), cei trei cuantificatori fecvenți (*, + și ?) sunt implicit greedy⁠(d), deoarece aceștia se potrivesc cu cât mai multe caractere posibil.[28] Regexul ".*" aplicat asupra șirului

"Ganymede," a continuat el, "este cel mai mare satelit din Sistemul Solar."

se potrivește cu întreaga linie în loc a se potrivi doar cu "Ganymede,". Cuantificatorii menționați pot fi făcuți și lazy sau minimali sau reticenți, așa încât să potrivească cât mai puține caractere posibil, astfel, prin adăugarea unui semn de întrebare: ".*?" șablonul de mai sus identifică doar "Ganymede,".

Potrivirea posesivă[modificare | modificare sursă]

În Java, cuantificatorii poate fi făcuți posesivi prin adăugarea unui semn plus, care dezactivează pașii înapoi în algoritmul backtracking de parcurgere a automatului, chiar dacă acești pași ar face să se găsească o potrivire:[29] Deși regexul ".*" aplicat pe șirul

"Ganymede," a continuat el, "este cel mai mare satelit din Sistemul Solar."

se potrivește cu întreaga linie, regexul ".*+" nu se potrivește cu nimic, pentru că .*+ consumă întreaga intrare, inclusiv " de la sfârșit. Astfel, cuantificatorii posesivi sunt cele mai utili cu clase de caractere negate, de exemplu cu "[^"]*+", care se potrivește cu "Ganymede," atunci când este aplicat pe același șir.

Cuantificatorii posesivi sunt mai ușor de implementat decât cei greedy și lazy, și sunt de obicei mai eficienți la runtime.

Șabloane pentru limbaje neregulate[modificare | modificare sursă]

Multe caracteristici găsite în aproape toate bibliotecile moderne de expresii regulate oferă o putere expresivă care depășește pe cea a limbajelor regulate. De exemplu, multe implementări permit gruparea subexpresiilor cu paranteze și reapelarea valorii care s-a potrivit deja în cadrul aceleeiași expresii (backreferences). Acest lucru înseamnă că, printre alte lucruri, un șablon poate compara șiruri de cuvinte repetate ca „papa” sau „WikiWiki”, numite în teoria limbajelor formale pătrate. Șablonul pentru aceste șiruri de caractere este (.+)\1.

Limbajul pătratelor nu este regulat, și nici independent de context, din cauza lemei de pompare⁠(d). Cu toate acestea, potrivirea șabloanelor⁠(d) cu un număr nelimitat de backreference-uri, așa cum este suportată de numeroase instrumente moderne, este încă dependentă de context⁠(d).[30]

Cu toate acestea, multe instrumente, biblioteci, și motoare care asigură astfel de construcții încă mai folosesc termenul expresie regulată pentru șabloanele lor. Acest lucru a condus la o nomenclatură în care termenul expresie regulată are o semnificație diferită în teoria limbajelor formale față de cea pe care o are în potrivirea șabloanelor. Din acest motiv, unii oameni folosesc termenul de regex, regexp, sau pur și simplu șablon sau pattern pentru a le descrie pe cele din urmă. Larry Wall, autorul limbajului de programare Perl, scria într-un eseu despre proiectarea Perl 6:{{Citat|"Expresiile regulate" […] sunt doar marginal legate de expresiile regulate adevărate. Chiar și așa, termenul s-a extins odată cu capabilitățile motoarelor noastre de potrivirea șabloanelor, așa că nu o să mă apuc acum să combat necesitățile lingvistice. Totuși, am să le numesc „regexuri”...Eroare la citare: Eticheta de închidere </ref> lipsește pentru eticheta <ref>[31]

Cel de-al treilea algoritm este potrivirea șablonului pe un șir de intrare prin backtracking. Acest algoritm este denumit în mod obișnuit AFN, dar această terminologie poate fi confuză. Timpul de funcționare poate fi exponențial, ceea ce se întâmplă cu implementările simple atunci când încearcă identificarea unei expresii ca (a|aa)*b , care conține atât alternanță cât și cuantificare nelimitată și forțează algoritmul să ia în considerare un număr de subcazuri care crește exponențial. Acest comportament poate provoca o problemă de securitate numită regular expression denial of service⁠(d).

Deși implementările de backtracking garantează doar timpi exponențiali în cel mai râu caz, ele oferă mult mai multă flexibilitate și putere expresivă. De exemplu, orice implementare care permite utilizarea de backreferences, sau pune în aplicare diferite extensii introduse de Perl, trebuie să includă un fel de backtracking. Unele implementari[care?] încearcă să ofere ce este mai bun în ambii algoritmi, executând la început un algoritm AFD rapid, recurgând la un algoritm potențial mai lent cu backtracking numai atunci când se întâlnește un backreference în timpul potrivirii.

Unicode[modificare | modificare sursă]

Din punct de vedere teoretic, orice set de tokenuri poate fi potrivit prin expresii regulate, atâta timp cât este predefinit. În termeni de implementări istorice, regexurile au fost inițial scrise pentru a utiliza caractere ASCII, deși există biblioteci de regex care suportă și alte seturi de caractere⁠(d). Multe motoare regex moderne oferă cel puțin suport parțial pentru Unicode. În cele mai multe privințe, nu contează care este setul de caractere, dar apar totuși unele probleme atunci când se extinde regexul cu suport Unicode.

  • Codificare suportată. Unele biblioteci de regex se așteaptă să meargă pe anumite codificări în locul caracterelor Unicode abstracte. Multe dintre acestea necesită codificarea UTF-8⁠(d), în timp ce altele ar putea aștepta UTF-16⁠(d) sau UTF-32⁠(d). Invers, Perl și Java sunt agnostice în ce privește codificările, operând în schimb pe caractere decodificate intern.
  • Game Unicode suportate. Multe motoare de regex suportă numai Plane (Unicode)⁠(d), adică acele caractere care pot fi codificate pe doar 16 biți. Actualmente, doar câteva motoare de regex (de exemplu, cele din Perl și Java) pot trata toată gama Unicode de 21 de biți.
  • Extinderea la Unicode a construcțiilor orientate către ASCII. De exemplu, în implementările pe bază de ASCII, gamele de caractere de forma [x-y] sunt valide atunci când x și y au coduri⁠(d) în gama [0x00,0x7F] și când codepoint(x) ≤ codepoint(y). Extensia naturală a acestor game de caractere la Unicode ar schimba cerința ca codurile lor să fie în gama [0x00,0x7F] la cea ca ele să fie în gama [0x0000,0x10FFFF]. În practică, însă, nu prea este cazul. Unele implementări, cum ar fi cea din gawk, nu permit ca gamele de caractere să traverseze limitele de blocuri Unicode. O gamă ca [0x61,0x7F] este validă deoarece ambele capete sunt în interiorul blocului Basic Latin, și la fel și [0x0530,0x0560] deoarece ambele capete sunt în interiorul blocului caracterelor armenești, dar o gamă ca [0x0061,0x0532] este invalidă deoarece cuprinde multiple blocuri Unicode. Alte motoare, cum ar fi cel din editorul Vim, permit traversarea limitelor de bloc, dar valorile caracterelor nu pot fi mai depărtate de 256 de poziții.[32]
  • Case insensitivity. Unele flaguri de case-insensitivity afectează doar caracterele ASCII. Altele afectează toate caracterele. Unele motoare au două flaguri diferite, unul pentru ASCII, altul pentru Unicode. Variază și apartenența caracterelor la clasele POSIX.
  • Concepte înrudite cu case insensitivity. Cum ASCII face distincția între litere mari și mici, conceptul acesta de case insensitivity a devenit o caracteristică logică a căutării de texte. Unicode a introdus scrieri alfabetice fără această distincție, cum ar fi Devanagari. Acestora nu li se poate aplica conceptul de case sensitivity⁠(d). Pentru scrieri cum ar fi cea chineză, pare logică o altă distincție: cea între tradițional și simplificat. În simbolurile alfabetului arab, ar putea fi de dorit distincția între pozițiile inițială, medială, finală și izolată⁠(d). În japoneză, s-ar putea să se dorească să se ignore diferența între hiragana și katakana.
  • Normalizarea. Unicode are și caractere combinabile. Ca și la vechile mașini de scris, literele simple pot fi urmate de unul sau mai multe caractere nespațiate (de regulă diacritice și accente) pentru a forma un unic caracter tipărit, dar furnizează și caractere precompuse, care deja includ unul sau mai multe caractere combinabile. Un șir format dintr-un caracter + un caracter combinabil ar trebui să se potrivească cu caracterul precompus identic simplu. Procesul de standardizare a șirurilor de caractere cu caractere combinabile se numește normalizare.
  • Noi coduri de control. Unicode a introdus, printre altele, semne de ordonarea octeților și pentru direcția textului. Aceste coduri pot pune probleme speciale.
  • Introducerea de clase de caractere pentru blocuri Unicode, alfabete, și numeroase alte proprietăți. Proprietățile pe blocuri sunt mult mai puțin utile decât cele pe alfabete, întrucât un bloc poate avea coduri din alfabete diferite, iar un alfabet poate avea coduri împrăștiate în multiple blocuri.[33] În Perl și în biblioteca Format:Javadoc:SE, proprietățile de forma \p{InX} sau \p{Block=X} se potrivesc cu caractere din blocul X iar \P{InX} sau \P{Block=X} se potrivesc cu coduri care nu se află în blocul respectiv. Analog, \p{Armenian}, \p{IsArmenian}, ori \p{Script=Armenian} se potrivesc cu orice caracter din alfabetul armenesc. În general, \p{X} se potrivește cu orice caracter care fie are proprietatea binară X fie este în categoria generală X. De exemplu, \p{Lu}, \p{Uppercase_Letter}, sau \p{GC=Lu} se potrivesc cu orice literă mare. Între proprietățile binare care nu sunt categorii generale se numără \p{White_Space}, \p{Alphabetic}, \p{Math} și \p{Dash}. Exemple de proprietăți nebinare sunt \p{Bidi_Class=Right_to_Left}, \p{Word_Break=A_Letter}, și \p{Numeric_Value=10}.

Folosește[modificare | modificare sursă]

Regexurile sunt utile într-o varietate de taskuri ce implică prelucrarea textului⁠(d) și, mai mult, prelucrarea șirurilor de caractere în general, în care datele nu trebuie neapărat să fie textuale. Printre aplicațiile comune se numără validarea datelor⁠(d), scrapingul de date⁠(d) (mai ales Web scraping⁠(d)), conversiile datelor între formate⁠(d), parsări simple, producerea de sisteme de evidențierea sintaxei⁠(d), și multe alte operațiuni.

În timp ce regexurile ar fi utile în motoarele de căutare pe Internet, procesarea acestora pe întregi baze de date ar putea consuma excesiv resurse de calcul în funcție de complexitatea și designul regexului. Deși, în multe cazuri, administratorii de sistem pot rula regexuri pe bază de interogări pe plan intern, cele mai multe motoare de căutare nu oferă suport de regex pentru public. O excepție notabilă este Exalead⁠(d).[34][necesită sursă mai bună]

Exemple[modificare | modificare sursă]

Regulile specifice de sintaxă pot varia în funcție de implementarea specifică, în funcție de limbajul de programare, sau de biblioteca⁠(d) utilizată. În plus, funcționalitatea implementării de regex poate varia de la o versiune⁠(d) la alta.

Pentru că regexurile pot fi dificil atât de explicat cât și de înțeles fără exemple, site-urile web interactive pentru testarea regexurilor sunt o resursă utilă pentru învățarea regexurilor prin experimentare. Această secțiune oferă o descriere de bază a unor proprietăți ale modului de ilustrare al regexurilor.

În exemple se folosesc următoarele convenții.[35]

metacaracter(e) ;; coloana metacaracterelor specifică sintaxa regex demonstrată
=~ m// ;; indică o operațiune de potrivire regex în Perl
=~ s/// ;; indică o operațiune de substituție în Perl

De asemenea, aceste regexuri sunt toate în sintaxa Perl. Expresiile pe standardul POSIX sunt diferite.

Dacă nu se indică altfel, următoarele exemple sunt conforme limbajului Perl, versiunea 5.8.8 din 31 ianuarie 2006. Aceasta înseamnă că altor implementări le poate lipsi suportul pentru unele părți ale sintaxei prezentate aici (de exemplu, regex de bază vs extins, \( \) vs (), sau lipsa lui \d în locul lui [:digit:]din POSIX).

Sintaxa și convențiile utilizate în aceste exemple coincid cu cele ale altor medii de programare, precum.[36]

Inducție[modificare | modificare sursă]

Expresiile regulate pot fi de multe ori create („induse” sau „învățate”), pe baza unui set de exemplu de șiruri de caractere. Acest lucru este cunoscut sub numele de inducție a limbajelor regulate⁠(d), și face parte din problema generală a inducției gramaticale⁠(d) în teoria învățării automate⁠(d). Formal, date fiind exemple de șiruri de caractere dintr-un limbaj regulat, și eventual și exemple de șiruri de caractere care nu fac parte din limbajul regulat, se poate induce o gramatică a limbajului, adică o expresie regulată care generează limbajul. Nu toate limbajele pot fi induse în acest fel, dar multe pot fi. De exemplu, setul de exemple {1, 10, 100}, și setul de contraexemple {11, 1001, 101, 0} pot fi folosite pentru a induce expresia regulată 1⋅0* (1 urmat de zero sau mai multe 0-uri).

Note[modificare | modificare sursă]

  1. ^ What Regular Expressions Are Exactly - Terminology
  2. ^ Ruslan Mitkov (2003). The Oxford Handbook of Computational Linguistics. Oxford University Press. p. 754. ISBN 978-0-19-927634-9. https://books.google.com/books?id=yl6AnaKtVAkC&pg=PA754 
  3. ^ Mark V. Lawson (17 septembrie 2003). Finite Automata. CRC Press. pp. 98–100. ISBN 978-1-58488-255-8. https://books.google.com/books?id=MDQ_K7-z2AMC&pg=PA98 
  4. ^ Kleene 1956.
  5. ^ a b Thompson 1968.
  6. ^ a b Johnson et al. 1968.
  7. ^ Kernighan, Brian. „A Regular Expressions Matcher”. Beautiful Code. O'Reilly Media⁠(d). pp. 1–2. ISBN 978-0-596-51004-6. http://www.cs.princeton.edu/courses/archive/spr09/cos333/beautiful.html. Accesat la 15 mai 2013 
  8. ^ Ritchie, Dennis M.. „An incomplete history of the QED Text Editor. http://cm.bell-labs.com/who/dmr/qed.html. Accesat la 9 octombrie 2013. 
  9. ^ a b Aho & Ullman 1992, 10.11 Bibliographic Notes for Chapter 10, p. 589.
  10. ^ Aycock 2003, 2. JIT Compilation Techniques, 2.1 Genesis, p. 98.
  11. ^ Raymond, Eric S.⁠(d) citing Dennis Ritchie (2003). „Jargon File 4.4.7: grep. http://catb.org/jargon/html/G/grep.html. 
  12. ^ New Regular Expression Features in Tcl 8.1. http://www.tcl.tk/doc/howto/regexp81.html. Accesat la 11 octombrie 2013. 
  13. ^ Friedl, Jeffrey. „The Mechanics of Expression Processing”. Mastering Regular Expressions. O'Reilly Media⁠(d). pp. 182. ISBN 0-596-52812-4 
  14. ^ PostgreSQL 9.3.1 Documentation: 9.7. Pattern Matching. http://www.postgresql.org/docs/9.3/interactive/functions-matching.html. Accesat la 12 octombrie 2013. 
  15. ^ Wall, Larry and the Perl 5 development team (2006). „perlre: Perl regular expressions. http://perldoc.perl.org/perlre.html. 
  16. ^ Unicode and Localisation Support. http://perldoc.perl.org/perlreguts.html#Unicode-and-Localisation-Support. Accesat la 11 octombrie 2013. 
  17. ^ Russ Cox (2007). „Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …). http://swtch.com/~rsc/regexp/regexp1.html. Accesat la 11 octombrie 2013. 
  18. ^ Wall (2002)
  19. ^ grep(1) man page
  20. ^ Hopcroft, Motwani & Ullman (2000)
  21. ^ Sipser (1998)
  22. ^ Gelade & Neven (2008)
  23. ^ Gruber & Holzer (2008)
  24. ^ Kozen (1991)[necesită pagina]
  25. ^ ISO/IEC 9945-2:1993 Information technology – Portable Operating System Interface (POSIX) – Part 2: Shell and Utilities, successively revised as ISO/IEC 9945-2:2002 Information technology – Portable Operating System Interface (POSIX) – Part 2: System Interfaces, ISO/IEC 9945-2:2003, and currently ISO/IEC/IEEE 9945:2009 Information technology – Portable Operating System Interface (POSIX®) Base Specifications, Issue 7
  26. ^ The Single Unix Specification (Version 2)
  27. ^ Perl Regular Expression Documentation”. perldoc.perl.org. http://perldoc.perl.org/perlre.html#PCRE%2fPython-Support. Accesat la 8 ianuarie 2012. 
  28. ^ Regular Expression Syntax”. Python Software Foundation⁠(d). https://docs.python.org/3/library/re.html#regular-expression-syntax. Accesat la 10 octombrie 2015. 
  29. ^ Essential classes: Regular Expressions: Quantifiers: Differences Among Greedy, Reluctant, and Possessive Quantifiers”. O=racle. https://docs.oracle.com/javase/tutorial/essential/regex/quant.html#difs. Accesat la 23 decembrie 2016. 
  30. ^ Cezar Câmpeanu and Kai Salomaa, and Sheng Yu (1 decembrie 2003). „A Formal Study of Practical Regular Expressions”. International Journal of Foundations of Computer Science 14 (6): 1007–1018. http://137.149.157.5/Articles/index.php?aid=1. 
  31. ^ Laurikari (2009)
  32. ^ Vim documentation: pattern”. Vimdoc.sourceforge.net. http://vimdoc.sourceforge.net/htmldoc/pattern.html#/%5B%5D. Accesat la 25 septembrie 2013. 
  33. ^ UTS#18 on Unicode Regular Expressions, Annex A: Character Blocks. http://unicode.org/reports/tr18/#Character_Blocks. Accesat la 5 februarie 2010. 
  34. ^ Replacement for Google Code Search?. https://stackoverflow.com/questions/7778034/replacement-for-google-code-search. 
  35. ^ The character 'm' is not always required to specify a Perl match operation.
  36. ^ E.g., see Java in a Nutshell⁠(en), p. 213; Python Scripting for Computational Science, p. 320; Programming PHP, p. 106.

Bibliografie[modificare | modificare sursă]