Hardware Upgrade Forum - View Single Post

MaxArt · 15-06-2010, 21:46

Espressioni Regolari avanzate
Quello che abbiamo visto finora è una guida di base, che già consente di fare parecchio con le espressioni regolari. Ma le RE possono fare ancora di più, ed inoltre si possono apprendere diversi trucchetti per migliorare le performance. Perché le basi delle RE si imparano in fretta, ma molto più ostico è creare delle RE che funzionino bene e che non uccidano le performance del nostro codice: spesso è facile creare delle RE la cui complessità è O(2^n) rispetto alla lunghezza della stringa. Immaginatevi le conseguenze...

Lookarounds
Supponiamo di avere una stringa al cui interno vogliamo identificare una... stringa, cioè una sequenza di caratteri racchiusa tra apici. È un caso comune se ci capita di dove fare il parsing di un codice o proto-codice, o semplicemente di un elenco di valori che possono essere anche delle stringhe delimitate da apici. Un'espressione regolare adeguata potrebbe essere '[^']*'. Non è difficile da interpretare: si cerca una stringa che inizi con un apice, prosegua con una sequenza di qualsivoglia lunghezza di caratteri che non siano apici, e poi si conclude con un apice.
Ma supponiamo che all'interno della stringa sia permesso inserire degli apici, purché adeguatamente preceduti da una backslash: in fondo, gli apici ci servono anche come apostrofi. Si potrebbe, infatti, avere qualcosa tipo 'un\'automobile', e la nostra RE si fermerebbe al solo 'un\'. Quello che dobbiamo fare è, allora, cercare di includere questi apici con escape, e per farlo il modo migliore sono i lookarounds, cioè delle sequenze di simboli che ci consentono di specificare da cosa dev'essere preceduta (lookbehind) o succeduta (lookahead) un gruppo perché esso venga considerato. Si noti che l'argomento dei lookaround non viene incluso nel gruppo di ricerca, ed è questo il loro punto fondamentale.

(?=...) positive lookahead. Specifica che la sequenza di caratteri dev'essere seguita dall'argomento compreso tra (?= e ).
(?!...) negative lookahead. Questa volta, si specifica che non debba essere seguita dall'argomento del lookahead.
(?<=...) positive lookbehind. Il gruppo verrà considerato solo se preceduto dall'argomento del lookbehind.
(?<!...) negative lookbehind. Il contrario di sopra.

Quello che ci serve nel nostro esempio è un positive lookbehind. Si noti che i lookahead venno specificati dopo il gruppo in esame, mentre i lookbehind prima. Dunque, la nostra espressione regolare diventa '(?:[^']|(?<=\\)')*'. Esaminiamola, in modalità free-space:

Codice:

'        # indica che la stringa deve iniziare con un apice
(?:      # dentro questo gruppo ci mettiamo i caratteri che vogliamo, cioè tutti tranne gli apici, a meno che non siano preceduti da \
[^']     # questo vuol dire "tutti i caratteri che non siano apici"
|        # quest'alternanza ci serve per dire che vogliamo includere anche gli apici preceduti da \
(?<=\\)' # questa sequenza significa "gli apici preceduti da \" (ricordiamo che le backslash devono essere a loro volta precedute da backslash)
)        # chiudiamo il gruppo e diciamo di cercare la sequenza più lunga possibile
'        # infine, la stringa deve finire con un apice.

Adesso dovrebbe risultare tutto chiaro.

Nota: in termini computazionali, i lookarounds sono piuttosto dispendiosi. Quello che fanno, in effetti, è andare ad esplorare le parti precedenti o successive al punto raggiunto e verificare una condizione in più, e poi tornare indietro. Conoscendo meglio il modo in cui funzionano le RE, però, ci si rende conto che molto spesso se ne può fare a meno. Se avessimo usato la RE '(?:[^']|\\')*' ci saremmo accorti che non avrebbe funzionato ma, semplicemente cambiando l'ordine dall'alternanza, ci si accorge che '(?:\\'|[^'])*' invece va bene. Dal punto di vista logico questo può lasciarci confusi, perché dovrebbe essere un or e quindi una sorta di operatore simmetrico. Qual è la differenza?
Il fatto è che nel primo caso il motore RE dapprima cerca tutti i caratteri che non siano degli apici: nella stringa 'un\'automobile', quindi, trova "u", poi trova "n", poi trova "\" ed infine trova l'apice. A questo punto il gruppo [^'] non va bene e allora prova con l'altro, cioè \\': ma anche questo non va bene. Dunque, il motore conclude che il gruppo (?:[^']|\\') non va più bene, quindi torna indietro di un carattere e verifica se il carattere dopo è un apice... ed in effetti lo è. Quindi produce solo 'un\' come risultato.
Nell'altro caso, invece, il motore RE cerca per prima cosa se siamo di fronte ad una sequenza \', e poi se è un qualsiasi carattere che non sia un apice. Quindi, dopo aver passato il primo apice, non trova "\'" ma trova "u"; poi non trova ancora "\'" ma trova "n"; infine trova "\'"! Di conseguenza la ricerca non si blocca e può andare avanti, trovando correttamente tutta la stringa 'un\'automobile'.
Quindi, il consiglio generale è: usando le alternanze, mettere sempre per primi i gruppi più lunghi, o si rischia che il motore RE si blocchi anzitempo.

Trucco: i lookahead, come detto, sono utili per trovare gruppi seguiti da un altro gruppo specifico, senza che questo venga incluso nel risultato. Ad esempio, se volessimo cercare un tag di chiusura HTML, potremmo cercare i simboli < che siano seguiti dalla /, dal nome del tag e poi da >. Una RE tipo <(?=/div>) farebbe a caso nostro. Come visto, in questi casi il lookahead va messo dopo il simbolo '<'.
È utile far notare che i lookahead, però, possono messere anche prima di un certo gruppo. In effetti, i lookaround non sono per forza legati ad un gruppo di riferimento: semplicemente dicono al motore delle RE di effettuare una verifica, in avanti o indietro. Cosa vuol dire, quindi, mettere un lookahead prima di un gruppo? In sostanza, signfica verificare che ciò che segue soddisfi la condizione specificata. Ad esempio, la RE \b(?=\w{10}\b)\w*ente\b va a cercare tutte le parole che finiscono in "ente", dopo però aver verificato che fossero lunghe 10 caratteri (sì, lo so, \b\w{6}ente\b avrebbe prodotto lo stesso risultato, ma era un esempio).
Si noti che i lookahead usati in questo modo possono anche essere più di uno, da usare in una sorta di and logico.

Quantificatori avidi, svogliati e possessivi
Supponiamo di avere una stringa come

"12,$4,25a,2 4,65=,3pippo"

e di voler isolare i singoli valori separati da virgole. I valori possono essere numeri, ma anche lettere o altri simboli, in un totale che sarebbe dispendioso contenere in una classe [...]. A questo punto, usiamo il carattere universale . (il punto) e procediamo con la semplice RE (.*), ottenendo come risultato "12,$4,25a,2 4,65=,". Cos'è successo? Semplicemente, il motore RE, non appena ha trovato la prima virgola, non ha pensato che fosse la fine di quel che stavamo cercando, ma invece l'ha considerata un carattere qualsiasi (quindi presa dal .) ed ha proseguito. Dunque è giunto fino in fondo alla stringa, è dovuto tornare indietro di un carattere, verificare che dopo ci fosse una virgola e fallendo, quindi di nuovo tornare indietro di un carattere e così via, per 7 volte, finché non ha infine trovato una virgola. Ecco spiegato il risultato finale.
Il fatto è che il quantificatore * è "avido" (greedy), e tende ad andare avanti a ripetere il gruppo finché gli è possibile. Tuttavia, ci sono modi per differire questo comportamento. Il primo di questo è rendere il quantificatore "svogliato" (lazy), tramite l'aggiunta di un punto interrogativo immediatamente dopo: l'espressione, quindi, diventerà (.*?), e funzionerà proprio al caso nostro.
Un quantificatore lazy fa agire il motore in maniera diversa: esso andrà avanti per il numero minimo di ripetizioni necessarie per non interrompersi. Nell'esempio, quindi, si è detto dapprima detto "cerca le sequenze qualsiasi seguite e fermati quando dopo c'è una virgola", mentre dopo "cerca le sequenze qualsiasi e fermati alla prima virgola trovata". Dunque, il motore dapprima verificherà che ci sia una virgola (fallendo), quindi troverà '1' e verificherà di nuovo la presenza di una virgola (fallendo di nuovo), poi troverà '2' e finalmente la virgola: la stringa di match sarà dunque "12," ed il gruppo catturato "12", proprio come volevamo.

Infine, c'è un altro tipo di quantificatore: quello possessivo (possessive), che si ottiene ponendo un '+' dopo il quantificatore. La sua filosofia si può riassumere in: o tutto, o niente!
I quantificatori possessivi sono simili a quelli avidi, ma c'è una sottile differenza che li rende sia potenzialmente molto più efficienti, sia più difficili da usare correttamente. Operativamente parlando, i quantificatori avidi tengono memoria di "dove sono stati", pronti a ritornarvi in caso di fallimento. Nel caso visto (.*), si è notato che il motore ha dovuto fare il backtracking di ben 7 caratteri prima di ottenere un risultato positivo. Il fenomeno può diventare poco gestibile nel caso di stringhe molto più lunghe.
I quantificatori possessivi, invece, non tengono conto delle posizioni precedenti e dunque non effettuano backtracking in caso di fallimento. Cosa succede, dunque? Semplice: vanno avanti con la stringa, ignorando completamente il pezzo preso in esame.
Vediamo come questo si traduce al lato pratico. La potenzialità dei quantificatori possessivi esce tutta quando il motore RE fallisce la corrispondenza. Supponiamo di avere una stringa che assomiglia ad un XML, tipo

"<persona><nome>Pippo</nome><eta>anni<100</eta></persona>",

e di volerne isolare i singoli tag. La nostra RE potrebbe essere <[^<>]*>: in questo caso troverebbe, nell'ordine, "<persona>", "<nome>", "</nome>", "<eta>", "</eta>" e "</persona>". Tutto bene? Sembra di sì. Un problema, però, si presenta quando il motore RE arriva a quel "<100", dove trova un altro '<' (quello di "</eta>") prima di trovare un '>': in questo caso, il motore ritorna indietro di uno, poi di due, infine di tre caratteri, ogni volta verificando che dopo venga un '>' e sempre fallendo, per poi rinunciare del tutto e proseguire nell'analisi della stringa. Un sacco di calcoli per qualcosa che, in fondo, era già ben evidente...
Un quantificatore possessivo, invece, appena nota che dopo il "100" c'è un altro '<', rinuncia da subito e riprende l'analisi direttamente da "</eta>". I risultati sono uguali, ma le performance sono nettamente diverse. I veri miglioramenti, a direi il vero, si ottengono soprattutto nel caso di raggruppamenti nidificati, in cui i backtracking possono essere numerosi e potrebbero inficiare molto le prestazioni.

Nota: alcuni motori RE si accorgono quando un gruppo sottoposto a quantificatore ed i caratteri successivi sono mutualmente esclusivi, rinunciando da subito al backtracking e di fatto rendendo automaticamente possessivi i quantificatori. Questo, ad esempio, è il caso del framework .NET. L'assenza di quantificatori possessivi, quindi, potrebbe essere benissimo una scelta voluta per non includere una caratteristica inutile.

Gruppi atomici
Un altro metodo per ottimizzare le RE è quello di usare i gruppi atomici. Tali gruppi vengono racchiusi entro il costrutto (?>...) e, al pari di (?:...) e dei lookarounds, non costituiscono un gruppo di cattura. Si usano solitamente in congiunzione a quantificatori ed alternanze, ed hanno un comportamento che per certi versi ricorda i quantificatori possessivi, nel senso che in caso di fallimento i gruppi atomici non effettuano backtracking. L'esempio per cui sono usati più spesso è quello della ricerca delle parole. Si supponga che si vogliano cercare le parole "atono", "atomi" e "atomica" in un testo: la RE \b(atomica|atomi|atono)\b farebbe al caso nostro (è una RE un po' scema, ma ricordiamoci che le RE si possono anche generare, e non è facile creare un algoritmo che generi RE veramente "intelligenti"). Se nella stringa s'incontra una delle tre parole, va tutto bene; se tuttavia si incontra una parola tipo "atomicamente", il motore RE prima troverà che "atomica" va bene ma poi non c'è la fine della parola, quindi tornerà indietro e proverà prima "atomi" e poi "atono", fallendo in entrambi i casi.
Se avessimo usato un gruppo atomico, una volta che si è visto che "atomica" poteva andare bene ma che poi non c'è la fine della parola, il motore RE non avrebbe provato le altre due alternative e sarebbe andato avanti. Il vantaggio è un sacco di tempo e calcoli risparmiati.

