Utente:LoStrangolatore/Espressioni regolari/Concetti generali
TODO:
- il sommario del libro dovrebbe essere come il riquadro orizzontale che è qui in cima alla pagina (quello che comprende i 4 link: "Tutorial", "Tools and Languages", ecc.)
- mettere un link "↑ Indice" in ciascuno dei riquadri di navigazione in questa pagina (intendo quelli che hanno i link per la sezione precedente e per la sezione successiva)
Una espressione regolare è una scrittura che identifica più stringhe allo stesso tempo. Un programma o una libreria software legge una stringa, la confronta con la regex carattere per carattere, finché non trova una parte di quella stringa che corrisponde esattamente alla regex fornita.
Ogni ambiente di esecuzione (programma o libreria) riconosce una sintassi specifica, quindi il significato di uno stesso simbolo cambia leggermente tra ambienti di esecuzione diversi. Tuttavia, tutti (o quasi tutti) gli ambienti condividono gli stessi concetti e regole di base.
Questa pagina illustra i concetti che accomunano tutte o buona parte delle varianti accettate dai diversi ambienti di esecuzione. Tuttavia, potrebbero esserci differenze di notazione e/o di significato tra quanto scritto di seguito e quanto accettato da un certo ambiente. Per tali differenze, si rimanda alla pagina di questo libro dedicata a tale ambiente.
Principio di funzionamento
[modifica | modifica sorgente]La regex individua un insieme di stringhe in questo modo: elenca in sequenza le porzioni che le stringhe hanno in comune, e delle alternative per le parti rimanenti. Il software (che nel seguito sarà chiamato anche motore di analisi o solo motore) si posiziona sul primo carattere della stringa e la scorre da sinistra verso destra, cercando, tra tutte le combinazioni possibili delle alternative, quella che corrisponde ai caratteri che man mano legge dalla stringa. Questo processo è chiamato backtracking.
Se la ricerca ha esito positivo, termina in questo punto. In caso contrario, il motore ricomincia da capo, partendo però dal secondo carattere della stringa. Se nessuna delle combinazioni previste dalla regex corrisponde alla stringa, ricomincia la ricerca partendo dal terzo carattere, e così via. L'ultima ricerca parte dall'ultimo carattere della stringa, dopo la quale il motore termina con il messaggio di "stringa non trovata".
- Esempi
Si applica la regex abc alla stringa abc. Questa regex significa: il carattere a, seguito dal carattere b, seguito dal carattere c.
Il motore comincia a cercare dal primo carattere della stringa, scorrendo la regex e la stringa da sinistra verso destra, e individua al primo colpo tutti e tre i caratteri. Arrivato alla fine della regex, dato che ha individuato una combinazione (in realtà l'unica) che ha una corrispondenza nella stringa, termina con il risultato di "stringa trovata" ed evidenziando l'intera parola abc.
Se la stringa fosse stata abcd invece che abc, il motore avrebbe eseguito gli stessi identici passi, e il carattere d non sarebbe stato neanche letto. Il risultato sarebbe stato il messaggio di "stringa trovata" e sarebbero stati evidenziati solo i primi tre caratteri della stringa.
Si applica la regex abc alla stringa babc.
- Il motore comincia a cercare dal primo carattere della stringa, scorrendo la regex e la stringa da sinistra verso destra. La regex comincia con una
a, mentre il primo carattere della stringa è una b, pertanto il motore si ferma, si posiziona al primo carattere della regex e al secondo carattere della stringa, e ricomincia a cercare. - Il primo carattere che viene letto durante questa nuova ricerca (cioè il secondo carattere della stringa) è una a, che corrisponde con la regex. Il motore si muove in avanti lungo la regex e lungo la stringa, quindi confronta
bcon b. C'è corrispondenza, pertanto confronta i due caratteri che seguono, cioèce c; anche qui c'è corrispondenza. - Il motore si accorge che non ci sono più caratteri da leggere nella regex, quindi termina con il risultato di "stringa trovata" ed evidenziando gli ultimi tre caratteri della parola babc.
- Caratteri e metacaratteri
I caratteri alfanumerici e alcuni segni di punteggiatura rappresentano se stessi: ad esempio, la regex pippo123 identifica solo la stringa pippo123.
Tutti gli altri simboli hanno un significato speciale, e per questo sono detti metacaratteri. Ad esempio, la regex . identifica tutte le stringhe composte da un solo carattere.
Alcuni simboli hanno un significato speciale solo se usati in combinazione con altri simboli speciali, altrimenti rappresentano se stessi. Ad esempio, 0-9 identifica solo la stringa 0-9, ma [0-9] individua tutte le stringhe che contengono un solo carattere, che è una cifra.
Classi di caratteri
[modifica | modifica sorgente]| Regex | Significato |
|---|---|
| [abc!] | Individua uno di questi caratteri: a b c ! |
| [^abc!] | Individua un carattere qualunque che non appartiene all'insieme [abc!] |
Per definire un intervallo di lettere e di numeri si usa il trattino: [a-z] identifica tutte le lettere minuscole dell'alfabeto latino[sicuro?]; [a-e1-9@] identifica una lettera compresa tra a ed e, una cifra diversa da zero, oppure il simbolo della chiocciola; e così via.
Per inserire i metacaratteri, si seguono queste regole:
- Il backslash va sottoposto ad escaping (esempio:
[\\]) ^ - ]devono essere preceduti dal backslash, oppure vanno posti in un punto in cui non possono essere interpretati come caratteri speciali. Quindi, il trattino va all'inizio o alla fine della classe, la parentesi quadra va all'inizio, e il circonflesso non va all'inizio. Esempi:[]^-][ac-][-ac]- Tutti gli altri metacaratteri si inseriscono così come sono, senza particolari accorgimenti, e senza ricorrere all'escaping.
- Esempi
on[eo]recorrisponde alle stringhe che cominciano peron, seguite dal carattereeoppure dal carattereo, seguito dare.- Quindi, corrisponde (solo) alle due parole
onereedonore.
- Quindi, corrisponde (solo) alle due parole
- ...
}}
Classi di caratteri predefinite
[modifica | modifica sorgente]Errori comuni legati all'uso del punto
Classi di caratteri predefinite in
.NET
•
Java
•
Javascript
•
Lua
•
Perl
•
Python
•
Tcl
•
PCRE
•
POSIX
L'ambiente di esecuzione può definire degli insiemi "preconfezionati" aggiuntivi, che non si indicano con le parentesi quadre, ma con una sintassi che dipende dall'ambiente di esecuzione in uso. Tra questi insiemi predefiniti ci sono l'insieme di tutti i caratteri alfanumerici, l'insieme di tutti i caratteri di spaziatura, e così via. Di seguito, si userà per comodità la sintassi \k.
TODO Sezioni "Shorthand Character Classes" e "Negated Shorthand Character Classes" di [1]
- Il punto
| Regex | Significato |
|---|---|
| . (single-line mode disattivata) |
[^\n] oppure [^\r\n], a seconda del contesto |
| . (single-line mode attivata) |
Un carattere qualunque. Equivale a [\w\W] e simili. |
Il punto individua un qualunque carattere diverso dai caratteri di nuova riga, pertanto . equivale a [^\n] in ambiente Unix e [^\r\n] in ambiente Windows. È così per ragioni storiche, in quanto i primi programmi che accettavano regex lavoravano su righe singole, che quindi non potevano contenere i caratteri di nuova riga.
Un numero sempre maggiore di motori supporta la cosiddetta single-line mode, la quale fa sì che il punto indichi un carattere qualunque, anche un carattere di nuova riga. Se questa modalità è attivata, il punto diventa equivalente a una classe come [\w\W], [\s\S], o simile. Questa notazione alternativa è particolarmente utile per quei motori che non supportano la modalità single-line.
La single-line mode interessa il punto, e non va confusa con la multi-line mode, la quale interessa invece le ancore.
}}
OR tra regex
[modifica | modifica sorgente]La regex a|b individua tutte le stringhe che corrispondono alla regex a oppure alla regex b.
In casi più complessi, ci si aiuta con le parentesi. Esempio: Sergio ha (due|tre) (mele|albicocche) individua le quattro stringhe
Sergio ha due meleSergio ha tre meleSergio ha due albicoccheSergio ha tre albicocche
Quantificatori
[modifica | modifica sorgente]| Regex | Significato |
|---|---|
| a{m,M} | a ripetuto almeno m volte e non più di M volte Equivalente all'uso della barra verticale |
| a{m,} | a ripetuto almeno m volte (M = illimitato) |
| a{m} | a ripetuto esattamente m volte Forma equivalente: a{m,m} |
| a? | a zero o una volta Forma equivalente: a{0,1} |
| a* | a zero o più volte Forma equivalente: a{0,} |
| a+ | a una o più volte Forma equivalente: a{1,} |
I quantificatori ripetono la regex e non i caratteri trovati. Ad esempio, [abc]{3} equivale a
[abc][abc][abc]
e quindi non vuol dire un carattere dell'insieme [abc] ripetuto 3 volte, ma vuol dire la regex [abc] ripetuta 3 volte. In definitiva, riconosce le stringhe aaa, bbb e ccc, ma anche abc, cbc e bac. Per ripetere il carattere, si deve usare un backreference.
I quantificatori agiscono solo sul componente che li precede, che di solito è un carattere singolo: giu?oco corrisponde alle stringhe gioco e giuoco. Per quantificare insieme più componenti, ci si aiuta con le parentesi: Austr(al)?ia corrisponde a tutte le stringhe che cominciano con Austr, seguite dalla coppia di caratteri al presente zero o una volta, seguito da ia, quindi corrisponde (solo) alle due stringhe Austria ed Australia.
Ancore
[modifica | modifica sorgente]Un'ancora non cerca un carattere, ma una posizione tra due caratteri.
- Inizio e fine testo
I due simboli che identificano rispettivamente l'inizio e la fine del testo dipendono dal programma in uso.
- Inizio e fine testo o riga
I simboli ^ (quando è fuori dalle parentesi quadre) e $ identificano rispettivamente l'inizio e la fine dell'input. Quindi, la regex
^pippo
identifica tutte le stringhe che iniziano con i cinque caratteri pippo; la regex
^pippo$
identifica solo la stringa di cinque caratteri pippo.
Tuttavia, il significato esatto di questi due simboli dipende dal programma in uso. Di solito, in un editor di testo, identificano l'inizio e la fine di una riga, mentre nelle librerie dei linguaggi di programmazione indicano tipicamente l'inizio e la fine dell'intero testo passato come input. In questo secondo caso, per attivare il primo comportamento, bisogna abilitare la modalità multi-riga (multi-line mode) con un meccanismo che dipende dal linguaggio di programmazione e dalla libreria in uso.
- Word boundaries
 | Questa sezione è ancora vuota; aiutaci a scriverla! |
