Espressione regolare

Da Wikipedia, l'enciclopedia libera.

(Reindirizzamento da Regular expression)

Le espressioni regolari (in inglese regular expression, che può trovarsi abbreviata in regexp, regex o RE) sono sintassi attraverso le quali si possono rappresentare insiemi di stringhe. Gli insiemi caratterizzabili con espressioni regolari sono anche detti linguaggi regolari (e coincidono quelli generabili dalle grammatiche regolari e riconoscibili dagli automi a stati finiti).

Più rigorosamente possiamo definire un'espressione regolare, a partire da un alfabeto Σ ed un insieme di simboli {+,*,(,),.,∅} come la stringa R appartenente a (Σ ∪ {+,*,(,),.,∅})+ tale che valga una delle seguenti operazioni

R = ∅
R appartiene a Σ
R = S+T oppure R=ST oppure R=S* con S e T sono espressioni regolari sull'alfabeto Σ

Indice

1 Storia
2 Espressioni regolari nei linguaggi formali
3 Impiego delle espressioni regolari
4 Sintassi
- 4.1 Espressioni regolari tradizionali di UNIX
5 Altri progetti

[modifica] 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 delle funzioni che ne permettessero l'uso fu una versione di QED scritta da Ken Thompson, uno dei pionieri di Unix.

L'editor, a linea 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ò de facto uno standard.

La grandissima diffusione di questi strumenti spinse alcuni sviluppatori a implementare le espressioni regolari anche in altri linguaggi, a mezzo di librerie come PCRE o persino a svilupparne implementazioni native per alcuni linguaggi, come Java e tcl.

Attualmente le espressioni regolari sono disponibili nella maggioranza degli editor di testo per GNU/Linux e altri sistemi unix-like.

[modifica] 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 Σ, sono definite le seguenti costanti:

(insieme vuoto) $\varnothing$ o ∅ oppure Λ
(stringa vuota) ε indica la stringa vuota (ben diverso dal linguaggio vuoto)
(carattere) a in Σ indica l'insieme {"a"}

e le operazioni:

(concatenazione) RS o R°S indica l'insieme { αβ | α in R e β in S }
(unione) R ∪ S indica l'unione dei due insiemi
(stella di Kleene) R* indica l'insieme che contiene tutte le possibili iterazioni ottenibili dagli elementi di R
(intersezione) R ∩ S indica l'intersezione tra i due insiemi di stringhe.
complementazione di R indica l'insieme delle stringhe appartenenti a Σ*-R

Ad esempio dati R = { "a","b" } e S = { "7","8" }

RS = { "a7", "b7", "a8", "b8" }
S* = { ε, "7", "8", "77", "78", "87", "88", "777", "778", ... }

Nelle grammatiche di Chomsky le espressioni regolari si utilizzano (insieme con gli automi a stati finiti) per rappresentare i linguaggi di tipo 3.

[modifica] 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 nell'informatica teorica, nella quale, ad esempio, sono utilizzate per rappresentare tutti i possibili cammini su un grafo. Tuttavia i linguaggi di tipo 3 e, quindi, 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 ed una buona decidibilità.

[modifica] Sintassi

[modifica] Espressioni regolari tradizionali di UNIX

La sintassi di base delle espressioni regolari in UNIX è attualmente definita obsoleta dallo standard POSIX, ma è comunque molto usata a causa della sua diffusione. 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 ("a" trova "a", "bc)" trova "bc)" ecc.). Le eccezioni a questa regola sono i metacaratteri:

.	Trova ogni singolo carattere (se è nella modalità linea singola altrimenti se è in multiriga prende tutti i caratteri diversi da \n, ovvero un a capo).
[ ]	Trova un singolo carattere contenuto nelle parentesi. Ad esempio, [abc] trova o una "a", "b", o "c". [a-z] è un intervallo e trova ogni lettera minuscola dell'alfabeto. Possono esserci casi misti: [abcq-z] trova a, b, c, q, r, s, t, u, v, w, x, y, z, esattamente come [a-cq-z]. Il carattere '-' è letterale solo se è primo o ultimo carattere nelle parentesi: [abc-] o [-abc]. Per trovare un carattere '[' o ']', il modo più semplice è metterli primi all'interno delle parentesi: [][ab] trova ']', '[', 'a' o 'b'.
[^ ]	Trova ogni singolo carattere non incluso nelle parentesi. Ad esempio, [^abc] trova ogni carattere diverso da "a", "b", o "c". [^a-z] trova ogni singolo carattere che non sia una lettera minuscola. Come sopra, questi due metodi possono essere usati insieme.
^	Corrisponde all'inizio della stringa (o di ogni riga della stringa, quando usato in modalità multilinea)
$	Corrisponde alla fine della stringa o alla posizione immediatamente precedente un carattere di nuova linea (o alla fine di ogni riga della stringa, quando usato in modalità multilinea)
( )	Definisce una "sottoespressione marcata". Ciò che è incluso nell'espressione, può essere richiamato in seguito. Vedi sotto, \n.
\n	Dove n è una cifra da 1 a 9; trova ciò che la nesima sottoespressione ha trovato. Tale costrutto è teoricamente irregolare e non è stato adottato nella sintassi estesa delle regexp.
*	Un'espressione costituita da un singolo carattere seguito da "", trova zero o più copie di tale espressione. Ad esempio, "[xyz]" trova "", "x", "y", "zx", "zyx", e così via. \n, dove n è una cifra da 1 a 9, trova zero o più iterazioni di ciò che la nesima sottoespressione ha trovato. Ad esempio, "(a.)c\1" trova "abcab" e "abcaba" ma non "abcac". Un'espressione racchiusa tra "$" e "$" seguita da "" non è valida. In alcuni casi (es. /usr/bin/xpg4/grep di SunOS 5.8), trova zero o più ripetizioni della stringa che l'espressione racchiusa ha trovato. In altri casi (es. /usr/bin/grep di SunOS 5.8), trova ciò che l'espressione racchiusa ha trovato, seguita da un letterale "".
{x,y}	Trova l'ultimo "blocco" almeno x volte e non più di y volte. Ad esempio, "a{3,5}" trova "aaa", "aaaa" o "aaaaa".

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:

classe POSIX	sintassi normale	significato
[:upper:]	[A-Z]	lettere maiuscole
[:lower:]	[a-z]	lettere minuscole
[:alpha:]	[A-Za-z]	lettera sia maiuscole che minuscole
[:alnum:]	[A-Za-z0-9]	numeri e lettere maiuscole e minuscole
[:digit:]	[0-9]	numeri
[:xdigit:]	[0-9A-Fa-f]	numeri in formato esadecimale
[:punct:]	[.,!?:...]	segni di interpunzione
[:blank:]	[ \t]	spazio o TAB
[:space:]	[ \t\n\r\f\v]	caratteri vuoti
[:cntrl:]		caratteri control
[:graph:]	[^ \t\n\r\f\v]	caratteri non vuoti
[:print:]	[^\t\n\r\f\v]	caratteri non vuoti e spazi

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.