Espressione regolare

Questa voce o sezione sull'argomento teorie dell'informatica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

Un'espressione regolare (in inglese regular expression o, in forma abbreviata, regexp, regex o RE) è una sequenza di simboli (quindi una stringa) che identifica un insieme di stringhe. Possono definire tutti e soli i linguaggi regolari. Il teorema di Kleene afferma che la classe dei linguaggi regolari corrisponde alla classe dei linguaggi generati da grammatiche di tipo 3 (nella gerarchia di Chomsky) e riconosciuti da automi a stati finiti. Tuttavia, nella pratica esistono taluni costrutti (ad esempio i costrutti di backreference)^[1] che permettono di ampliare l'insieme di linguaggi definibili. Programmi diversi supportano notazioni diverse per esprimere le stesse espressioni regolari, pertanto non esiste una sintassi "universale".

Sebbene fossero state formalizzate già fin dagli anni quaranta, le espressioni regolari entrarono nel mondo informatico per la prima volta alla fine degli anni sessanta, in ambiente Unix: il primo editor di testo che implementava funzioni che ne permettessero l'uso fu una versione di QED scritta da Ken Thompson, uno dei pionieri di Unix. L'editor, dalla sua interfaccia a riga di comando, metteva a disposizione un comando chiamato global regular expression print, che successivamente fu reso un applicativo indipendente, grep.

Le espressioni regolari non ebbero grande diffusione ed utilizzo fino agli anni ottanta, quando fu inventato il linguaggio di programmazione Perl che permetteva nativamente l'uso di espressioni regolari. La versatilità del linguaggio, dovuta anche al fatto d'essere un linguaggio interpretato, ne permise l'utilizzo in svariate situazioni e favorì lo sviluppo del formalismo di Perl per le espressioni regolari, che diventò uno standard de facto. La grandissima diffusione di questi strumenti spinse gli sviluppatori a implementare le espressioni regolari anche in altri linguaggi, a mezzo di librerie come PCRE o persino come parte delle librerie standard di alcuni linguaggi, come Java e tcl.

Un'espressione regolare definisce una funzione che prende in ingresso una stringa, e restituisce in uscita un valore del tipo sì/no, a seconda che la stringa segua o meno un certo pattern.

Ad esempio, tutti gli indirizzi e-mail devono essere costituiti nel seguente modo: cominciare con una sequenza di caratteri alfanumerici, seguiti dal simbolo chiocciola, seguiti da altri caratteri alfanumerici, seguiti dal punto, seguiti da due o tre lettere.^[2] Questa regola informale diventerebbe una regex qualora fosse codificata secondo una sintassi ben precisa e riconosciuta da un programma in grado di analizzare le stringhe.

Nei linguaggi formali le espressioni regolari sono composte da costanti e operatori che denotano insiemi di stringhe, e da operazioni tra questi insiemi.

Dato un alfabeto finito ${\displaystyle \Sigma }$, sono definite le seguenti costanti:

1. ${\displaystyle \varnothing }$ o ${\displaystyle \emptyset }$ (insieme vuoto)
2. ${\displaystyle \epsilon }$ (stringa vuota, ovvero la stringa di lunghezza 0)
3. ${\displaystyle \left\{a\right\}}$ (carattere, ${\displaystyle \forall a\in \Sigma }$)

e le seguenti operazioni:

1. concatenazione: RS o ${\displaystyle R\circ S}$ indica l'insieme ${\displaystyle \left\{\alpha \beta |\alpha \in R\land \beta \in S\right\}}$
2. unione: ${\displaystyle R\cup S}$ indica l'unione dei due insiemi
3. stella di Kleene: ${\displaystyle R^{*}}$ indica l'insieme che contiene tutte le possibili iterazioni ottenibili dagli elementi di R
4. intersezione: ${\displaystyle R\cap S}$ indica l'intersezione tra i due insiemi di stringhe
5. complemento: il complementare di R indica l'insieme delle stringhe appartenenti a ${\displaystyle \Sigma ^{*}\setminus R}$

Ad esempio dati ${\displaystyle R=\left\{a,b\right\}}$ e ${\displaystyle S=\left\{7,8\right\}}$, ${\displaystyle RS=\left\{a7,b7,a8,b8\right\}}$ e ${\displaystyle S^{*}=\left\{\epsilon ,7,8,77,78,87,88,777,778,\cdots \right\}}$

Allora, possiamo dire che un'espressione regolare, definita a partire da un alfabeto ${\displaystyle \Sigma }$ ed un insieme di simboli ${\displaystyle \left\{+,*,(,),.,\emptyset \right\}}$, è una stringa ${\displaystyle R\in {\left(\Sigma \cup \left\{+,*,(,),.,\emptyset \right\}\right)}^{+}}$ che rende vera alcuna delle seguenti condizioni:

1. ${\displaystyle R=\emptyset }$
2. ${\displaystyle R\in \Sigma }$
3. ${\displaystyle R=S+T}$ o ${\displaystyle R=ST}$ o ${\displaystyle R=S^{*}}$, dove S e T sono espressioni regolari sull'alfabeto ${\displaystyle \Sigma }$

Le espressioni regolari sono utilizzate principalmente da editor di testo per la ricerca e la sostituzione di porzioni del testo. Grande importanza rivestono inoltre nell'informatica teorica, nella quale, ad esempio, sono utilizzate per rappresentare tutti i possibili cammini su un grafo. Tuttavia, le espressioni regolari sono adatte a rappresentare un ristrettissimo insieme di linguaggi formali (se volessimo rappresentare espressioni aritmetiche o linguaggi di programmazione, avremmo già bisogno di utilizzare linguaggi di tipo 2): l'utilizzo dei linguaggi regolari è comunque conveniente, in quanto la chiusura degli stessi alle operazioni di unione, intersezione e complementazione, permettono la costruzione di un'algebra di Boole e una buona capacità decisionale.

In base allo standard POSIX, la sintassi delle espressioni regolari in UNIX esiste in due versioni diverse:

• la sintassi detta di base è quella che è stata creata per prima ed è la più diffusa: un esempio di applicativo che la usa è ed;
• la sintassi detta nuova, cioè quella che è stata definita con lo standard POSIX.2, viene usata ad esempio da egrep.

Quando è stata proposta la nuova versione della sintassi delle espressioni regolari, si è deciso di rendere obsoleta la versione vecchia, solo che oramai la diffusione della vecchia versione era tale che cambiare non era proficuo^[3]. La maggior parte dei programmi che utilizzano le regexp, come grep e sed, utilizzano tali regole di base fornendo al contempo supporto per le nuove regole estese. In questa sintassi, la maggior parte dei caratteri sono visti come letterali, e trovano solo se stessi; ad esempio: "a" trova "a"; "bc)" trova "bc)". Le eccezioni a questa regola sono i metacaratteri:

Vecchie versioni di grep non supportano il separatore alternativo "|".

Esempi

".atto" trova ogni stringa di cinque caratteri come gatto, matto o patto

"[gm]atto" trova gatto e matto

"[^p]atto" trova tutte le combinazioni dell'espressione ".atto" tranne patto

"^[gm]atto" trova gatto e matto ma solo all'inizio di una riga

"[gm]atto$" trova gatto e matto ma solo alla fine di una riga

Dal momento che molte serie di caratteri variano a seconda della configurazione locale (in alcuni casi le lettere sono organizzate in abc..xyzABC...XYZ, in altri aAbB..yYzZ), lo standard POSIX ha definito alcune classi o categorie di caratteri come mostrato nella seguente tabella:

Le parentesi quadrate fanno parte della sintassi per indicare la classe di caratteri. Ad esempio [[:upper:][:digit:]ab] trova corrispondenza in una qualsiasi lettera maiuscola, in una qualsiasi cifra, nella lettera 'a' minuscola e nella lettera 'b' minuscola.

• * Cerca l'occorrenza (zero o più volte) del carattere o insieme di caratteri cui segue:

abc* identifica ab seguito da zero o più c

come in ab, abc, abcc, abccc

• + Cerca l'occorrenza (una o più volte) del carattere o insieme di caratteri cui segue:

ab[ce]+ identifica ab seguito da una o più c oppure una o più e

come in abc, abec, abccc, abcceeecccccce

• ? Cerca l'occorrenza (zero o una volta) del carattere o insieme di caratteri cui segue:

abc? identifica ab seguito o meno da una c

come in abc e ab

• {m, n} Cerca l'occorrenza (da m a n volte; m lasciato vuoto è zero, n lasciato vuoto infinito) del carattere, insieme di caratteri o sotto-regex cui segue:

(ab){1,2} identifica le sequenze di uno o due ab

come in ab e abab

• (EN) Regular expression, in Encyclopedia of Computer Science, Hoboken, Wiley, 2003.

• Glob pattern
• ^txt2regex$

• Wikibooks contiene un manuale sulle espressioni regolari
• Wikiversità contiene una lezione riguardante i linguaggi ed espressioni regolari
• Wikimedia Commons contiene immagini o altri file sulle espressioni regolari

• (EN) Eric W. Weisstein, Regular Expression, su MathWorld, Wolfram Research.
• (EN) Denis Howe, regular expression, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• (EN) Regular expression, su fon.hum.uva.nl.
• Manuale di Wikipedia sulle espressioni regolari

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica