sed, un editor di flusso: Sotto-espressioni non rivolte all'indietro

Nelle ripetizioni, sia minimizzanti che massimizzanti, una mancata corrispondenza nel seguito della stringa normalmente fa sì che l’elemento ripetuto sia valutato ancora, per controllare se un numero differente di ripetizioni permette la corrispondenza col resto dell’espressione. Talora è utile evitare ciò, sia per modificare il tipo di corrispondenza, che per far terminare la ricerca prima di quel che normalmente avverrebbe, quando l’autore dell’espressione regolare sia consapevole che non val la pena di proseguire oltre.

Si consideri, per esempio, l’espressione regolare \d+foo, applicata alla stringa

Dopo aver trovato una corrispondenza con tutte e 6 le cifre, e in seguito non riuscendo a trovare la stringa ‘foo’, l’azione normale del programma sarebbe di provare ancora con la corrispondenza di solo 5 cifre, poi di 4, e così via, prima di concludere che non c’è alcuna corrispondenza. Le sotto-espressioni regolari non rivolte all’indietro consentono di specificare che una volta che una porzione dell’espressione regolare è stata trovata, non deve essere nuovamente ricalcolata come descritto sopra, in modo che il programma possa concludere che non c’è corrispondenza, subito dopo non essere riuscito a trovare ‘foo’ la prima volta. La notazione è un altro tipo di parentesi speciale, che inizia con (?>, come in questo esempio:

Questo tipo di parentesi “blocca” la parte dell’espressione regolare in essa contenuta, una volta che sia stata trovata una corrispondenza, e se non si riesce a trovare alcuna corrispondenza in seguito, il programma non effettua altri tentativi all’indietro. Tornare ancora più indietro, fino all’elemento precedente [se presente] è consentito come al solito.

Le sotto-espressioni rivolte all’indietro sono sotto-espressioni non di cattura. Semplici casi come quello visto sopra possono essere visti come una ripetizione massimizzata che deve “inghiottire” il massimo possibile. Così, mentre sia \d+ che \d+? procedono a nidificare il numero di cifre che a loro corrisponde, per cercare una corrispondenza nel resto dell’espressione regolare, (?>\d+) può solo corrispondere a una sequenza intera di cifre.

Questa costruzione può, naturalmente, contenere sotto-espressioni complesse a piacere, e può essere nidificata.

Le sotto-espressioni non rivolte all’indietro possono essere usate insieme a dichiarazioni rivolte all’indietro per specificare corrispondenze in maniera efficiente, che si trovino alla fine della stringa in esame. Si consideri una semplice espressione regolare come

quando venga applicata a una lunga stringa senza che vengano trovate corrispondenze. Poiché il processo di ricerca procede da sinistra verso destra, sed cercherà ogni ‘a’ nella stringa in esame, e quindi controllerà se quel che segue corrisponde al resto dell’espressione regolare. Se l’espressione regolare è specificata come

l’espressione iniziale .* trova come corrispondenza l’intera stringa da esaminare, ma quando il confronto non riesce (perché non c’è alcuna ‘a’ dopo la fine della stringa), il programma torna indietro e prova la corrispondenza di tutta la stringa tranne l’ultimo carattere, quindi tutta la stringa tranne gli ultimi due caratteri, e così via. Ancora una volta, la ricerca di ‘a’ ripercorre l’intera stringa, da destra a sinistra, e quindi la situazione equivale a quella vista più sopra, senza alcun miglioramento. Invece, se l’espressione regolare è scritta come

non può esserci un ritorno indietro per l’elemento .*; può solo corrispondere all’intera stringa. La successiva dichiarazione rivolta all’indietro effettua un solo test sugli ultimi quattro caratteri. Se questo non va a buon fine, la ricerca termina immediatamente. Per stringhe lunghe, questo approccio permette un notevole risparmio nel tempo di esecuzione.

Quando un’espressione regolare contiene una ripetizione illimitata all’interno di una sotto-espressione che pure può essere ripetuta un numero illimitato di volte, l’uso di una sotto-espressione "con una sola scansione" è la sola maniera per evitare alcune mancate corrispondenze che finirebbero per richiedere un tempo di esecuzione molto lungo.¹⁵

corrisponde a un numero illimitato di sotto-stringhe che consistono in caratteri diversi dalle cifre, o in cifre racchiuse fra parentesi angolari [ <> ] seguite da un punto esclamativo o da un punto interrogativo. Quando c’è una corrispondenza, il tempo di esecuzione è minimo. Però, se applicata alla stringa

è necessario molto più tempo prima di concludere che non ci sono corrispondenze. Questo avviene perché la stringa può essere divisa fra le due ripetizioni in un numero elevato di modi, e ognuno di essi deve essere controllato.¹⁶

le sequenze di caratteri diversi dalle cifre non possono essere suddivise e il responso negativo è presto raggiunto.

Note a piè di pagina

(15)

In realtà, il programma usato all’interno di GNU sed tenta di far qualcosa per gestire i casi più semplici, come ([^b]*b)*. Questi casi sono in realtà abbastanza frequenti: sono per esempio presenti in un’espressione regolare come \/\*([^*]*\*)*\/ che serve per trovare i commenti nei programmi C.

(16)

L’esempio usa [!?] piuttosto che un solo carattere alla fine perché sia GNU sed che Perl hanno un’ottimizzazione che permette di arrivare velocemente a un risultato negativo, quando si usa un solo carattere. Si tiene in memoria l’ultimo carattere richiesto per una corrispondenza, e viene dato un risultato negativo se non è presente nella stringa.

B.9 Sotto-espressioni non rivolte all’indietro

Note a piè di pagina

(15)

(16)