Nota: bisogna fare attenzione con i gruppi atomici. Se al posto di*\b(?>atomica|atomi|atono)\b avessimo usato \b(?>atomi|atomica|atono)\b, pur essendo la parola "atomica" nel nostro testo non sarebbe stata trovata la corrispondenza. Questo perché la RE avrebbe prima trovato che "atomi" poteva starci, ma poi non avrebbe trovato la fine della parola e dunque non avrebbe provato le altre due alternative, tra cui c'era proprio la parola "atomica".

Performance catastrofiche
Ora vediamo in che senso un'espressione regolare può avere performance davvero disastrose. I veri problemi cominciano quando si fa uso di quantificatori non limitati superiormente (come *, + e {n,}). Supponiamo di* cercare una sequenza di lettere maiuscole seguita da almeno una cifra. La RE \b([A-Z]+\d+)\b fa il lavoro che ci serve. In effetti, una riga di testo come "AS400" viene elaborata senza rallentamenti. I veri problemi cominciano, come sempre, quando le corrispondenze falliscono: in questi casi, è possibile che si scatenino una serie di backtracking che aumentano esponenzialmente con la lunghezza della stringa. Se ad esempio la stringa fosse stata "AUTHENTICAMD", il motore RE avrebbe prima trovato tutto "AUTHENTICAMD", poi avrebbe non trovato una cifra e dunque sarebbe tornato indietro di un carattere, avrebbe riprovato a trovare una cifra e così via, eseguendo un backtracking ben 12 volte prima di accorgersi che non c'è nulla da fare.
Ma fin qui va ancora bene. Supponiamo invece la seguente situazione: abbiamo delle righe di valori separati da virgole, e noi vogliamo delle righe contenenti esattamente tre valori. Inoltre, non sappiamo come sono formati i nostri valori: in questo caso sarebbe comodo usare il carattere universale . (il punto). Ovviamente, però, l'espressione ^(.*,){3}$ (con flag multi-line) non va bene perché la sequenza .* ci "mangia" subito tutta la stringa, perché si tratta di un quantificatore avido: usiamo dunque la forma svogliata, ottenendo*^(.*?,){3}$ . Cosa succede, dunque, in caso di fallimento? Ipotizziamo ad esempio che nella riga i valori non siano tre ma quattro o più, tipo "asino,banana,cane,dattero,elefante": allora il motore RE troverà subito "asino,banana,cane," e poi si accorgerà che non c'è la fine della riga. Quindi, il punto troverà la virgola, poi cercherà la virgola (fallendo) e andando avanti, cosicché l'ultimo gruppo catturato diventerà "cane,dattero," e non più solo "cane,". Alla fine arriverà a "cane,dattero,elefante", non troverà la virgola e tornerà indietro. Sì, ma dove?
In questa tornata è stato "espanso" l'ultimo gruppo, ma a questo punto verrà espanso il secondo, che diventerà "banana,cane," ed il terzo prima "dattero," e poi non troverà la fine della riga, quindi il secondo gruppo diventa "banana,cane,dattero," e via dicendo, con una quantità di backtracking evidentemente crescente in maniera esponenziale.
Il nostro problema, in questo caso, è quel dannato punto che ci "mangia" la virgola: se avessimo usato [^,] al posto del punto, sarebbe andato tutto liscio.
Le tecniche per evitare i backtracking esponenziali sono diverse:

usare gruppi di caratteri mutualmente esclusivi quando si tratta di individuare qualcosa tra separatori. Ad esempio, "([^"]*)" può essere decisamente meglio di "(.*?)" per individuare qualcosa tra doppi apici;
fare uso di quantificatori possessivi e di gruppi atomici, se possibile;
ripensare completamente alla RE che si è creata: in questo conta molto l'esperienza.

Trucchi e funzionalità vari
Ecco varie funzionalità offerte dalle ultime caratteristiche sviluppate per le RE.

Gruppi con nomi
Abbiamo visto che i gruppi catturati vengono referenziati da sinistra a destra (in "ordine di apparizione") con un numero progressivo da 1 in poi. Tuttavia, usare i numeri per i riferimenti può confondere le idee, e sarebbe bello poter chiamare i gruppi con un loro nome.
Il Python è stato il primo linguaggio ad offrire questa funzionalità: un gruppo con nome può essere indicato con (?<...>...), dove la parte tra parentesi angolate è il nome del gruppo. Il gruppo può essere referenziato con la sintassi (?P=...) oppure con la vecchia sintassi \# (con # un numero), perché anche i gruppi con nomi ricevono un numero di assegnazione.
Il framework .NET permette i gruppi con nomi, con qualche differenza. Come sequenza, oltre a quella già vista si può usare anche (?'...'...) che è più utile con linguaggio ASP (dove si fa abbondante uso di < e >). I riferimenti si fanno con la sintassi \k<...> o \k'...' indifferentemente. Inoltre, col framework .NET è possibile assegnare lo stesso nome a più gruppi, qualora si escludano a vicenda con un'alternanza. Se, infatti, volessimo catturare la cifra che segue una "a" seguita da 0-3, oppure una "b" seguita da 4-7, possiamo scrivere a(?<cifra>[0-3])|b(?<cifra>[4-7]) senza che questo ci dia un errore di compilazione.

Commenti
Oltre alla modalità free-space, diversi motori RE supportano i commenti "in linea" delle RE. Basta includerli tra la sequenza (?# e la parentesi chiusa.
Generalmente, i linguaggi che supportano la modalità free-space supportano anche i commenti in linea, con la rilevante eccezione del Java.

Modificatori locali
Tutti gli interpreti di RE consentono di specificare le modalità, come visto nei paragrafi precedenti. Non tutti, però, consentono di applicare i modificatori solo a parte della RE. Per quelli che lo consentono, il gioco è semplice: basta indicare tra in mezzo a (?...) i modificatori che si vogliono usare, e questi verranno applicati sono a partire dalla destra della sequenza.
Come si è detto, i modificatori sono indicati dalle varie lettere: 'i' per ignore-case, 'm' per multi-line e così via. Per "spegnere" le modalità basta indicarle dopo il segno '-' (meno). Dunque, per attivare la modalità ignore-case si deve usare (?i), mentre per disattivarla ed attivare invece quella single-line si usa (?s-i).
In alternativa, anziché "accendere" e "spegnere" i modificatori, si può inserire la parte interessata dal modificatore direttamente all'interno della sequenza (?...:...), dove tra ? e : si mettono i modificatori, e tra : e ) la parte interessata.

Espressioni condizionali
Alcuni linguaggi supportano dei particolari costrutti di branching, per a seconda del risultato di un test viene applicata una parte della RE oppure un'altra. Si tratta delle espressioni condizionali, e possono esistere in varie forme.
La forma più utile a mio avviso è quella che verifica se un gruppo di cattura è andato a buon fine: ha la sintassi (?(#)...|...), dove # indica il numero della cattura, l'espressione prima del simbolo '|' è l'espressione da applicare se il gruppo # è stato catturato, mentre quello dopo è la parte da applicare se invece non è stato catturato. Ad esempio, la RE (Grande\s)(?(1)Punto|Panda) troverà corrispondenza in "Grande Punto" e in "Panda", ma non in "Grande Panda".
Un'altra forma di espressione condizionale consiste nell'usare i lookarounds: semplicemente, al posto di (#) si mette un lookaround che rappresenti il nostro test. Ad esempio, (?(?=\w{1,6}\b)\w*|.{3}) significa che si prenderanno tutte le lettere se ciò che viene dopo è una parola di 6 lettere, altrimenti si prendono i primi 3 caratteri.

Nota: i più esperti avranno notato che quest'ultima forma di espressione condizionale è quasi del tutto inutile, perché lo stesso identico effetto si può ottenere con (?:(lookaround)...|...). In effetti il significato profondo di quella sintassi sfugge anche a me, ma suppongo che ce ne sia uno...

Differenze tra i vari linguaggi
Questa tabella riassume il supporto alle varie caratteristiche delle RE presenti nei vari linguaggi e con i pacchetti più comuni.
Ne risulta alla fine che il supporto alle RE di XSLT/XPath/XQuery è molto povero, con quello di JavaScript appena migliore (ma ci si rende conto che è sufficiente per la stragrande maggioranza delle applicazioni), mentre il più completo risulta essere il framework .NET, seguito a ruota da Java e dal motore PCRE.

Links e riferimenti

RegExr: Online Regular Expression Testing Tool
Sito per testare le proprie RE. Manca delle funzionalità più avanzate, come gruppi atomici.
http://www.gskinner.com/RegExr/

Regular-Expressions.info
Un'autentica miniera d'oro di informazioni. C'è tutto quello che c'è in questa guida e molto di più. Manca solo un accenno alle RE ricorsive.
http://www.regular-expressions.info/

**********************
Il contenuto di questo post è rilasciato con licenza Creative Commons Attribution-Noncommercial-Share Alike 2.5
Creative Commons Attribution-Noncommercial-Share Alike 2.5

15-06-2010, 21:46	#2
MaxArt Senior Member Iscritto dal: Apr 2004 Città: Livorno Messaggi: 6611	Espressioni Regolari avanzate Quello che abbiamo visto finora è una guida di base, che già consente di fare parecchio con le espressioni regolari. Ma le RE possono fare ancora di più, ed inoltre si possono apprendere diversi trucchetti per migliorare le performance. Perché le basi delle RE si imparano in fretta, ma molto più ostico è creare delle RE che funzionino bene e che non uccidano le performance del nostro codice: spesso è facile creare delle RE la cui complessità è O(2^n) rispetto alla lunghezza della stringa. Immaginatevi le conseguenze... Lookarounds Supponiamo di avere una stringa al cui interno vogliamo identificare una... stringa, cioè una sequenza di caratteri racchiusa tra apici. È un caso comune se ci capita di dove fare il parsing di un codice o proto-codice, o semplicemente di un elenco di valori che possono essere anche delle stringhe delimitate da apici. Un'espressione regolare adeguata potrebbe essere '[^']'. Non è difficile da interpretare: si cerca una stringa che inizi con un apice, prosegua con una sequenza di qualsivoglia lunghezza di caratteri che non siano apici, e poi si conclude con un apice. Ma supponiamo che all'interno della stringa sia permesso inserire degli apici, purché adeguatamente preceduti da una backslash: in fondo, gli apici ci servono anche come apostrofi. Si potrebbe, infatti, avere qualcosa tipo 'un\'automobile', e la nostra RE si fermerebbe al solo 'un\'. Quello che dobbiamo fare è, allora, cercare di includere questi apici con escape, e per farlo il modo migliore sono i lookarounds, cioè delle sequenze di simboli che ci consentono di specificare da cosa dev'essere preceduta (lookbehind) o succeduta (lookahead) un gruppo perché esso venga considerato. Si noti che l'argomento dei lookaround non* viene incluso nel gruppo di ricerca, ed è questo il loro punto fondamentale. (?=...) positive lookahead. Specifica che la sequenza di caratteri dev'essere seguita dall'argomento compreso tra (?= e ). (?!...) negative lookahead. Questa volta, si specifica che non debba essere seguita dall'argomento del lookahead. (?<=...) positive lookbehind. Il gruppo verrà considerato solo se preceduto dall'argomento del lookbehind. (?<!...) negative lookbehind. Il contrario di sopra. Quello che ci serve nel nostro esempio è un positive lookbehind. Si noti che i lookahead venno specificati dopo il gruppo in esame, mentre i lookbehind prima. Dunque, la nostra espressione regolare diventa '(?:[^']\|(?<=\\)')'. Esaminiamola, in modalità free-space: Codice: ' # indica che la stringa deve iniziare con un apice (?: # dentro questo gruppo ci mettiamo i caratteri che vogliamo, cioè tutti tranne gli apici, a meno che non siano preceduti da \ [^'] # questo vuol dire "tutti i caratteri che non siano apici" \| # quest'alternanza ci serve per dire che vogliamo includere anche gli apici preceduti da \ (?<=\\)' # questa sequenza significa "gli apici preceduti da \" (ricordiamo che le backslash devono essere a loro volta precedute da backslash) ) # chiudiamo il gruppo e diciamo di cercare la sequenza più lunga possibile ' # infine, la stringa deve finire con un apice. Adesso dovrebbe risultare tutto chiaro. Nota: in termini computazionali, i lookarounds sono piuttosto dispendiosi. Quello che fanno, in effetti, è andare ad esplorare le parti precedenti o successive al punto raggiunto e verificare una condizione in più, e poi tornare indietro. Conoscendo meglio il modo in cui funzionano le RE, però, ci si rende conto che molto spesso se ne può fare a meno. Se avessimo usato la RE '(?:[^']\|\\')' ci saremmo accorti che non avrebbe funzionato ma, semplicemente cambiando l'ordine dall'alternanza, ci si accorge che '(?:\\'\|[^'])' invece va bene. Dal punto di vista logico questo può lasciarci confusi, perché dovrebbe essere un or e quindi una sorta di operatore simmetrico. Qual è la differenza? Il fatto è che nel primo caso il motore RE dapprima cerca tutti i caratteri che non siano degli apici: nella stringa 'un\'automobile', quindi, trova "u", poi trova "n", poi trova "\"* ed infine trova l'apice. A questo punto il gruppo [^'] non va bene e allora prova con l'altro, cioè \\': ma anche questo non va bene. Dunque, il motore conclude che il gruppo (?:[^']\|\\') non va più bene, quindi torna indietro di un carattere e verifica se il carattere dopo è un apice... ed in effetti lo è. Quindi produce solo 'un\' come risultato. Nell'altro caso, invece, il motore RE cerca per prima cosa se siamo di fronte ad una sequenza \', e poi se è un qualsiasi carattere che non sia un apice. Quindi, dopo aver passato il primo apice, non trova "\'" ma trova "u"; poi non trova ancora "\'" ma trova "n"; infine trova "\'"! Di conseguenza la ricerca non si blocca e può andare avanti, trovando correttamente tutta la stringa 'un\'automobile'. Quindi, il consiglio generale è: usando le alternanze, mettere sempre per primi i gruppi più lunghi, o si rischia che il motore RE si blocchi anzitempo. Trucco: i lookahead, come detto, sono utili per trovare gruppi seguiti da un altro gruppo specifico, senza che questo venga incluso nel risultato. Ad esempio, se volessimo cercare un tag di chiusura HTML, potremmo cercare i simboli < che siano seguiti dalla /, dal nome del tag e poi da >. Una RE tipo <(?=/div>) farebbe a caso nostro. Come visto, in questi casi il lookahead va messo dopo il simbolo '<'. È utile far notare che i lookahead, però, possono messere anche prima di un certo gruppo. In effetti, i lookaround non sono per forza legati ad un gruppo di riferimento: semplicemente dicono al motore delle RE di effettuare una verifica, in avanti o indietro. Cosa vuol dire, quindi, mettere un lookahead prima di un gruppo? In sostanza, signfica verificare che ciò che segue soddisfi la condizione specificata. Ad esempio, la RE \b(?=\w{10}\b)\wente\b va a cercare tutte le parole che finiscono in "ente", dopo però aver verificato che fossero lunghe 10 caratteri (sì, lo so, \b\w{6}ente\b avrebbe prodotto lo stesso risultato, ma era un esempio). Si noti che i lookahead usati in questo modo possono anche essere più di uno, da usare in una sorta di and* logico. Quantificatori avidi, svogliati e possessivi Supponiamo di avere una stringa come "12,$4,25a,2 4,65=,3pippo" e di voler isolare i singoli valori separati da virgole. I valori possono essere numeri, ma anche lettere o altri simboli, in un totale che sarebbe dispendioso contenere in una classe [...]. A questo punto, usiamo il carattere universale . (il punto) e procediamo con la semplice RE (.), ottenendo come risultato "12,$4,25a,2 4,65=,". Cos'è successo? Semplicemente, il motore RE, non appena ha trovato la prima virgola, non ha pensato che fosse la fine di quel che stavamo cercando, ma invece l'ha considerata un carattere qualsiasi (quindi presa dal .) ed ha proseguito. Dunque è giunto fino in fondo alla stringa, è dovuto tornare indietro di un carattere, verificare che dopo ci fosse una virgola e fallendo, quindi di nuovo tornare indietro di un carattere e così via, per 7 volte, finché non ha infine trovato una virgola. Ecco spiegato il risultato finale. Il fatto è che il quantificatore è "avido" (greedy), e tende ad andare avanti a ripetere il gruppo finché gli è possibile. Tuttavia, ci sono modi per differire questo comportamento. Il primo di questo è rendere il quantificatore "svogliato" (lazy), tramite l'aggiunta di un punto interrogativo immediatamente dopo: l'espressione, quindi, diventerà (.?), e funzionerà proprio al caso nostro. Un quantificatore lazy fa agire il motore in maniera diversa: esso andrà avanti per il numero minimo di ripetizioni necessarie per non interrompersi. Nell'esempio, quindi, si è detto dapprima detto "cerca le sequenze qualsiasi seguite e fermati quando dopo c'è una virgola", mentre dopo "cerca le sequenze qualsiasi e fermati alla prima* virgola trovata". Dunque, il motore dapprima verificherà che ci sia una virgola (fallendo), quindi troverà '1' e verificherà di nuovo la presenza di una virgola (fallendo di nuovo), poi troverà '2' e finalmente la virgola: la stringa di match sarà dunque "12," ed il gruppo catturato "12", proprio come volevamo. Infine, c'è un altro tipo di quantificatore: quello possessivo (possessive), che si ottiene ponendo un '+' dopo il quantificatore. La sua filosofia si può riassumere in: o tutto, o niente! I quantificatori possessivi sono simili a quelli avidi, ma c'è una sottile differenza che li rende sia potenzialmente molto più efficienti, sia più difficili da usare correttamente. Operativamente parlando, i quantificatori avidi tengono memoria di "dove sono stati", pronti a ritornarvi in caso di fallimento. Nel caso visto (.), si è notato che il motore ha dovuto fare il backtracking* di ben 7 caratteri prima di ottenere un risultato positivo. Il fenomeno può diventare poco gestibile nel caso di stringhe molto più lunghe. I quantificatori possessivi, invece, non tengono conto delle posizioni precedenti e dunque non effettuano backtracking in caso di fallimento. Cosa succede, dunque? Semplice: vanno avanti con la stringa, ignorando completamente il pezzo preso in esame. Vediamo come questo si traduce al lato pratico. La potenzialità dei quantificatori possessivi esce tutta quando il motore RE fallisce la corrispondenza. Supponiamo di avere una stringa che assomiglia ad un XML, tipo "<persona><nome>Pippo</nome><eta>anni<100</eta></persona>", e di volerne isolare i singoli tag. La nostra RE potrebbe essere <[^<>]>: in questo caso troverebbe, nell'ordine, "<persona>", "<nome>", "</nome>", "<eta>", "</eta>" e "</persona>". Tutto bene? Sembra di sì. Un problema, però, si presenta quando il motore RE arriva a quel "<100", dove trova un altro '<' (quello di "</eta>") prima di trovare un '>': in questo caso, il motore ritorna indietro di uno, poi di due, infine di tre caratteri, ogni volta verificando che dopo venga un '>' e sempre fallendo, per poi rinunciare del tutto e proseguire nell'analisi della stringa. Un sacco di calcoli per qualcosa che, in fondo, era già ben evidente... Un quantificatore possessivo, invece, appena nota che dopo il "100" c'è un altro '<', rinuncia da subito e riprende l'analisi direttamente da "</eta>". I risultati sono uguali, ma le performance sono nettamente diverse.* I veri miglioramenti, a direi il vero, si ottengono soprattutto nel caso di raggruppamenti nidificati, in cui i backtracking possono essere numerosi e potrebbero inficiare molto le prestazioni. Nota: alcuni motori RE si accorgono quando un gruppo sottoposto a quantificatore ed i caratteri successivi sono mutualmente esclusivi, rinunciando da subito al backtracking e di fatto rendendo automaticamente possessivi i quantificatori. Questo, ad esempio, è il caso del framework .NET. L'assenza di quantificatori possessivi, quindi, potrebbe essere benissimo una scelta voluta per non includere una caratteristica inutile. Gruppi atomici Un altro metodo per ottimizzare le RE è quello di usare i gruppi atomici. Tali gruppi vengono racchiusi entro il costrutto (?>...) e, al pari di (?:...) e dei lookarounds, non costituiscono un gruppo di cattura. Si usano solitamente in congiunzione a quantificatori ed alternanze, ed hanno un comportamento che per certi versi ricorda i quantificatori possessivi, nel senso che in caso di fallimento i gruppi atomici non effettuano backtracking. L'esempio per cui sono usati più spesso è quello della ricerca delle parole. Si supponga che si vogliano cercare le parole "atono", "atomi" e "atomica" in un testo: la RE \b(atomica\|atomi\|atono)\b farebbe al caso nostro (è una RE un po' scema, ma ricordiamoci che le RE si possono anche generare, e non è facile creare un algoritmo che generi RE veramente "intelligenti"). Se nella stringa s'incontra una delle tre parole, va tutto bene; se tuttavia si incontra una parola tipo "atomicamente", il motore RE prima troverà che "atomica" va bene ma poi non c'è la fine della parola, quindi tornerà indietro e proverà prima "atomi" e poi "atono", fallendo in entrambi i casi. Se avessimo usato un gruppo atomico, una volta che si è visto che "atomica" poteva andare bene ma che poi non c'è la fine della parola, il motore RE non avrebbe provato le altre due alternative e sarebbe andato avanti. Il vantaggio è un sacco di tempo e calcoli risparmiati. Nota: bisogna fare attenzione con i gruppi atomici. Se al posto di\b(?>atomica\|atomi\|atono)\b avessimo usato \b(?>atomi\|atomica\|atono)\b, pur essendo la parola "atomica" nel nostro testo non* sarebbe stata trovata la corrispondenza. Questo perché la RE avrebbe prima trovato che "atomi" poteva starci, ma poi non avrebbe trovato la fine della parola e dunque non avrebbe provato le altre due alternative, tra cui c'era proprio la parola "atomica". Performance catastrofiche Ora vediamo in che senso un'espressione regolare può avere performance davvero disastrose. I veri problemi cominciano quando si fa uso di quantificatori non limitati superiormente (come , + e {n,}). Supponiamo di cercare una sequenza di lettere maiuscole seguita da almeno una cifra. La RE \b([A-Z]+\d+)\b fa il lavoro che ci serve. In effetti, una riga di testo come "AS400" viene elaborata senza rallentamenti. I veri problemi cominciano, come sempre, quando le corrispondenze falliscono: in questi casi, è possibile che si scatenino una serie di backtracking che aumentano esponenzialmente con la lunghezza della stringa. Se ad esempio la stringa fosse stata "AUTHENTICAMD", il motore RE avrebbe prima trovato tutto "AUTHENTICAMD", poi avrebbe non trovato una cifra e dunque sarebbe tornato indietro di un carattere, avrebbe riprovato a trovare una cifra e così via, eseguendo un backtracking ben 12 volte prima di accorgersi che non c'è nulla da fare. Ma fin qui va ancora bene. Supponiamo invece la seguente situazione: abbiamo delle righe di valori separati da virgole, e noi vogliamo delle righe contenenti esattamente tre valori. Inoltre, non sappiamo come sono formati i nostri valori: in questo caso sarebbe comodo usare il carattere universale . (il punto). Ovviamente, però, l'espressione ^(.,){3}$ (con flag multi-line) non va bene perché la sequenza . ci "mangia" subito tutta la stringa, perché si tratta di un quantificatore avido: usiamo dunque la forma svogliata, ottenendo^(.?,){3}$ . Cosa succede, dunque, in caso di fallimento? Ipotizziamo ad esempio che nella riga i valori non siano tre ma quattro o più, tipo "asino,banana,cane,dattero,elefante": allora il motore RE troverà subito "asino,banana,cane," e poi si accorgerà che non c'è la fine della riga. Quindi, il punto troverà la virgola, poi cercherà la virgola (fallendo) e andando avanti, cosicché l'ultimo gruppo catturato diventerà "cane,dattero," e non più solo "cane,". Alla fine arriverà a "cane,dattero,elefante", non troverà la virgola e tornerà indietro. Sì, ma dove? In questa tornata è stato "espanso" l'ultimo gruppo, ma a questo punto verrà espanso il secondo, che diventerà "banana,cane," ed il terzo prima "dattero," e poi non troverà la fine della riga, quindi il secondo gruppo diventa "banana,cane,dattero," e via dicendo, con una quantità di backtracking evidentemente crescente in maniera esponenziale. Il nostro problema, in questo caso, è quel dannato punto che ci "mangia" la virgola: se avessimo usato [^,] al posto del punto, sarebbe andato tutto liscio. Le tecniche per evitare i backtracking esponenziali sono diverse: usare gruppi di caratteri mutualmente esclusivi quando si tratta di individuare qualcosa tra separatori. Ad esempio, "([^"])" può essere decisamente meglio di "(.?)" per individuare qualcosa tra doppi apici; fare uso di quantificatori possessivi e di gruppi atomici, se possibile; ripensare completamente alla RE che si è creata: in questo conta molto l'esperienza. Trucchi e funzionalità vari Ecco varie funzionalità offerte dalle ultime caratteristiche sviluppate per le RE. Gruppi con nomi Abbiamo visto che i gruppi catturati vengono referenziati da sinistra a destra (in "ordine di apparizione") con un numero progressivo da 1 in poi. Tuttavia, usare i numeri per i riferimenti può confondere le idee, e sarebbe bello poter chiamare i gruppi con un loro nome. Il Python è stato il primo linguaggio ad offrire questa funzionalità: un gruppo con nome può essere indicato con (?<...>...), dove la parte tra parentesi angolate è il nome del gruppo. Il gruppo può essere referenziato con la sintassi (?P=...) oppure con la vecchia sintassi \# (con # un numero), perché anche i gruppi con nomi ricevono un numero di assegnazione. Il framework .NET permette i gruppi con nomi, con qualche differenza. Come sequenza, oltre a quella già vista si può usare anche (?'...'...) che è più utile con linguaggio ASP (dove si fa abbondante uso di < e >). I riferimenti si fanno con la sintassi \k<...> o \k'...' indifferentemente. Inoltre, col framework .NET è possibile assegnare lo stesso nome a più gruppi, qualora si escludano a vicenda con un'alternanza. Se, infatti, volessimo catturare la cifra che segue una "a" seguita da 0-3, oppure una "b" seguita da 4-7, possiamo scrivere a(?<cifra>[0-3])\|b(?<cifra>[4-7]) senza che questo ci dia un errore di compilazione. Commenti Oltre alla modalità free-space, diversi motori RE supportano i commenti "in linea" delle RE. Basta includerli tra la sequenza (?# e la parentesi chiusa. Generalmente, i linguaggi che supportano la modalità free-space supportano anche i commenti in linea, con la rilevante eccezione del Java. Modificatori locali Tutti gli interpreti di RE consentono di specificare le modalità, come visto nei paragrafi precedenti. Non tutti, però, consentono di applicare i modificatori solo a parte della RE. Per quelli che lo consentono, il gioco è semplice: basta indicare tra in mezzo a (?...) i modificatori che si vogliono usare, e questi verranno applicati sono a partire dalla destra della sequenza. Come si è detto, i modificatori sono indicati dalle varie lettere: 'i' per ignore-case, 'm' per multi-line e così via. Per "spegnere" le modalità basta indicarle dopo il segno '-' (meno). Dunque, per attivare la modalità ignore-case si deve usare (?i), mentre per disattivarla ed attivare invece quella single-line si usa (?s-i). In alternativa, anziché "accendere" e "spegnere" i modificatori, si può inserire la parte interessata dal modificatore direttamente all'interno della sequenza (?...:...), dove tra ? e : si mettono i modificatori, e tra : e ) la parte interessata. Espressioni condizionali Alcuni linguaggi supportano dei particolari costrutti di branching, per a seconda del risultato di un test viene applicata una parte della RE oppure un'altra. Si tratta delle espressioni condizionali, e possono esistere in varie forme. La forma più utile a mio avviso è quella che verifica se un gruppo di cattura è andato a buon fine: ha la sintassi (?(#)...\|...), dove # indica il numero della cattura, l'espressione prima del simbolo '\|' è l'espressione da applicare se il gruppo # è stato catturato, mentre quello dopo è la parte da applicare se invece non è stato catturato. Ad esempio, la RE (Grande\s)(?(1)Punto\|Panda) troverà corrispondenza in "Grande Punto" e in "Panda", ma non in "Grande Panda". Un'altra forma di espressione condizionale consiste nell'usare i lookarounds: semplicemente, al posto di (#) si mette un lookaround che rappresenti il nostro test. Ad esempio, (?(?=\w{1,6}\b)\w\|.{3}) significa che si prenderanno tutte le lettere se ciò che viene dopo è una parola di 6 lettere, altrimenti si prendono i primi 3 caratteri. Nota: i più esperti avranno notato che quest'ultima forma di espressione condizionale è quasi del tutto inutile, perché lo stesso identico effetto si può ottenere con (?:(lookaround)...\|...). In effetti il significato profondo di quella sintassi sfugge anche a me, ma suppongo che ce ne sia uno... Differenze tra i vari linguaggi* Questa tabella riassume il supporto alle varie caratteristiche delle RE presenti nei vari linguaggi e con i pacchetti più comuni. Ne risulta alla fine che il supporto alle RE di XSLT/XPath/XQuery è molto povero, con quello di JavaScript appena migliore (ma ci si rende conto che è sufficiente per la stragrande maggioranza delle applicazioni), mentre il più completo risulta essere il framework .NET, seguito a ruota da Java e dal motore PCRE. Links e riferimenti RegExr: Online Regular Expression Testing Tool Sito per testare le proprie RE. Manca delle funzionalità più avanzate, come gruppi atomici. http://www.gskinner.com/RegExr/ Regular-Expressions.info Un'autentica miniera d'oro di informazioni. C'è tutto quello che c'è in questa guida e molto di più. Manca solo un accenno alle RE ricorsive. http://www.regular-expressions.info/ ********************** Il contenuto di questo post è rilasciato con licenza Creative Commons Attribution-Noncommercial-Share Alike 2.5 Creative Commons Attribution-Noncommercial-Share Alike 2.5 __________________ HWU Rugby Group :'( - FAQ Processori - Aurea Sectio - CogitoWeb: idee varie sviluppando nel web Ultima modifica di MaxArt : 15-06-2010 alle 21:49.