Expressió normal

De la Viquipèdia, l'enciclopèdia lliure.
Saltar a la navegació Saltar a la cerca

Una expressió regular (en anglès regular expression o, de forma abreujada, regexp , regex o RE ) és una seqüència de símbols (per tant, una cadena ) que identifica un conjunt de cadenes. Poden definir tots i només els idiomes normals . El teorema de Kleene afirma que la classe de llengües regulars correspon a la classe de llengües generades per gramàtiques de tipus 3 (a la jerarquia de Chomsky ) i reconegudes per autòmats d'estats finits . Tanmateix, a la pràctica hi ha certes construccions (per exemple, les construccions de referència ) [1] que permeten ampliar el conjunt de llenguatges definibles. Diferents programes admeten notacions diferents per expressar les mateixes expressions regulars, de manera que no hi ha una sintaxi "universal".

Història

Tot i que ja s’havien formalitzat als anys quaranta , les expressions regulars van entrar al món de la informàtica per primera vegada a finals dels anys seixanta , a l’entorn Unix : el primer editor de text que va implementar funcions que en permetien l’ús va ser una versió de QED escrita per Ken Thompson , un dels pioners d'Unix. L'editor, des de la seva interfície de línia d'ordres , va fer disponible una ordre anomenada impressió d'expressió regular global , que posteriorment es va convertir en una aplicació independent, grep .

Les expressions regulars no van tenir una gran difusió i ús fins als anys vuitanta , quan es va inventar el llenguatge de programació Perl que permetia de forma nativa l’ús d’expressions regulars. La versatilitat de la llengua, també pel fet de ser una llengua interpretada , va permetre el seu ús en diverses situacions i va afavorir el desenvolupament del formalisme de Perl per a expressions regulars, que es va convertir en un estàndard de facto . L’ús generalitzat d’aquestes eines va motivar els desenvolupadors a implementar expressions regulars també en altres idiomes, mitjançant biblioteques com PCRE o fins i tot com a part de les biblioteques estàndard d’alguns idiomes, com Java i tcl .

Descripció

Una expressió regular defineix una funció que pren una cadena com a entrada i retorna un valor del tipus sí / no, depenent de si la cadena segueix un patró determinat o no.

Per exemple, totes les adreces de correu electrònic s’han de compondre de la manera següent: comenceu amb una seqüència de caràcters alfanumèrics, seguida del signe at, seguida d’altres caràcters alfanumèrics, seguida d’un punt, seguit de dues o tres lletres . [2] Aquesta regla informal es convertiria en una expressió regular si es codifica d'acord amb una sintaxi molt precís reconegut per un programa capaç d'analitzar cadenes.

Expressions regulars en llenguatges formals

Les expressions regulars es componen de constants i operadors que denoten conjunts de cadenes i d’operacions entre aquests conjunts.

Donat un alfabet finit , es defineixen les constants següents:

  1. o bé ( conjunt buit )
  2. (cadena buida, és a dir, cadena de longitud 0)
  3. (personatge, )

i les operacions següents:

  1. concatenació: RS o indica el conjunt
  2. Unió: indica la unió dels dos conjunts
  3. Estrella de Kleene : indica el conjunt que conté totes les possibles iteracions que es poden obtenir dels elements de R.
  4. intersecció: indica la intersecció entre els dos conjunts de cordes
  5. complement: el complementari de R indica el conjunt de cordes pertanyents a

Per exemple, dades I , I

Per tant, podem dir que una expressió regular, definida a partir d’un alfabet i un conjunt de símbols , és una cadena cosa que fa que sigui cert qualsevol dels següents:

  1. o bé o bé , on S i T són expressions regulars de l'alfabet

Ús d’expressions regulars

Els editors de text utilitzen principalment expressions regulars per trobar i substituir porcions de text. També tenen una gran importància en informàtica teòrica, en què, per exemple, s’utilitzen per representar tots els camins possibles en un gràfic . Tanmateix, les expressions regulars són adequades per representar un conjunt de llenguatges formals molt restringit (si volguéssim representar expressions aritmètiques o llenguatges de programació, ja hauríem d’utilitzar llenguatges de tipus 2): l’ús de llenguatges regulars encara és convenient , com a tancament a les operacions d'unió, intersecció i complementació, permeten la construcció d'una àlgebra booleana i una bona capacitat de decisió.