Capturing groups
[modifica | modifica sorgente]Una coppia di parentesi tonde definisce un cosiddetto capturing group, cioè un segnaposto che si riempie durante l'analisi della stringa. I capturing groups impongono al programma di ricordare ciò che ha incontrato durante l'analisi.
Ad esempio, la regex le ([0-9]) (di mattina|del pomeriggio) applicata alla stringa Mi sono svegliato alle 5 del pomeriggio non solo riconosce la stringa le 5 del pomeriggio, ma ricorda che la prima coppia di parentesi ha incontrato la stringa 5, e che la seconda coppia ha incontrato la stringa del pomeriggio.
Questo risultato può essere sfruttato per ulteriori elaborazioni, perché può essere ricavato esplicitamente. Infatti, il k-esimo capturing group è identificato dal cosiddetto backreference, che in genere ha sintassi \k.
- I backreference possono essere usati all'interno della stessa espressione regolare. Ad esempio, la regex
Car([ao]), bentornat\1!corrisponde solo alle due stringheCara, bentornata!eCaro, bentornato!, assicurando la concordanza del genere. - Molti programmi e librerie software hanno una funzione chiamata Sostituisci o Cerca e sostituisci, che rimpiazza le occorrenze della regex sostituendole con una certa stringa, che può contenere dei backreference. Ad esempio, si può cercare
Car(o|a)e sostituirlo conCarissim\1. - Se si sta usando una libreria software, in genere il processo di analisi di una stringa viene svolto tramite un oggetto software, e quindi il valore acquisito da un capturing group può essere ricavato leggendo una certa proprietà di quell'oggetto.
I backreference sono un'estensione che permette alle espressioni regolari di descrivere alcuni linguaggi non regolari.
- Altri tipi di gruppi
Alcuni motori di analisi considerano come capturing group ogni coppia di parentesi tonde il cui contenuto non cominci con un punto interrogativo. Infatti, per questi motori, il punto interrogativo identifica un atomic group, un lookaround, un commento, o un gruppo di altro tipo.
- Gruppi con nomi
TODO [2]
TODO Aggiungere http://www.regular-expressions.info/brackets.html
}}
Escaping
[modifica | modifica sorgente]Il backslash cambia il significato del carattere che lo segue:
- se è un metacarattere, lo rende un carattere "normale",
- altrimenti attiva un significato speciale che dipende dall'ambiente di esecuzione.
In inglese, questa pratica viene chiamata escaping, e il carattere che viene marcato dal backslash viene detto escaped character. Alcuni esempi:
- Il simbolo
+è un quantificatore, invece\+rappresenta il carattere +. - La lettera
srappresenta se stessa, ma la combinazione\srappresenta tipicamente la classe dei caratteri di spaziatura.
Alcuni ambienti di esecuzione permettono di applicare l'escaping a più metacaratteri insieme, includendoli tra \Q...\E
Ad esempio: -1\+\(3\*7\)=\+20 può essere scritto più semplicemente come \Q-1+(3*7)=+20\E.
Se \E si trova alla fine della regex, può essere omesso. Inoltre, un quantificatore posto dopo \E viene applicato solo all'ultimo carattere che lo precede e non all'intera sequenza.
- Errori frequenti
Anche -1+(3*7)=+20 è una regex corretta, ma ha un significato diverso, perché i simboli + e * sono interpretati come quantificatori e le parentesi tonde definiscono un capturing group. Il motore di analisi non può sapere qual è il significato desiderato, quindi non segnala un errore, ma prosegue nella ricerca.
Alcuni linguaggi di programmazione fanno essi stessi uso del backslash per l'escaping dei propri caratteri speciali, all'interno del codice sorgente. In questi linguaggi, lo stesso backslash è a sua volta un carattere speciale. Ad esempio, in C++, una stringa come "\\" contiene un solo carattere: il primo backslash indica l'escaping del carattere che lo segue, pertanto il secondo backslash viene interpretato come un carattere normale.
Per scrivere una regex usando questi linguaggi, conviene dapprima scriverla a parte con la sintassi apposita, poi inserirla nel testo del programma applicando l'escaping ai backslash ed eventualmente scrivendo la regex iniziale in un commento nel codice sorgente.
Esempi d'uso:
- Si vuole scrivere in C++ una stringa che contiene una regex che corrisponde solo alla stringa C:\pippo. La regex è
C:\\pippo, e per inserirla nel codice sorgente C++ bisogna applicare l'escaping a ciascuno dei due backslash: quindi il risultato èstring regex = "C:\\\\pippo" - Si vuole scrivere in C++ la regex
a\s+b. Applicando l'escaping al backslash, si ottienea\\s+b
Atomic groups
[modifica | modifica sorgente]TODO da http://www.regular-expressions.info/atomic.html#use
Avidità dei quantificatori
[modifica | modifica sorgente]| Quantificatori | Nome | Significato |
|---|---|---|
|
a{m,M} a? |
Greedy | Catturano il maggior numero di ripetizioni tale che sia seguito da... |
|
a{m,M}? a?? |
Reluctant o lazy | Catturano il minor numero di ripetizioni tale che sia seguito da... |
|
a{m,M}+ a?+ |
Possessive | Catturano il massimo numero di ripetizioni. |
Ciascun quantificatore è disponibile in tre versioni.
- I quantificatori presentati finora sono detti greedy (che in italiano vuol dire avidi), perché catturano il maggior numero di ripetizioni possibile affinché il resto della regex sia soddisfatto.
- Aggiungendo un punto interrogativo, sono detti reluctant o lazy (in italiano riluttanti o pigri) perché catturano il minor numero di ripetizioni possibile affinché il resto della regex sia soddisfatto.
- Aggiungendo il simbolo
+, i quantificatori sono detti possessive, perché catturano il massimo numero di ripetizioni possibile, a prescindere dal resto dell'espressione.
Esempi:
- todo
- Differenza tra greedy e possessive
L'effetto di un quantificatore greedy dipende dal seguito della regex. Ciò ha conseguenze importanti sulle prestazioni delle regex. Infatti, il motore di ricerca deve andare per tentativi, controllando il seguito con le varie ripetizioni possibili, ovviamente cominciando da quelle più lunghe. In altre parole, il motore di ricerca esegue questi passi:
- memorizza temporaneamente il massimo numero di ripetizioni;
- controlla se il seguito della regex è soddisfatto; in caso affermativo, termina con il risultato: "stringa trovata";
- altrimenti, considera una ripetizione in meno e ripete il controllo, ripetendo questo passo finché non viene trovato un riscontro o finché le ripetizioni non sono terminate.
Questo tipo di ricerca si chiama backtracking, e può essere estremamente lento, perché consiste nel controllare tutte le combinazioni possibili finché non viene trovata quella giusta.
Ad esempio, la regex \d+\d\d\d individua la successione di cifre più lunga tale che dopo di essa ci siano altre tre cifre. La corrispondenza di questa regex nella stringa 12345 è, evidentemente, 12. Il motore di analisi non può saperlo a priori, ma deve calcolarlo scorrendo la stringa un carattere per volta, pertanto deve eseguire questi passi:
- prova a sostituire
\d+con il massimo numero di cifre in sequenza, cioè12345, dopodiché controlla se queste sono seguite da altre tre cifre ===> falso; - allora prova con quattro ripetizioni, cioè sostituisce
\d+con1234, e controlla se è seguita da altre tre cifre ===> falso; - allora prova con tre ripetizioni, cioè sostituisce
\d+con123, e controlla se è seguita da altre tre cifre ===> falso; - allora prova con due ripetizioni, cioè sostituisce
\d+con12, e controlla se è seguita da altre tre cifre ===> vero, perché 345 corrisponde a\d\d\d.
Quindi la ricerca termina con successo.
Al contrario, l'effetto di un quantificatore possessive prescinde dal seguito della regex. Cercare con un quantificatore possessive vuol dire semplicemente cercare il massimo numero di ripetizioni. Applicare la regex \d++\d\d\d alla stringa 12345 vuol dire eseguire questi passi:
- sostituire
\d++con il massimo numero di ripetizioni, cioè12345; - controllare se queste cifre sono seguite da altre tre cifre ===> falso.
In questo caso, la ricerca fallisce.
TODO - aggiungere da: [3]; [4]
TODO - Alternativa al +? presa da [5] (sezione "An alternative to Laziness"), che è più efficiente ed anche supportata da un maggior numero di ambienti di esecuzione
TODO - atomic groups e possessive quantifiers: [6], sezione "Alternative Solution Using Atomic Grouping"
- Esempi
- Descrivi l'effetto di
a+?rgh!, applicata alla stringa aaaaaaaaaaargh!- Il motore di analisi legge la stringa un carattere alla volta, da sinistra verso destra. Quando incontra la prima a, la associa ad
a+?, e, partendo da quel punto, comincia la ricerca di tutte le a che seguono. Quindi la regex include tutta la stringa.
- Il motore di analisi legge la stringa un carattere alla volta, da sinistra verso destra. Quando incontra la prima a, la associa ad
Lookaround
[modifica | modifica sorgente]| Regex | Significato |
|---|---|
| (?=regex) | Positive lookahead |
| (?!regex) | Negative lookahead |
| (?<=regex) | Positive lookbehind |
| (?<!regex) | Negative lookbehind |
I lookaround controllano se il contenuto che precede (lookahead) o che segue (lookbehind) un punto di una stringa, corrisponde (positive) o non corrisponde (negative) ad una certa regex.
Non catturano caratteri; restituiscono un valore di verità del tipo "regex trovata" o "regex non trovata".
- Esempi
A. Si vuole analizzare la stringa Antonio con la regex An(?=to)nio.
- Per prima cosa, il motore trova An all'inizio della stringa.
- Segue un lookahead che controlla se i due caratteri che seguono corrispondono a to; è così, quindi il motore prosegue la ricerca.
- I lookahead non catturano caratteri, quindi il motore controlla se i caratteri che seguono An sono pari a nio; il controllo fallisce.
- Il motore ricomincia a cercare, partendo dal secondo carattere (n). Dato che da qui in poi non ci sono ulteriori occorrenze di An, la ricerca termina con il risultato di "stringa non trovata".
B. Si vuole analizzare la stringa Antnio con la regex An(?=to)nio.
- Il motore cerca An e lo trova all'inizio della stringa.
- Segue un lookahead che controlla se i due caratteri che seguono corrispondono a to. Il controllo fallisce, perché i due caratteri che seguono An sono tn.
- Quindi il motore ricomincia a cercare, partendo dal secondo carattere (n). Dato che da qui in poi non ci sono ulteriori occorrenze di An, la ricerca termina con il risultato di "stringa non trovata".
C. Da(?!vi).+de dapprima cerca la stringa Da, poi controlla i due caratteri che seguono, e controlla se sono uguali a vi. In caso affermativo, legge i caratteri rimanenti, inclusi quei due che ha appena controllato (perché il lookaround non cattura caratteri); si assicura che la stringa finisca in de. Pertanto, \bDa(?!vi).+de\b cerca tutte le parole che cominciano per Da, ma non per Davi, e terminano per de.
TODO un esempio per il lookbehind
- Proprietà dei lookaround
Anche se si scrivono con le parentesi tonde, i lookaround non sono capturing groups. Per ottenere un backreference che punti al contenuto letto da un lookaround, o a una sua parte, bisogna inserire apposta un capturing group.
Per esempio, (?=(pippo)) è un lookahead che contiene un capturing group.
Poiché i lookaround non catturano caratteri, essi sono anche atomici: dopo aver trovato una combinazione che verifica il lookaround, il motore non ne tenta altre. Ciò va tenuto presente se il lookaround contiene dei capturing groups, in particolare quando questi sono referenziati da qualche backreference, perché i valori memorizzati nei gruppi non cambiano.
TODO un esempio
- Limitazioni del lookbehind
In genere, i motori di analisi ammettono nei lookbehind solo regex che hanno una lunghezza fissa. La ragione è che il programma deve conoscere in anticipo il numero di caratteri da controllare, prima di muoversi all'indietro lungo la stringa. Ciò vuol dire che un lookbehind come (?<=[Pp]ippo) potrebbe essere accettato, mentre (?<=pipp+o) potrebbe non essere accettato. Inoltre, alcuni motori riconoscono il lookahead, ma non il lookbehind.
Per maggiori informazioni, si rimanda al capitolo specifico del motore di analisi in uso.
Modificatori
[modifica | modifica sorgente]TODO: aggiungere anche [7]
Caratteri non stampabili
[modifica | modifica sorgente]http://www.regular-expressions.info/characters.html#qe
Set di caratteri
[modifica | modifica sorgente]Altre caratteristiche
[modifica | modifica sorgente]- Commenti
Per rendere una regex più leggibile, si possono inserire dei commenti con la notazione (?#commento).
Specchietto riassuntivo
[modifica | modifica sorgente]Questo specchietto va considerato un aiuto per il lettore che vuole acquisire un'infarinatura della sintassi delle regex. I costrutti elencati di seguito potrebbero essere riconosciuti in modo diverso dai diversi ambienti di esecuzione. Per specchietti specifici per i diversi motori, si rimanda ai rispettivi capitoli.
- TODO uno specchietto come questo e/o quello che è a destra qui. Eventualmente, farne uno in un'immagine SVG che abbia le proporzioni dell'A4, così da poterlo stampare a parte.
- TODO eventualmente mettere il tutto in una pag. dedicata a specchietti e riassuntini vari messi x comodità del lettore
Gli ambienti di esecuzione
[modifica | modifica sorgente]Tabella delle differenze
[modifica | modifica sorgente]La seguente tabella riassume il supporto delle caratteristiche illustrate in questo capitolo, negli ambienti di esecuzione per i quali esiste un capitolo in questo manuale.
TODO [8]
TODO Informazioni da smistare nelle sottopagine relative ai singoli ambienti di esecuzione:
- http://www.regular-expressions.info/lookaround.html, sezione "Important Notes About Lookbehind", da "The bad news" in poi
- http://www.regular-expressions.info/dot.html
Altri linguaggi e librerie
[modifica | modifica sorgente]C, C++
- Non c'è un supporto nelle librerie standard, pertanto si ricorre a librerie di terze parti, per es. il PCRE.
PHP
Note
[modifica | modifica sorgente]Collegamenti esterni
[modifica | modifica sorgente]- Altri tutorial