Expresie regulată
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/23/The_river_effect_in_justified_text.jpg/220px-The_river_effect_in_justified_text.jpg)
(?<=\.) {2,}(?
=[A-Z])
.Se caută cel puțin două spații, dar numai dacă apar imediat după un punct (.) și înainte de o literă mare.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Kleene.jpg/220px-Kleene.jpg)
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 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 ș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
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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/8/8e/Thompson-kleene-star.svg/220px-Thompson-kleene-star.svg.png)
(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
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 Raku(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ă
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
șigr(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
Expresiile regulate descriu limbaje regulate în teoria limbajelor formale. Ele au aceeași putere expresivă ca și gramaticile regulate(d).
Definiție formală
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 Σ 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 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.
Exemple:
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
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 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
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 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
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
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
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
În standardul POSIX, Basic Regular Syntax (BRE) impune ca metacaracterele(d) ( )
și { }
să fie notate cu \(\)
și \{\}
, pe când Extended Regular Syntax (ERE) nu.
\( \)
\( \)
{m,n}
{m,n}
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 |
[^ ] | 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*c se 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
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
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
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, și XML Schema(d). Unele limbi și instrumente, cum ar fi Boost(en)[traduceți] ș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
În Python și în alte implementări (de exemplu, Java), cei trei cuantificatori fecvenți (*
, +
și ?
) sunt implicit greedy, 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ă
Î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
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:
„"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”...[18]”
Regexuri fuzzy
Unele variante de regex poate fi folosite pentru lucrul cu text în limbaj natural, atunci când este necesar să se ia în considerare posibilele greșeli de ortografie și variante de ortografie. De exemplu, textul „Iulius Cezar” ar putea fi o potrivire fuzzy pentru:
- Gaius Iulius Cezar
- Yulius Cesar
- G. Julius Caezar
În astfel de cazuri, mecanismul implementează un algoritm fuzzy de identificare a șirurilor(d) și, eventual, un algoritm pentru găsirea similitudinilor(d) între fragmentul de text și șablon.
Această sarcină este strâns legată de căutarea în texte(d) și recunoașterea entităților cu nume.
Unele biblioteci software(d) lucrează cu regexuri fuzzy:
- TRE(d) – proiect liber și bine dezvoltat în C, care utilizează o sintaxă similară cu POSIX
- FREJ – proiect open source în Java cu sintaxă nestandard (care utilizează o notație prefixată, în stil Lisp), orientate spre a permite o utilizare ușoară a substituțiilor fragmentelor interne identificate din blocuri exterioare, fără a avea însă multe caracteristici ale regexurilor standard.
- agrep – utilitar open source în linie de comandă.
Implementări și timpi de rulare
Există cel puțin trei tipuri diferite de algoritmi care decid dacă și cum se potrivește un anumit regex cu un șir de caractere.
Cea mai vechi și mai rapidă se bazează pe un rezultat din teoria limbajelor formale, care permite ca fiecare automat finit nedeterminist(d) (AFN) să fie transformat într-un automat finit determinist(d) (AFD). AFD-ul poate fi construit în mod explicit și apoi executat pe șirul de intrare simbol cu simbol. Construirea AFD pentru o expresie regulată de dimensiune m are complexitatea în timp și spațiu O(2m), dar poate fi rulată pe un șir de caractere de dimensiune n într-un timp O(n).
O abordare alternativă este aceea de a simula AFN-ul direct, construind practic la cerere fiecare stare a AFD-ului și apoi renunțând la ea în pasul următor. Acest lucru face ca AFD-ul să fie doar implicit și evită costurile exponențiale de construcție a lui, dar și costurile de funcționare se ridică la O(mn). Abordarea explicită se numește „algoritmul AFD” și cea implicită - algoritmul AFN. Adăugarea de caching pentru algoritmul AFN este adesea numită „algoritmul AFD lazy”, sau „algoritmul AFD”, fără a face o distincție. Acești algoritmi sunt rapizi, dar folosirea lor pentru obținerea subexpresiilor grupate, pentru cuantificarea lazy, și alte caracteristici similare este complicată.[31][32]
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
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 Unicode plane(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.[33] - 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.[34] În Perl și în biblioteca
java.util.regex
, 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}
.
Utilizare
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).[35][necesită sursă mai bună]
Exemple
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.[a]
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.[36]
Meta- caracter(e) | Descriere | Exemple[b] |
---|---|---|
. | Se potrivește în mod normal cu orice caracter cu excepția unui sfârșit de linie. În paranteze drepte, punctul este un literal. | $string1 = "Hello World\n"; if ($string1 =~ m/...../) { print "$string1 are lungime >= 5.\n"; } Rezultat: Hello World are lungime >= 5. |
( ) | Grupează o serie de elemente de șablon într-unul singur. La potrivirea expresie dintre paranteze, se poate folsi $1 , $2 , … ulterior pentru a face referire la textul anterior potrivit. | $string1 = "Hello World\n"; if ($string1 =~ m/(H..).(o..)/) { print "We matched '$1' and '$2'.\n"; } Rezultat: We matched 'Hel' and 'o W'. |
+ | Potrivește elementul anterior o dată sau de mai multe ori. | $string1 = "Hello World\n"; if ($string1 =~ m/l+/) { print "There are one or more consecutive letter \"l\"'s in $string1.\n"; } Rezultat: There are one or more consecutive letter "l"'s in Hello World. |
? | Potrivește prezența elementului anterior o dată sau deloc. | $string1 = "Hello World\n"; if ($string1 =~ m/H.?e/) { print "There is an 'H' and a 'e' separated by "; print "0-1 characters (e.g., He Hue Hee).\n"; } Rezultat: There is an 'H' and a 'e' separated by 0-1 characters (e.g., He Hue Hee). |
? | Modifică expresia cu * , + , ? sau {M,N} astfel încât să se potrivească cu cât mai puține caractere. | $string1 = "Hello World\n"; if ($string1 =~ m/(l.+?o)/) { print "The non-greedy match with 'l' followed by one or\n"; print "more characters is 'llo' rather than 'llo Wo'.\n"; } Rezultat: The non-greedy match with 'l' followed by one or more characters is 'llo' rather than 'llo Wo'. |
* | Potrivește prezența elementului anterior de oricâte ori (inclusiv zero). | $string1 = "Hello World\n"; if ($string1 =~ m/el*o/) { print "There is an 'e' followed by zero to many "; print "'l' followed by 'o' (e.g., eo, elo, ello, elllo).\n"; } Rezultat: There is an 'e' followed by zero to many 'l' followed by 'o' (e.g., eo, elo, ello, elllo). |
{M,N} | Notează o potrivire de minim M și maxim N ori. N poate fi omis, iar M poate fi 0: {M} se potrivește de „exact” M ori; {M,} se potrivește „de cel puțin” M ori; {0,N} se potrivește „de cel mult” N ori.x* y+ z? este astfel echivalent cu x{0,} y{1,} z{0,1} . | $string1 = "Hello World\n"; if ($string1 =~ m/l{1,2}/) { print "There exists a substring with at least 1 "; print "and at most 2 l's in $string1\n"; } Rezultat: There exists a substring with at least 1 and at most 2 l's in Hello World |
[…] | Notează un set de potriviri posibile cu caractere. | $string1 = "Hello World\n"; if ($string1 =~ m/[aeiou]+/) { print "$string1 contains one or more vowels.\n"; } Rezultat: Hello World contains one or more vowels. |
| | Separă posibilitățile alternative. | $string1 = "Hello World\n"; if ($string1 =~ m/(Hello|Hi|Pogo)/) { print "$string1 contains at least one of Hello, Hi, or Pogo."; } Rezultat: Hello World contains at least one of Hello, Hi, or Pogo. |
\b | Se potrivește cu marginea cuvântului (potrivire de lungime zero); la fel ca
| $string1 = "Hello World\n"; if ($string1 =~ m/llo\b/) { print "There is a word that ends with 'llo'.\n"; } Rezultat: There is a word that ends with 'llo'. |
\w | Se potrivește cu un caracter alfanumeric, inclusiv cu "_"; la fel ca [A-Za-z0-9_] în ASCII, și
în Unicode,[34] unde proprietatea | $string1 = "Hello World\n"; if ($string1 =~ m/\w/) { print "There is at least one alphanumeric "; print "character in $string1 (A-Z, a-z, 0-9, _).\n"; } Rezultat: There is at least one alphanumeric character in Hello World (A-Z, a-z, 0-9, _). |
\W | Se potrivește cu un caracter nealfanumeric, excluzând "_"; ca și [^A-Za-z0-9_] în ASCII, și
în Unicode. | $string1 = "Hello World\n"; if ($string1 =~ m/\W/) { print "The space between Hello and "; print "World is not alphanumeric.\n"; } Rezultat: The space between Hello and World is not alphanumeric. |
\s | Se potrivește cu un caracter de whitespace, care în ASCII sunt tab, line feed, form feed, carriage return, și space; în Unicode, se potrivește și cu no- | $string1 = "Hello World\n"; if ($string1 =~ m/\s.*\s/) { print "In $string1 there are TWO whitespace characters, which may"; print " be separated by other characters.\n"; } Rezultat: In Hello World there are TWO whitespace characters, which may be separated by other characters. |
\S | Se potrivește cu orice în afară de whitespace. | $string1 = "Hello World\n"; if ($string1 =~ m/\S.*\S/) { print "In $string1 there are TWO non-whitespace characters, which"; print " may be separated by other characters.\n"; } Rezultat: In Hello World there are TWO non-whitespace characters, which may be separated by other characters. |
\d | Se potrivește cu o cifră; la fel ca [0-9] în ASCII; în Unicode, la fel ca proprietățile \p{Digit} sau \p{GC=Decimal_Number} , care la rândul lor sunt similare proprietății \p{Numeric_Type=Decimal} . | $string1 = "99 bottles of beer on the wall."; if ($string1 =~ m/(\d+)/) { print "$1 is the first number in '$string1'\n"; } Rezultat: 99 is the first number in '99 bottles of beer on the wall.' |
\D | Se potrivește cu orice în afară de cifră; la fel ca [^0-9] în ASCII sau \P{Digit} în Unicode. | $string1 = "Hello World\n"; if ($string1 =~ m/\D/) { print "There is at least one character in $string1"; print " that is not a digit.\n"; } Rezultat: There is at least one character in Hello World that is not a digit. |
^ | Se potrivește cu începutul unei linii sau al șirului. | $string1 = "Hello World\n"; if ($string1 =~ m/^He/) { print "$string1 starts with the characters 'He'.\n"; } Rezultat: Hello World starts with the characters 'He'. |
$ | Se potrivește cu sfârșitul liniei sau șirului. | $string1 = "Hello World\n"; if ($string1 =~ m/rld$/) { print "$string1 is a line or string "; print "that ends with 'rld'.\n"; } Rezultat: Hello World is a line or string that ends with 'rld'. |
\A | Se potrivește cu începutul șirului (dar nu al liniei). | $string1 = "Hello\nWorld\n"; if ($string1 =~ m/\AH/) { print "$string1 is a string "; print "that starts with 'H'.\n"; } Rezultat: Hello World is a string that starts with 'H'. |
\z | Se potrivește cu sfârșitul șirului (dar nu al unei linii).[37] | $string1 = "Hello\nWorld\n"; if ($string1 =~ m/d\n\z/) { print "$string1 is a string "; print "that ends with 'd\\n'.\n"; } Rezultat: Hello World is a string that ends with 'd\n'. |
[^…] | Se potrivește cu toate caracterele cu excepția celor din paranteze. | $string1 = "Hello World\n"; if ($string1 =~ m/[^abc]/) { print "$string1 contains a character other than "; print "a, b, and c.\n"; } Rezultat: Hello World contains a character other than a, b, and c. |
Inducție
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 de completare
Note bibliografice
- ^ What Regular Expressions Are Exactly - Terminology
- ^ Ruslan Mitkov (). The Oxford Handbook of Computational Linguistics. Oxford University Press. p. 754. ISBN 978-0-19-927634-9.
- ^ Mark V. Lawson (). Finite Automata. CRC Press. pp. 98–100. ISBN 978-1-58488-255-8.
- ^ Kleene 1956.
- ^ a b Thompson 1968.
- ^ a b Johnson et al. 1968.
- ^ Kernighan, Brian. „A Regular Expressions Matcher”. Beautiful Code. O’Reilly Media(d). pp. 1–2. ISBN 978-0-596-51004-6. Accesat în .
- ^ Ritchie, Dennis M. „An incomplete history of the QED Text Editor”. Arhivat din original la . Accesat în .
- ^ a b Aho & Ullman 1992, 10.11 Bibliographic Notes for Chapter 10, p. 589.
- ^ Aycock 2003, 2. JIT Compilation Techniques, 2.1 Genesis, p. 98.
- ^ Raymond, Eric S. citing Dennis Ritchie (). „Jargon File 4.4.7: grep”.
- ^ „New Regular Expression Features in Tcl 8.1”. Accesat în .
- ^ Friedl, Jeffrey. „The Mechanics of Expression Processing”. Mastering Regular Expressions. O’Reilly Media(d). p. 182. ISBN 0-596-52812-4.
- ^ „PostgreSQL 9.3.1 Documentation: 9.7. Pattern Matching”. Accesat în .
- ^ Wall, Larry and the Perl 5 development team (). „perlre: Perl regular expressions”.
- ^ „Unicode and Localisation Support”. Accesat în .
- ^ Russ Cox (). „Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, …)”. Accesat în .
- ^ a b Wall (2002)
- ^ grep(1) man page
- ^ Hopcroft, Motwani & Ullman (2000)
- ^ Sipser (1998)
- ^ Gelade & Neven (2008)
- ^ Gruber & Holzer (2008)
- ^ Kozen (1991)[necesită pagina]
- ^ 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
- ^ The Single Unix Specification (Version 2)
- ^ „Perl Regular Expression Documentation”. perldoc.perl.org. Accesat în .
- ^ „Regular Expression Syntax”. Python 3.5.0 documentation. Python Software Foundation(d). Accesat în .
- ^ „Essential classes: Regular Expressions: Quantifiers: Differences Among Greedy, Reluctant, and Possessive Quantifiers”. The Java Tutorials. O=racle. Accesat în .
- ^ Cezar Câmpeanu and Kai Salomaa, and Sheng Yu (). „A Formal Study of Practical Regular Expressions”. International Journal of Foundations of Computer Science. 14 (6): 1007–1018.
- ^ Cox (2007)
- ^ Laurikari (2009)
- ^ „Vim documentation: pattern”. Vimdoc.sourceforge.net. Accesat în .
- ^ a b „UTS#18 on Unicode Regular Expressions, Annex A: Character Blocks”. Accesat în .
- ^ „Replacement for Google Code Search?”.
- ^ Vezi, de exemplu, Java in a Nutshell(en)[traduceți], p. 213; Python Scripting for Computational Science, p. 320; Programming PHP, p. 106.
- ^ Conway, Damian (). „Regular Expressions, End of String”. Perl Best Practices. O'Reilly. p. 240. ISBN 978-0-596-00173-5.
Bibliografie
- Aho, Alfred V. (). van Leeuwen, Jan, ed. Algorithms for finding patterns in strings. Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity. The MIT Press. pp. 255–300.
- Aho, Alfred V.; Ullman, Jeffrey D. (). „Chapter 10. Patterns, Automata, and Regular Expressions” (PDF). Foundations of Computer Science.
- „Regular Expressions”. The Single UNIX ® Specification, Version 2. The Open Group. .
- „Chapter 9: Regular Expressions”. The Open Group Base Specifications Issue 6, IEEE Std 1003.1, 2004 Edition. The Open Group. .
- Cox, Russ (). „Regular Expression Matching Can Be Simple and Fast”.
- Forta, Ben (). Sams Teach Yourself Regular Expressions in 10 Minutes. Sams. ISBN 0-672-32566-7.
- Friedl, Jeffrey (). Mastering Regular Expressions. O'Reilly(d). ISBN 0-596-00289-0.
- Gelade, Wouter; Neven, Frank (). Succinctness of the Complement and Intersection of Regular Expressions. Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008). pp. 325–336.
- Goyvaerts, Jan; Levithan, Steven (). Regular Expressions Cookbook. [O'reilly]. ISBN 978-0-596-52068-7.
- Gruber, Hermann; Holzer, Markus (). Finite Automata, Digraph Connectivity, and Regular Expression Size (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). 5126. pp. 39–50. doi:10.1007/978-3-540-70583-3_4.
- Habibi, Mehran (). Real World Regular Expressions with Java 1.4. Springer. ISBN 1-59059-107-0.
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (). Introduction to Automata Theory, Languages, and Computation (ed. 2nd). Addison-Wesley.
- Johnson, W. L.; Porter, J. H.; Ackley, S. I.; Ross, D. T. (). „Automatic generation of efficient lexical processors using finite state techniques”. Communications of the ACM. 11 (12): 805–813. doi:10.1145/364175.364185.
- Kleene, Stephen C. (). Shannon, Claude E.; McCarthy, John, ed. Representation of Events in Nerve Nets and Finite Automata. Automata Studies. Princeton University Press. pp. 3–42.
- Kozen, Dexter (). „A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events”. Proceedings of the 6th Annual IEEE Symposium on Logic in Computer Science (LICS 1991): 214–225.
- Laurikari, Ville (). „TRE library 0.7.6”.
- Liger, Francois; Craig McQueen; Paul Wilton (). Visual Basic .NET Text Manipulation Handbook. Wrox Press(d). ISBN 1-86100-730-2.
- Sipser, Michael (). „Chapter 1: Regular Languages”. Introduction to the Theory of Computation. PWS Publishing. pp. 31–90. ISBN 0-534-94728-X.
- Stubblebine, Tony (). Regular Expression Pocket Reference. O'Reilly. ISBN 0-596-00415-X.
- Thompson, K. (). „Programming Techniques: Regular expression search algorithm”. Communications of the ACM. 11 (6): 419–422. doi:10.1145/363347.363387.
- Wall, Larry (). „Apocalypse 5: Pattern Matching”. Arhivat din original la . Accesat în .