Expresie uzuala

O expresie regulată (în limba engleză expresie regulată sau, sub formă prescurtată, regexp, regex sau RE) este o secvență de simboluri (deci un șir de caractere ) care identifică un set de șiruri. Ele pot defini toate și numai limbile obișnuite . Teorema lui Kleene afirmă că clasa de limbi regulate corespunde clasei de limbi generate de tip 3 gramatici (în ierarhia Chomsky ) și recunoscute de automate de stare finită . Cu toate acestea, în practică , există anumite constructe (de exemplu backreference constructelor) ^[1] , care permit să se extindă setul de limbi definibile. Diferite programe sprijină notatii diferite pentru a exprima aceleași expresii regulate, astfel încât nu există nici un „universal“ sintaxă .

Istorie

Deși fuseseră formalizate deja în anii 1940 , expresiile regulate au intrat în lumea computerelor pentru prima dată la sfârșitul anilor 1960 , în mediul Unix : primul editor de text care a implementat funcții care le-au permis utilizarea a fost o versiune a QED scrisă de Ken Thompson , unul dintre pionierii Unix. Editorul, de la ei interfață linie de comandă , pus la dispoziție o comandă de imprimare numit la nivel mondial expresie regulată, care ulterior a fost făcută o cerere independentă, grep .

Expresiile regulate nu au avut o mare difuzie și utilizarea până în anii optzeci , când Perl limbajul de programare a fost inventat , care a permis utilizarea de nativ expresii regulate. Versatilitatea limbii, de asemenea , datorită faptului de a fi un limbaj interpretat , a permis utilizarea acestuia în diferite situații și au favorizat dezvoltarea formalismului Perl pentru expresii regulate, care a devenit un standard de facto . Utilizarea pe scară largă a acestor instrumente a determinat dezvoltatorii să pună în aplicare expresii regulate în alte limbi , precum și, prin intermediul bibliotecilor , cum ar fi PCRE sau chiar ca o parte din bibliotecile standard ale unor limbi, cum ar fi Java și TCL .

Descriere

O expresie regulată definește o funcție care are un șir de caractere ca intrare și returnează o valoare de tip da / nu, în funcție de faptul dacă șirul urmează un anumit tipar sau nu.

De exemplu, toate adresele de e-mail trebuie să se facă după cum urmează: începe cu o secvență de caractere alfanumerice, urmat de la semn, urmat de alte caractere alfanumerice, urmat de o perioadă, urmat de două sau trei litere. ^[2] Această regulă informală ar deveni regexp în cazul în care au fost codificate în conformitate cu o sintaxă foarte precis recunoscut de un program capabil de interpretare siruri de caractere.

Expresiile regulate în limbile oficiale

Expresiile regulate sunt compuse din constante și operatori care denotă seturi de șiruri și operații între aceste seturi.

Dat fiind un alfabet finit $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ , sunt definite următoarele constante:

$\varnothing$ ${\ displaystyle \ varnothing}$ $\ varnothing$ sau $\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$ ( Set gol )
$\epsilon$ ${\ displaystyle \ epsilon}$ $\ epsilon$ (string gol, adică șir de lungime 0)
$\left\{a\right\}$ ${\ displaystyle \ left \ {a \ right \}}$ $\ left \ {a \ right \}$ (caracter, $\forall a\in \Sigma$ ${\ displaystyle \ forall a \ in \ Sigma}$ $\ forall a \ in \ Sigma$ )

și următoarele operațiuni:

concatenare: RS o $R\circ S$ ${\ displaystyle R \ circ S}$ $R \ circ S$ indică întregul $\left\{\alpha \beta |\alpha \in R\land \beta \in S\right\}$ ${\ displaystyle \ left \ {\ alpha \ beta | \ alpha \ în R \ land \ beta \ în S \ right \}}$ ${\ displaystyle \ left \ {\ alpha \ beta | \ alpha \ în R \ land \ beta \ în S \ right \}}$
Uniune: $R\cup S$ ${\ displaystyle R \ cup S}$ $R \ cup S$ indică unirea dintre cele două seturi
Kleene stele : $R^{*}$ ${\ displaystyle R ^ {*}}$ $R ^ {{*}}$ indică setul care conține toate posibilele iterații care pot fi obținute din elementele R.
intersecție: $R\cap S$ ${\ displaystyle R \ cap S}$ $R \ cap S$ indică intersecția dintre cele două seturi de șiruri
completează: complementaritatea R indică setul de siruri de caractere care aparțin $\Sigma ^{*}\setminus R$ ${\ displaystyle \ Sigma ^ {*} \ setminus R}$ $\ Sigma ^ {{*}} \ setminus R$