Sintaxi

Expressions regulars UNIX tradicionals

La sintaxi de les expressions regulars a UNIX segons l'estàndard POSIX existeix en dues versions diferents:

  • la sintaxi anomenada bàsica , és la que es va crear primer i és la més estesa, un exemple d’aplicació que l’utilitza és ed ;
  • la sintaxi anomenada nova , que és la que s'ha definit amb l'estàndard POSIX.2, és utilitzada per exemple per egrep .

Quan es va proposar la nova versió de la sintaxi de les expressions regulars, es va decidir deixar obsoleta la versió antiga, només ara la difusió de la versió antiga era tal que el canvi no era rendible [3] . La majoria de programes que fan servir l’expressió regular, com grep i sed , utilitzen aquestes regles bàsiques mentre proporcionen suport per a les noves regles ampliades. En aquesta sintaxi, la majoria dels personatges es veuen com a literals i només es troben a si mateixos. Per exemple: "a" troba "a"; "bc)" troba "bc)"; etc. Les excepcions a aquesta regla són metacaràcters :

. Cerqueu un sol caràcter (si està en mode de línia única , en cas contrari, si és en una línia múltiple, tindrà tots els caràcters diferents de \ n, és a dir, un retorn de carro ).
[] Cerqueu un sol caràcter contingut entre parèntesis. Per exemple, [ABC] partits ja sigui una "a", "b", o "c". [az] és un interval que coincideix amb totes les lletres minúscules de l'alfabet. Hi pot haver casos mixtos: [abcq-z] troba a, b, c, q, r, s, t, u, v, w, x, y, z, exactament com [a-cq-z].

