Espressione regolare

Da Wikipedia, l'enciclopedia libera.

Le espressioni regolari (in inglese regular expression, che può trovarsi abbreviata in regexp, regex o RE) sono una sintassi attraverso la quale 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 Espressioni regolari nei linguaggi formali
2 Impiego delle espressioni regolari
3 Sintassi
- 3.1 Espressioni regolari tradizionali di UNIX
4 Altri progetti

[modifica] Espressioni regolari nei linguaggi formali

Le espressioni regolari sono composte da costanti e operatori che denotano insiemi di stringhe, e da operatori 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 è stata ora definita obsoleta dal POSIX, ma è comunque molto usata a causa della sua diffusione. La maggior parte dei programmi che utilizzano le regexp, come grep e sed, usano il vecchio sistema.

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
[ ]	Trova un singolo carattere contenuto nelle parentesi. Ad esempio, [abc] trova o una "a", "b", o "c". [a-z] è un intervallo e trova ogni lettere 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 d'una riga (o ad una riga, quando usato in modalità multilinea)
$	Corrisponde alla fine d'una riga (o ad una riga, 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