De exemplu date $R=\left\{a,b\right\}$ ${\ displaystyle R = \ left \ {a, b \ right \}}$ $R = \ left \ {a, b \ right \}$ Și $S=\left\{7,8\right\}$ ${\ displaystyle S = \ left \ {7,8 \ right \}}$ $S = \ left \ {7,8 \ right \}$ , $RS=\left\{a7,b7,a8,b8\right\}$ ${\ displaystyle RS = \ left \ {a7, b7, a8, b8 \ right \}}$ $RS = \ left \ {a7, b7, a8, b8 \ right \}$ Și $S^{*}=\left\{\epsilon ,7,8,77,78,87,88,777,778,\cdots \right\}$ ${\ displaystyle S ^ {*} = \ left \ {\ epsilon, 7,8,77,78,87,88,777,778, \ cdots \ right \}}$ $S ^ {{*}} = \ left \ {\ epsilon, 7,8,77,78,87,88,777,778, \ cdots \ right \}$

Deci, putem spune că o expresie regulată, definită pornind de la un alfabet $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ și un set de simboluri $\left\{+,*,(,),.,\emptyset \right\}$ ${\ displaystyle \ left \ {+, *, (,),., \ emptyset \ right \}}$ $\ left \ {+, *, (,),., \ emptyset \ right \}$ , este un șir $R\in {\left(\Sigma \cup \left\{+,*,(,),.,\emptyset \right\}\right)}^{+}$ ${\ displaystyle R \ in {\ left (\ Sigma \ cup \ left \ {+, *, (,),., \ emptyset \ right \} \ right)} ^ {+}}$ $R \ in {\ left (\ Sigma \ cup \ left \ {+, *, (,),., \ Emptyset \ right \} \ right)} ^ {{+}}$ ceea ce face ca oricare dintre următoarele să fie adevărate:

$R=\emptyset$ ${\ displaystyle R = \ emptyset}$ $R = \ emptyset$
$R\in \Sigma$ ${\ displaystyle R \ in \ Sigma}$ $R \ in \ Sigma$
$R=S+T$ ${\ displaystyle R = S + T}$ $R = S + T$ sau $R=ST$ ${\ displaystyle R = ST}$ $R = ST$ sau $R=S^{*}$ ${\ displaystyle R = S ^ {*}}$ $R = S ^ {{*}}$ , unde S și T sunt expresii regulate pe alfabet $\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$

Utilizarea expresiilor regulate

Expresiile regulate sunt utilizate în principal de către editori de text pentru găsirea și înlocuirea porțiuni de text. Ele sunt , de asemenea , de o mare importanță în informatică teoretică, în care, de exemplu, acestea sunt folosite pentru a reprezenta toate căile posibile pe un grafic . Cu toate acestea, expresiile regulate sunt potrivite pentru a reprezenta un set foarte restrâns de limbaje formale (dacă am dori să reprezentăm expresii aritmetice sau limbaje de programare, ar trebui deja să folosim limbaje de tip 2): utilizarea limbajelor regulate este încă convenabilă , ca închiderea lor către operațiile de unire, intersecție și complementare, permit construirea unei algebre booleene și o bună capacitate de luare a deciziilor.

Sintaxă

Expresii regulate UNIX tradiționale

Sintaxa expresiilor regulate în UNIX conform POSIX standardului există în două versiuni diferite:

sintaxa numita bază, este cel care a fost creat pentru prima dată și este cea mai răspândită, un exemplu al unei aplicații care folosește este ed ;
sintaxa numita noua, care este cel care a fost definit cu standardul POSIX.2, este utilizat , de exemplu , prin egrep .

Când a fost propus noua versiune a sintaxei de expresie regulată, sa decis să facă vechea versiune învechită, doar de acum difuzarea versiunii vechi a fost de așa natură încât schimbarea nu a fost profitabilă ^[3] . Cele mai multe programe care utilizează regexps, cum ar fi grep și sed , folosesc aceste reguli de bază oferind în același timp sprijin pentru noile norme extinse. În această sintaxă, majoritatea personajelor sunt văzute ca literal și se găsesc doar pe ele însele. De exemplu: „a” găsește „a”; "bc)" găsește "bc)"; etc. Excepțiile de la această regulă sunt metacaractere :

.	Găsiți un singur caracter (dacă acesta este în modul linie unică în caz contrar , dacă acesta este în multilinie este nevoie de toate celelalte decât \ n, adică un cărucior de întoarcere de caractere).
[]	Găsiți un singur caracter cuprins între paranteze. De exemplu, [abc] chibrituri fie un "a", "b" sau "c". [az] este un interval și se potrivește cu fiecare literă mică a alfabetului. Pot exista cazuri mixte: [abcq-z] găsește a, b, c, q, r, s, t, u, v, w, x, y, z, exact ca [a-cq-z]. Caracterul '-' este literal doar dacă este primul sau ultimul caracter din paranteze: [abc-] sau [-abc]. Pentru a găsi un caracter '[' sau ']', cel mai simplu mod este să le puneți mai întâi în paranteze: [] [ab] se potrivește cu ']', '[', 'a' sau 'b'.
[^]	Găsiți orice caracter care nu este inclus în paranteză. De exemplu, [^ abc] se potrivește cu orice alt caracter decât "a", "b" sau "c". [^ az] găsește orice alt caracter decât o literă mică. Ca mai sus, aceste două metode pot fi utilizate împreună.
^	Se potrivește la începutul șirului (sau fiecare linie a șirului, atunci când este utilizat în modul multilinie)
$	Se potrivește la sfârșitul șirului sau la poziția imediat precedentă unui caracter nou de linie (sau la sfârșitul fiecărei linii a șirului, atunci când este utilizat în modul multilinie)
()	Definește o „subexpresie marcată”. Rezultatul a ceea ce este inclus în expresie poate fi amintit mai târziu. A se vedea mai jos, \ n.
\ n	În cazul în care n este o cifră la 1 la 9; este ceea ce n - lea subexpression potrivire. Acest construct, numit backreference, extinde potențialul regexps dincolo de limbi regulate și nu a fost adoptată în sintaxa extinsă a regexps.
*	O expresie constând dintr-un singur caracter urmat de „” găsește zero sau mai multe copii ale expresiei respective. De exemplu, "[xyz] " găsește "", "x", "y", "zx", "zyx" și așa mai departe. \ N , unde n este o cifră de la 1 la 9, se potrivește cu zero sau mai multe iterații ceea ce n - lea subexpression MATCHED. De exemplu, „(a.) C \ 1 ” se potrivește cu „abcab” și „accac”, dar nu cu „abcac”. O expresie inclusă în „\ (” și „\)” urmată de „” nu este validă. În unele cazuri (de exemplu / usr / bin / xpg4 / grep din SunOS 5.8), găsește zero sau mai multe repetări ale șirului pe care le-a găsit expresia inclusă. În alte cazuri (de exemplu / usr / bin / grep din SunOS 5.8), găsește ceea ce a găsit expresia inclusă, urmată de un „” literal.
{X, y}	Găsiți ultimul „bloc“ , cel puțin x ori și nu mai mult de ori y. De exemplu, „a {3,5}” se potrivește cu „aaa”, „aaaa” sau „aaaaa”.

Versiunile mai vechi de grep nu acceptă alternativ „|“ separator.

Exemple:

„.atto“ se potrivește cu orice șir de cinci caractere , cum ar fi pisica, nebun, sau pact

„[GM] fapta“ își găsește și pisica nebun

„[^ P] fapta“ găsește toate combinațiile expresiei „.act“ cu excepția legământului

„^ [GM] fapta“ găsește pisică și prost , dar numai la începutul unei linii