El caràcter '-' és literal només si és el primer o l'últim caràcter entre claudàtors: [abc-] o [-abc]. Per trobar un caràcter '[' o ']', la manera més senzilla és posar-los primer entre claudàtors: [] [ab] coincideix amb ']', '[', 'a' o 'b'.

[^] Cerqueu qualsevol caràcter que no estigui inclòs entre parèntesis. Per exemple, [^ abc] coincideix amb qualsevol caràcter que no sigui "a", "b" o "c". [^ az] troba qualsevol caràcter que no sigui una lletra minúscula. Com es va esmentar anteriorment, aquests dos mètodes es poden utilitzar conjuntament.
^ Coincideix al començament de la cadena (o cada línia de la cadena, quan s’utilitza en mode multilínia)
$ Coincideix amb el final de la cadena o la posició que precedeix immediatament un caràcter de línia nova (o el final de cada línia de la cadena, quan s’utilitza en mode multilínia)
() Defineix una "subexpressió marcada". El resultat del que s’inclou a l’expressió es pot recordar més endavant. Vegeu a continuació, \ n .
\ n On n és un dígit de l'1 al 9; és el que el n-èsim subexpressió igualada. Aquesta construcció, anomenada backreference , amplia el potencial de les expressions regulars més enllà dels llenguatges normals i no s’ha adoptat en la sintaxi ampliada de les expressions regulars.
*
  • Una expressió que consta d'un sol caràcter seguit de "*" troba zero o més còpies d'aquesta expressió. Per exemple, "[xyz] *" troba "", "x", "y", "zx", "zyx", etc.
  • \ N *, on n és un dígit d'1 a 9, coincideix amb zero o més iteracions del que el n-èsim subexpressió igualada. Per exemple, "(a.) C \ 1 *" coincideix amb "abcab" i "accac" però no amb "abcac".
  • Una expressió inclosa a "\ (" i "\)" seguida de "*" no és vàlida. En alguns casos (per exemple, / usr / bin / xpg4 / grep de SunOS 5.8), troba zero o més repeticions de la cadena que ha trobat l'expressió inclosa. En altres casos (per exemple, / usr / bin / grep de SunOS 5.8), troba el que ha trobat l'expressió adjunta, seguit d'un literal "*".
{ x , y } Cerqueu l'últim "bloc" com a mínim x vegades i no més que y vegades. Per exemple, "a {3,5}" coincideix amb "aaa", "aaaa" o "aaaaa".

Les versions anteriors de grep no admeten el separador "|" alternatiu.

Exemples:

".atto" coincideix amb qualsevol cadena de cinc caràcters com ara gat , boig o pacte
"[gm] gesta" troba gat i boig
"[^ p] deed" troba totes les combinacions de l'expressió ".act" excepte el pacte
"^ [gm] deed" troba gat i ximple, però només al principi d'una línia
"[gm] act $" troba gat i parella però només al final d'una línia

Com que molts conjunts de caràcters varien segons la configuració local (en alguns casos les lletres s’organitzen en abc..xyzABC ... XYZ, en altres aAbB..yYzZ), l’estàndard POSIX ha definit algunes classes o categories de caràcters tal com es mostra a la taula següent:

Classe POSIX sintaxi normal significat
[: superior:] [AZ] majúscules
[: més baix:] [az] lletres minúscules
[: alfa:] [A-Za-z] tant en majúscules com en minúscules
[: alnum:] [A-Za-z0-9] majúscules i minúscules i números
[: dígit:] [0-9] números
[: xdigit:] [0-9A-Fa-f] nombres en format hexadecimal
[: punct:] [! \ - "# $% & '() * +,. \ /:; <=>? @ [\] \ ^ _` {|} ~ \\] signes de puntuació
[: en blanc:] [\ t] espai o TAB
[: espai:] [\ t \ n \ r \ f \ v] caràcters buits
[: cntrl:] [\ x00- \ x1F \ x7F] control de personatges
[: gràfic:] [^ \ t \ n \ r \ f \ v] caràcters no en blanc
[: imprimir:] [^ \ t \ n \ r \ f \ v] caràcters i espais no en blanc

Els claudàtors formen part de la sintaxi per indicar la classe de caràcters. Per exemple, [[: upper:] [: digit:] ab] coincideix amb qualsevol lletra majúscula, qualsevol dígit, minúscula 'a' i minúscula 'b'.

Exemples de quantificadors

  • * Cerqueu l'ocurrència (zero o més vegades) del següent caràcter o conjunt de caràcters:
abc* identifica ab seguit de zero o més c
com a ab , abc , abcc , abccc
  • + Cerqueu l'ocurrència (una o més vegades) del caràcter o conjunt de caràcters següents:
ab[ce]+ identifica ab seguit d'una o més c o d'una o més e
com a abc , abec , abccc , abcceeecccccce
  • ? Cerca l'ocurrència (zero o una vegada) del caràcter o conjunt de caràcters següents:
abc? identifica ab seguit o no de c
com en abc i ab
  • {m, n} Trobeu l'ocurrència (des de l'home, m l'esquerra en blanc és zero, n l'esquerra en blanc és infinita) del caràcter, el conjunt de caràcters o la subregió que segueix:
(ab){1,2} identifica les seqüències d'un o dos ab
com en ab i abab

Nota

  1. ^ Construccions de referències posteriors en expressions regulars , a technet.microsoft.com , Microsoft . Consultat el 9 de setembre de 2014 .
  2. ^ En realitat, la regla s'hauria de refinar per donar suport als símbols no alfanumèrics que apareixen abans i després del signe at, però els descuidem en aquest senzill exemple.
  3. ^ regex - expressions regulars POSIX.2 , a cl.cam.ac.uk. Consultat el 17 de gener de 2014 .

Bibliografia

Articles relacionats

Altres projectes

Enllaços externs

Control de l'autoritat LCCN (EN) sh2018002310 · GND (DE) 4506116-6 · BNF (FR) cb14626171d (data) · NDL (EN, JA) 01.121.341
Informàtica Portal de TI : accediu a les entrades de Viquipèdia relacionades amb TI