B.11 Espressioni regolari ricorsive

Si consideri il problema di trovare una stringa racchiusa fra parentesi, permettendo un numero illimitato di parentesi nidificate. Senza far uso della ricorsione, il meglio che si può fare è di usare un’espressione regolare che controlli un numero limitato di parentesi nidificate. Non è possibile gestire una profondità di nidificazione arbitraria. Perl 5.6 contiene del codice sperimentale che permette (tra l’altro) la ricorsione di espressioni regolari. Ciò si realizza modificando il codice Perl nell’espressione in fase di esecuzione, e il codice può fare riferimento all’espressione stessa. Un’espressione regolare Perl per risolvere il problema delle parentesi può essere creata come mostrato qui sotto:

$re = qr{\( (?: (?>[^()]+) | (?p{$re}) )* \)}x;

L’elemento (?p{...}) modifica il codice Perl al momento dell’esecuzione, e in questo caso fa un riferimento ricorsivo all’espressione regolare in cui appare. Ovviamente sed non può supportare la modifica dinamica di codice Perl. In alternativa, lo speciale elemento (?R) viene reso disponibile per il caso specifico della ricorsione. Quest’espressione regolare risolve il problema delle parentesi (si supponga che l’opzione modificatrice X sia in uso, in modo da ignorare gli spazi bianchi):

\( ( (?>[^()]+) | (?R) )* \)

Dapprima si cerca una parentesi aperta. Poi un numero qualsiasi di sotto-stringhe che possono essere sia una sequenza di non-parentesi, oppure una ricorrenza ricorsiva dell’espressione regolare stessa (ossia una sotto-stringa correttamente racchiusa fra parentesi). Infine si cerca una parentesi chiusa.

Questo particolare esempio di espressione regolare contiene un numero illimitato di ripetizioni nidificate, e quindi l’uso di una sotto-espressione non rivolta all’indietro è importante quando si applichi l’espressione regolare a stringhe per cui non esiste una corrispondenza. Per esempio, quando la si applica a

(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa()

una risposta “no match” [nessuna corrispondenza] viene prodotta rapidamente. Comunque, se non si usa una sotto-espressione standard rivolta all’indietro, il confronto dura sicuramente per un tempo molto lungo, perché ci sono moltissime modalità differenti in cui le ripetizioni + e * possono suddividere la stringa in esame, e ognuna di esse deve essere esaminata, prima di poter dichiarare che non esiste una corrispondenza.

I valori impostati per ogni sotto-espressione di cattura sono quelli dal livello più esterno della ricorsione in cui il valore della sotto-espressione è impostato. Se l’espressione precedente è utilizzata per esaminare la stringa

(ab(cd)ef)

il valore della parentesi di cattura è ‘ef’, che è l’ultimo valore raccolto al livello più alto.