Indietro

ⓘ Espressione regolare




Espressione regolare
                                     

ⓘ Espressione regolare

Una espressione regolare è una sequenza di simboli che identifica un insieme di stringhe. Programmi diversi supportano notazioni diverse per esprimere le stesse espressioni regolari, pertanto non esiste una sintassi "universale".

Le espressioni regolari 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 che permettono di ampliare linsieme di linguaggi definibili.

                                     

1. Storia

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 luso fu una versione di QED scritta da Ken Thompson, uno dei pionieri di Unix.

Leditor, 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 luso di espressioni regolari. La versatilità del linguaggio, dovuta anche al fatto dessere un linguaggio interpretato, ne permise lutilizzo 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.

                                     

2. Descrizione

Una 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. 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.

                                     

2.1. Descrizione Espressioni regolari 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:

  • ϵ {\displaystyle \epsilon } stringa vuota, ovvero la stringa di lunghezza 0
  • ∅ {\displaystyle \varnothing } o ∅ {\displaystyle \emptyset } insieme vuoto
  • { a } {\displaystyle \left\{a\right\}} carattere, ∀ a ∈ Σ {\displaystyle \forall a\in \Sigma }

le seguenti operazioni:

  • complemento: il complementare di R indica linsieme delle stringhe appartenenti a Σ ∗ ∖ R {\displaystyle \Sigma ^{*}\setminus R}
  • concatenazione: RS o R ∘ S {\displaystyle R\circ S} indica linsieme { α β | α ∈ R ∧ β ∈ S } {\displaystyle \left\{\alpha \beta |\alpha \in R\land \beta \in S\right\}}
  • unione: R ∪ S {\displaystyle R\cup S} indica lunione dei due insiemi
  • stella di Kleene: R ∗ {\displaystyle R^{*}} indica linsieme che contiene tutte le possibili iterazioni ottenibili dagli elementi di R
  • intersezione: R ∩ S {\displaystyle R\cap S} indica lintersezione tra i due insiemi di stringhe

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

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

  • R ∈ Σ {\displaystyle R\in \Sigma }
  • R = ∅ {\displaystyle R=\emptyset }
  • R = S + T {\displaystyle R=S+T} o R = S T {\displaystyle R=ST} o R = S ∗ {\displaystyle R=S^{*}}, dove S e T sono espressioni regolari sullalfabeto Σ {\displaystyle \Sigma }


                                     

2.2. Descrizione Impiego delle espressioni regolari

Le espressioni regolari sono utilizzate principalmente da editor di testo per la ricerca e la sostituzione di porzioni del testo. Grande importanza rivestono inoltre nellinformatica 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: lutilizzo dei linguaggi regolari è comunque conveniente, in quanto la chiusura degli stessi alle operazioni di unione, intersezione e complementazione, permettono la costruzione di unalgebra di Boole ed una buona capacità decisionale.

                                     

3.1. Sintassi Espressioni regolari tradizionali di UNIX

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

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

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.

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)"; ecc. 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 "+ identifica ab seguito da una o più c oppure una o più e come in abc, abec, abccc, abcceeecccccce
  • ? Cerca loccorrenza 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 loccorrenza 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