Expresie uzuala

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

O expresie regulată (în engleză regular expression sau, în formă prescurtată, regexp , regex sau RE ) este o secvență de simboluri (deci un șir ) care identifică un set de șiruri. Ele pot defini toate și numai limbile obișnuite . Teorema lui Kleene afirmă că clasa limbajelor regulate corespunde clasei de limbaje generate de gramaticile de tip 3 (în ierarhia Chomsky ) și recunoscută de automatele de stare finită . Cu toate acestea, în practică există anumite construcții (de exemplu constructele de referință inversă ) [1] care permit extinderea setului de limbaje definibile. Diferite programe acceptă notații diferite pentru exprimarea acelorași expresii regulate, deci nu există o sintaxă „universală”.

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, din interfața sa de linie de comandă , a pus la dispoziție o comandă numită global regular expression print , care ulterior a devenit o aplicație independentă, grep .

Expresiile regulate nu au avut o mare difuzie și utilizare până în anii optzeci , când a fost inventat limbajul de programare Perl care a permis în mod nativ utilizarea expresiilor regulate. Versatilitatea limbajului, datorită și faptului că este un limbaj interpretat , a permis utilizarea acestuia în diverse situații și a favorizat dezvoltarea formalismului Perl pentru expresii regulate, care au devenit un standard de facto . Utilizarea pe scară largă a acestor instrumente i-a determinat pe dezvoltatori să implementeze expresii regulate și în alte limbi, prin intermediul bibliotecilor precum PCRE sau chiar ca parte a bibliotecilor standard ale unor limbi, cum ar fi Java și tcl .

Descriere

O expresie regulată definește o funcție care ia un șir ca intrare și returnează o valoare de tipul da / nu, în funcție de faptul că șirul urmează un anumit model sau nu.

De exemplu, toate adresele de e-mail trebuie să fie alcătuite după cum urmează: începeți cu o succesiune de caractere alfanumerice, urmată de semnul la, urmată de alte caractere alfanumerice, urmată de un punct, urmat de două sau trei litere . [2] Această regulă informală ar deveni regex dacă ar fi codificată după o sintaxă foarte precisă recunoscută de un program capabil să analizeze șirurile.

Expresii regulate în limbaje formale

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

Dat fiind un alfabet finit , sunt definite următoarele constante:

  1. sau ( set gol )
  2. (șir gol, adică șir de lungime 0)
  3. (caracter, )

și următoarele operațiuni:

  1. concatenare: RS o indică întregul
  2. Uniune: indică unirea celor două mulțimi
  3. Steaua Kleene : indică setul care conține toate iterațiile posibile obținute din elementele lui R.
  4. intersecție: indică intersecția dintre cele două seturi de șiruri
  5. complement: complementarul lui R indică setul de șiruri aparținând

De exemplu date Și , Și

Deci, putem spune că o expresie regulată, definită pornind de la un alfabet și un set de simboluri , este un șir ceea ce face ca oricare dintre următoarele să fie adevărate:

  1. sau sau , unde S și T sunt expresii regulate pe alfabet

Utilizarea expresiilor regulate

Expresiile regulate sunt utilizate în principal de editorii de text pentru găsirea și înlocuirea unor porțiuni de text. Ele au, de asemenea, o mare importanță în informatica teoretică, în care, de exemplu, sunt utilizate 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 acestora 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 standardului POSIX există în două versiuni diferite:

  • sintaxa numită de bază , este cea care a fost creată mai întâi și este cea mai răspândită, un exemplu de aplicație care o folosește este ed ;
  • sintaxa numită nouă , adică cea care a fost definită cu standardul POSIX.2, este folosită de exemplu de egrep .

Când a fost propusă noua versiune a sintaxei expresiei obișnuite, s-a decis ca vechea versiune să devină învechită, doar că difuzarea vechii versiuni a fost de așa natură încât schimbarea nu a fost profitabilă [3] . Majoritatea programelor care utilizează regexps, cum ar fi grep și sed , utilizează aceste reguli de bază, oferind în același timp suport pentru noile reguli 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ă este în modul cu o singură linie , altfel, dacă este în linie multiplă, va lua toate caracterele, altele decât \ n, adică o întoarcere a carului ).
[] 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. Vedeți mai jos, \ n .
\ n Unde n este o cifră de la 1 la 9; este ceea ce se potrivea subexpresia a n- a. Această construcție, numită backreference , extinde potențialul regexps dincolo de limbaje obișnuite ș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 din ceea ce se potrivește cu a n- a subexpresie. 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” de cel puțin x ori și nu mai mult de y ori. De exemplu, „a {3,5}” se potrivește cu „aaa”, „aaaa” sau „aaaaa”.

Versiunile mai vechi ale grep nu acceptă separatorul alternativ "|".

Exemple:

„.atto” se potrivește cu orice șir de cinci caractere, cum ar fi pisică , nebun sau pact
„Fapta [gm]” găsește pisica și nebunul
„[^ p] fapta” găsește toate combinațiile expresiei „.act”, cu excepția legământului
„^ [gm] fapta” găsește pisica și prostul, dar numai la începutul unei rânduri
„[gm] act $” găsește pisica și perechea, dar numai la sfârșitul liniei

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

  • * Căutați apariția (zero sau de mai multe ori) a următorului caracter sau set de caractere:
abc* identifică ab urmat de zero sau mai mult c
ca în ab , abc , abcc , abccc
  • + Căutați apariția (de una sau mai multe ori) a următorului caracter sau set de caractere:
ab[ce]+ identifică ab urmat de unul sau mai multe c sau unul 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 (din timpurile omului; m stânga necompletată este zero, n stânga necompletată este infinită) a caracterului, setului de caractere sau subregexului care urmează:
(ab){1,2} identifică secvențele unuia sau a două ab
ca în ab și abab

Notă

  1. ^ Backreference construiește în expresii regulate , pe technet.microsoft.com , Microsoft . Adus pe 9 septembrie 2014 .
  2. ^ De fapt regula ar trebui rafinată pentru a susține simbolurile nealfanumerice care apar înainte și după semnul at, dar le neglijăm în acest exemplu simplu.
  3. ^ regex - expresii regulate POSIX.2 , pe cl.cam.ac.uk. Adus la 17 ianuarie 2014 .

Bibliografie

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității LCCN (EN) sh2018002310 · GND (DE) 4506116-6 · BNF (FR) cb14626171d (data) · NDL (EN, JA) 01.121.341
Informatică Portal IT : accesați intrările Wikipedia care se ocupă cu IT