Expresie uzuala
Această intrare sau secțiune despre subiectul teoriilor informatice nu citează sursele necesare sau cei prezenți sunt insuficienți . |
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:
și următoarele operațiuni:
- concatenare: RS o indică întregul
- Uniune: indică unirea celor două mulțimi
- Steaua Kleene : indică setul care conține toate iterațiile posibile obținute din elementele lui R.
- intersecție: indică intersecția dintre cele două seturi de șiruri
- 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:
- 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. |
* |
|
{ 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 multc
- 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 multec
sau unul sau mai multee
- 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 unc
- ca în
abc
șiab
-
{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
șiabab
Notă
- ^ Backreference construiește în expresii regulate , pe technet.microsoft.com , Microsoft . Adus pe 9 septembrie 2014 .
- ^ 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.
- ^ regex - expresii regulate POSIX.2 , pe cl.cam.ac.uk. Adus la 17 ianuarie 2014 .
Bibliografie
- (EN) Expresie regulată , în Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
Elemente conexe
Alte proiecte
- Wikibooks conține un manual privind expresiile regulate
- Wikiversitatea conține o lecție despre limbi și expresii regulate
- Wikimedia Commons conține imagini sau alte fișiere cu expresii regulate
linkuri externe
- ( RO ) Expresie regulată , pe fon.hum.uva.nl.
- Manual Wikipedia despre expresii regulate
Controlul autorității | LCCN (EN) sh2018002310 · GND (DE) 4506116-6 · BNF (FR) cb14626171d (data) · NDL (EN, JA) 01.121.341 |
---|