„[GM] acționează $“ găsește pisică și se împerechează , dar numai la sfârșitul unei linii

Deoarece multe seturi de caractere variază în funcție de configurația locală (în unele cazuri literele sunt organizate în abc..xyzABC ... XYZ, în altele aAbB..yYzZ), standardul POSIX a definit unele clase sau categorii de caractere așa cum se arată în următorul tabel:

Clasa POSIX	sintaxa normală	sens
[: upper:]	[AZ]	majuscule
[: inferior:]	[az]	litere mici
[: alfa:]	[A-Za-z]	atât majuscule, cât și minuscule
[: alnum:]	[A-Za-z0-9]	litere majuscule și minuscule și cifre
[: cifră:]	[0-9]	numere
[: xdigit:]	[0-9A-Fa-f]	numere în format hexazecimal
[: punct:]	[! \ - "# $% & '() * +,. \ /:; <=>? @ [\] \ ^ _` {\|} ~ \\]	semne de punctuatie
[: gol:]	[\ t]	spațiu sau TAB
[: space:]	[\ t \ n \ r \ f \ v]	caractere goale
[: cntrl:]	[\ x00- \ x1F \ x7F]	controlul personajelor
[: grafic:]	[^ \ t \ n \ r \ f \ v]	caractere necompletate
[: imprimare:]	[^ \ t \ n \ r \ f \ v]	caractere și spații care nu sunt goale

Parantezele pătrate fac parte din sintaxa pentru indicarea clasei de caractere. De exemplu [[: upper:] [: digit:] ab] se potrivește cu orice literă majusculă, orice cifră, litere mici „a” și litere mici „b”.

Exemple de cuantificatori

* Caută apariția (zero sau mai multe ori) din următoarele caractere sau set de caractere:

abc* identificã ab urmat de zero sau mai multe c

ca în ab , abc , abcc , abccc

+ Căutare pentru apariția (una sau mai multe ori) din următoarele caractere sau set de caractere:

ab[ce]+ identifică ab urmat de una sau mai multe c sau una sau mai multe e

ca în abc , abec , abccc , abcceeecccccce

? Caută apariția (zero sau o dată) a următorului caracter sau set de caractere:

abc? identifică ab urmată sau nu de un c

ca în abc și ab

{m, n} Găsiți apariția (de ori om; m lăsat gol este zero, n gol stânga este infinit) a caracterului, setul de caractere sau sub- regex care urmează:

(ab){1,2} identifică secvențele de una sau două ab

ca în ab și abab

Notă

^ Backreference constructe în expresii regulate , pe technet.microsoft.com, Microsoft . Adus pe 9 septembrie 2014 .
^ De fapt , regula ar trebui să fie rafinat pentru a sprijini simbolurile non-alfanumerice care apar înainte și după , la semn, dar le neglija în acest exemplu simplu.
^ Regex - POSIX.2 expresii regulate , pe cl.cam.ac.uk. Adus la 17 ianuarie 2014 .

Bibliografie

(RO) Expresia regulată , în Enciclopedia de Informatica, Hoboken, Wiley, 2003.

Elemente conexe

Alte proiecte

Wikimanuale conține un manual privind expresii regulate
Wikiversitate conține o lecție despre limbi și expresii regulate
Wikimedia Commons conține imagini sau alte fișiere pe expresii regulate

linkuri externe

(RO) Expresia regulată , pe fon.hum.uva.nl.
Wikipedia manual pe expresii regulate

Controlul autorității	LCCN (RO) sh2018002310 · GND (DE) 4506116-6 · BNF (FR) cb14626171d (data) · NDL (RO, JA) 01121341

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] Backreference constructe în expresii regulate , pe technet.microsoft.com, Microsoft . Adus pe 9 septembrie 2014 .

[2] De fapt , regula ar trebui să fie rafinat pentru a sprijini simbolurile non-alfanumerice care apar înainte și după , la semn, dar le neglija în acest exemplu simplu.

[3] Regex - POSIX.2 expresii regulate , pe cl.cam.ac.uk. Adus la 17 ianuarie 2014 .

[1]

[2]

[3]