Archivi delle etichette: Regular Expression

Linguaggi regolari

Oggi si va un po’ di più sulla teoria. Oh, prima o poi toccava farlo. Qui il link al post precedente.

Linguaggi

Chi di voi conosce Noam Chomsky? Si proprio lui, avete sentito bene: il vecchio anarchico americano, uno dei pochissimi rimasti. Una persona decisamente controcorrente, sempre pronto a dire la sua fuori dal coro, dai tempi in cui si oppose alla guerra in Vietnam, fino alla guerra del golfo e la guerra in Iraq con il suo attivismo pacifista, nonostante l’età. In effetti, non deve essere facile essere come lui in un paese come gli USA.

Ma che c’entra Noam Chomsky con l’informatica e con le espressioni regolari? Moltissimo a dire la verità. Infatti, il vero mestiere di Noam Chomsky è quello del ricercatore nel campo della linguistica, e uno dei padri ispiratori della disciplina della linguistica computazionale, una disciplina al confine tra l’informatica e la linguistica classica.

In particolare, Chomsky è l’inventore del concetto di grammatica generativa e della classificazione dei linguaggi formali. Cosè un linguaggio formale?

Si parte con un alfabeto definito come un insieme di simboli (ad esempio le lettere dell’alfabeto italiano o inglese, oppure il codice ASCII). L’importante è definire appunto l’insieme dei simboli.

Una parola è una sequenza di simboli. Ad esempio, se prendiamo l’alfabeto italiano, sono parole le seguenti abc, aaaa, informatica, parola, ecc. Basta prendere una sequenza di simboli, non importa se abbia o no “senso comune”. La sequenza potrebbe anche essere illimitata, ovvero contenere un numero a priori illimitato di simboli.

A questo punto un linguaggio L è un sottoinsieme delle possibili parole. Ad esempio, potrei definire un linguaggio L1 che contiene le parole “Giuseppe” e “aaa”. Non che un linguaggio così abbia senso, ma è per farvi capire la generalità della definizione. Un altro linguaggio potrebbe essere quello dei codici di una tastiera che permettono l’apertura di una porta. Ovvero, l’esempio visto negli scorsi post. Ad esempio, il linguaggio L2 di una fantomatica porta potrebbe contenere due parole soltanto, 12A45 e 22B48.

Oppure potrei dire che il linguaggio L3 contiene parole che cominciano per il simbolo a e successivamente sono formate da un numero da zero a illimitato di sequenze della coppia ab. Per esempio, aababab è una parola del linguaggio, così come a e aab, mentre la parola aaa non lo è.

Quindi i linguaggi possono contenere un numero finito di parole, oppure infinito. Nel primo caso basta elencarle tutte. Nel secondo caso, devo dare una regola di appartenenza.

Le regole di un linguaggio

Concentriamoci sul secondo caso: vogliamo definire un linguaggio dando delle regole. Possiamo farlo in due modi: generativo, oppure riconoscitivo.

Nel caso generativo, diamo delle regole per generare tutte le parole che appartengono al linguaggio: in pratica, dato l’alfabeto iniziale e le regole, possiamo creare la lista delle parole che compongono il linguaggio. Queste regole si chiamano grammatica. Si, proprio come la vostra vecchia grammatica di italiano che portavate a scuola tutti i giorni quando eravate dei pischelli. Naturalmente, in questo contesto, grammatica significa in realtà algoritmo o procedura per generare un elenco di parole.

Nel caso riconoscitivo, vogliamo risolvere in problema leggermente diverso: data una parola, vogliamo sapere se questa fa parte di un linguaggio. Naturalmente, ogni linguaggio avrà le sue regole. Salta fuori che un cosa come gli automi che abbiamo visto negli scorsi post sarebbero adatti ad implementare dei riconoscitori.

I due metodi sono uno il duale dell’altro: in particolare, una strategia per riconoscere se una data parola w appartiene o no al linguaggio potrebbe essere la seguente:

  • generare la lista di tutte le parole del linguaggio che hanno la stessa lunghezza di w;
  • vedere se w è presente nella lista.

Viceversa, se vogliamo generare tutte le parole di un linguaggio, si potrebbe:

  • generare tutte le possibili parole di lunghezza 1, 2, 3, … n,
  • e vedere quali di queste sono riconosciute dal riconoscitore.

E quindi, grammatica o riconoscitore, per noi pari sono. Più o meno.

Potenza espressiva

Ma non tutti i linguaggi sono ugualmente “facili”. In particolare, certi linguaggi sono più “semplici” e altri sono più difficili. Chomsky classificò i linguaggi in varie categorie, a seconda del tipo di algoritmo per generare/riconoscere il linguaggio. Ecco la tabella dal più “semplice” al più “complesso”.

Tipo Linguaggio Tipo di Automa
3 Linguaggi regolari Automi a stati finiti
2 Linguaggi liberi dal contesto Automi a pila
1 Linguaggi dipendenti dal contesto Automi lineari
0 Ricorsivo Decisore / Macchina di Turing

Avete visto cosa c’è in alto a destra? I nostri amici automi a stati finiti! Si, gli automi sono in grado di riconoscere la categoria di linguaggi più semplice che c’è. Invece nella casella in basso a destra c’è la famosa Macchina di Turing, la macchina calcolatrice più espressiva di tutte. Quindi, i linguaggi ricorsivi sono i più “difficili” di tutti.

Esempio

A questo punto bisogna fare un esempio. Prendiamo il linguaggio che avevo definito prima: una parola appartiene al linguaggio se c’è una a come primo simbolo seguita da una sequenza di un numero qualsiasi (anche 0) di coppie ab. Ecco l’automa che riconosce le parole di questo linguaggio:

automa-linguaggio.png

Figure 1: Automa a stati finiti per il linguaggio dell’esempio

Nel disegnare la figura, ho fatto l’assunzione che se uno stato riceve un simbolo per cui non ha un arco in uscita, allora si blocca con errore. Per esempio, se mentre siamo in S0 arriva una b, allora l’automa si blocca con un errore. In realtà avrei dovuto mettere un stato apposito, per esempio ERR in cui si finisce quando arriva un simbolo inaspettato, e aggiungere degli archi da ciascuno stato allo stato di errore. Ma il disegno si complica inutilmente, e allora molto spesso si utilizza questa scorciatoia.

L’automa in figura definisce il linguaggio in maniera esatta. Cioè, invece di scrivere la definizione del linguaggio a parole, descrivo l’automa, che sicuramente è più preciso di qualunque descrizione in italiano. In effetti, l’automa è un modo procedurale di definire il linguaggio.

E se volessi utilizzare una grammatica? Si scrive più o meno così:

\displaystyle  a(ab)^n

dove l’elevazione a n indica la ripetizione per un numero intero di volte dei simboli contenuti tra le parentesi tonde. Sembra quasi uguale a un’espressione regolare, vero? L’espressione sarebbe:

a(ab)*

dove l’asterisco significa “il precedente pattern può essere ripetuto un numero arbitrario di volte (anche zero volte)”.

Notate che il pattern è illimitato. In altre parole, non abbiamo messo un limite alla lunghezza delle parole del linguaggio. Il nostro linguaggio L contiene dunque un numero infinito di parole! Tuttavia, poiché il pattern con cui queste parole sono generate è molto semplice, altrettanto semplici sono la grammatica e l’automa che lo descrivono.

Quindi, la difficoltà di un linguaggio non ha niente a che vedere con il numero di parole che contiene, ma semmai con la complessità del pattern di riconoscimento. Nell’ultima puntata spiegherò perché un automa a stati finiti non è poi così potente, e cosa non può riconoscere.

Errata Corrige

Nello scorso post ho fatto un errore: nella figura ho messo una freccia da da S3 a S2 con etichetta “2”; in realtà, la freccia doveva essere da S3 a S4, sempre con etichetta “2”. Grazie a Stefano per la segnalazione, è molto gratificante avere lettori attenti che ti trovano i bachi! Grazie ancora.

Espressioni regolari in Perl

Il mio primo messaggio 🙂

Ciao a tutti!
Per questo mio primo messaggio su questo blog (grazie mille per l’ospitalità) vi parlerò di espressioni regolari in Perl, ma non fatevi prendere dal panico (altrimenti sarò io a farlo…).

Espressioni regolari

Una definizione intuitiva di espressione regolare

Immaginiamo un file di testo come una serie di porte con serrature corrispondenti ad una qualsiasi sequenza dei suoi caratteri. Se per esempio il testo è ‘Casa dolce casa’ la chiave ‘dolce’ aprirà una porta sola ma la chiave ‘asa’ ne aprirà due, una presente nella prima parola ed una nella terza.

L’espressione regolare non è altro che un modo per generare chiavi da provare sul testo e quando una porta si apre possiamo fare sostanzialmente due cose:
* prendere atto che la chiave ha funzionato (come accade quando si vuol validare un indirizzo di posta elettronica);
* oppure se la chiave ha funzionato possiamo voler manipolare il testo (come accade quando si sostituisce una parola con un’altra).

L’utilità delle espressioni regolari sta nel fatto che con esse possiamo generare chiavi anche molto sofisticate in modo semplice ed essenziale: basta scrivere la giusta sequenza di caratteri criptici… 🙂

Come sperimentare?

Il linguaggio Perl è stato progettato per essere un potente strumento per modificare il testo ed è quindi naturale che disponga di una potente libreria per le espressioni regolari (dette anche RegExpr o RegExp oppure ancora RE), ed è anche facilmente reperibile su moltissimi sistemi operativi compreso Windows ed ovviamente Linux e Mac OS X dove lo troveremo già installato (date il comando perl -v per constatarlo).

Se siete poco pratici della riga di comando consiglio di leggere una buona (spero) guida, essenziale nel darvi i concetti di base come per esempio la Guida Tematica alla riga di comando scaricabile liberamente dal sito del GuIT e contenente ulteriori esempi di correzione massiva del testo.

Invece, l’ottimo tutorial PerlReQuick della documentazione ufficiale di Perl vi fornirà con molta chiarezza le informazioni di base sulle espressioni regolari.

La modalità con cui useremo Perl non sarà quella di scrivere codice in uno script ma quella più semplice di digitare un comando al terminale che eseguirà operazioni di sostituzione su molti file di testo in una volta, in una forma estremamente compatta ed immediata.
Il comando avrà la seguente struttura:

$ perl <opzioni> <regexp> <file> <file> ...

Primo esempio: di città in città

Prima di tutto consiglio vivamente di fare gli esperimenti su una copia dei file originali fino a che non si è sicuri di intervenire correttamente sul testo.

La sostituzione si scrive nella forma ‘s/regexp/nuovo testo/’: il carattere iniziale s sta per string ed è obbligatorio poi, separati da caratteri slash, ci sono due campi: il primo è l’espressione regolare, la chiave che verrà provata nelle porte del testo, il secondo è il nuovo testo di sostituzione.
Immaginiamo che nel testo contenuto nel file ‘city.txt’ devono essere sostituite tutte le occorrenze della parola ‘Savona’ con ‘Genova’. Il comando Perl è questo:

$ perl -i -p -e 's/Savona/Genova/g' city.txt

Se osserviamo il formato dell’espressione regolare ci accorgiamo che il primo campo è semplicemente la sequenza dei caratteri da sostituire, poi, che è comparso un nuovo carattere non previsto in coda all’espressione: la g. Si tratta di un modificatore che sta per global ed assicura che tutte le occorrenze trovate e non solo la prima vengano sostituite.
L’opzione al comando -i (inline) dice al compilatore perl di modificare i file sovrascrivendo gli originali. Per rimediare ad eventuali errori l’unico modo è fare una copia di backup dei file e per comodità possiamo farla fare al comando stesso specificando un suffisso all’opzione inline: -ibak oppure -i.bak.
L’opzione -p processa il file con un ciclo (il testo può passare al comando per singole linee) e l’opzione -e (esegui) indica che il codice da eseguire è quello che seguirà subito dopo.

E se per caso abbiamo scritto ‘savona’ anziché ‘Savona’ cosa succede? Semplice, la chiave non gira e ci perderemo quella sostituzione.
Se vogliamo che la chiave giri per entrambe allora o aggiungiamo in coda un ulteriore modificatore i (ignore case):

$ perl -i -p -e 's/Savona/Genova/gi' city.txt

oppure cambiamo l’espressione regolare usando le classi di caratteri definite con parentesi quadre:

$ perl -i -p -e 's/[Ss]avona/Genova/g' city.txt

Ed ancora, se dobbiamo sostituire la città ‘Sestri Levante’ con ‘Imperia’ come cavarsela con gli spazi? Niente panico, se è possibile che tra ‘Sestri’ e ‘Levante’ ci sia un carattere spazio, o addirittura una tabulazione, basta usare un altro tipo di classe di caratteri: un backslash seguito da un carattere.
Fa al caso nostro \s che rappresenta uno spazio, una tabulazione od un ritorno a capo od altre spaziature.
E se temiamo che vi siano più caratteri di spaziatura tra le parole possiamo usare i quantificatori di match repetitions, per esempio + significa che il carattere che lo precede può presentarsi una o più volte.
Riassumendo il comando sarà:

$ perl -i -p -e 's/Sestri\s+Levante/Imperia/g' city.txt

Secondo esempio: cambiare data

La situazione: nella cartella ‘src’ ci sono molti file sorgenti Python di estensione ‘.py’ che contengono la data di versione 20/01/2008. Vogliamo con un unico comando modificarla in 5/11/2012. Ipotizzando che nei file le date contenute nel testo siano esclusivamente quelle di versione, un possibile comando Perl è il seguente (poiché la slash funziona da separatore dobbiamo inserirla con il carattere di escape che è il backslash quindi ‘\/’ corrisponde a ‘/’):

$ perl -p -i-bak -e 's/20\/01\/2008/5\/11\/2012/g' src/*.py

Possiamo fare di meglio generalizzando il pattern di ricerca delle date per rendere il comando indipendente dal valore attuale, con la classe ‘\d’ che corrisponde ad una cifra qualunque:

$ perl -p -i-bak -e 's/(\d{1,2})\/\d{1,2}\/\d{4}/5\/11\/2012/g' src/*.py

Abbiamo usato tra parentesi graffe una match repetition molto restrittiva: per il giorno ed il mese ricerchiamo numeri con solamente una o due cifre e per l’anno numeri solamente con quattro cifre (certo includendo anche date senza senso del tipo 0/00/0000).
A questo punto è facile modificare il formato della data in quello internazionale yyyymmdd:

$ perl -p -i-bak -e 's/(\d{1,2})\/(\d{1,2})\/(\d{4})/$3$2$1/g' src/*.py

Se inseriamo chiavi tra parentesi tonde formiamo un gruppo la cui corrispondenza sarà assegnata alle variabili $1, $2 ecc a seconda della posizione.

Esercizio: validare una data

Qual è l’espressione regolare che valida anche se non proprio rigorosamente la correttezza della data?
Suggerimento: e se utilizzassimo classi di caratteri includendo tra parentesi quadre le cifre ed il quantificatore ‘?’?

Esempio avanzato: tag html

Situazione: disponiamo di un numero elevato di file in formato html contenenti titoli racchiusi nel tag di header in questo modo:

<h3>Titolo di sezione</h3>

Tuttavia vorremmo rendere i titoli più evidenti. Dovremo quindi sostituire i tag utilizzando un livello superiore di sezione trasformando per esempio il codice precedente nel seguente dove anziché il livello 3 si usa il livello di importanza 2:

<h2>Titolo di sezione</h2>

Per utilizzare le espressioni regolari ci serve qualcosa di sofisticato perché una volta trovato un tag di apertura o di chiusura titolo, è necessario effettuare un calcolo estraendo il numero del livello attuale per diminuirlo di 1. Il testo di sosituzione è una funzione della chiave.
La strategia è la seguente: lanciare un primo comando che marchi tutti i numeri di livello e successivamente lanciare un secondo comando che esegua il calcolo.
Salviamo il file ‘test.html’ con il seguente contenuto:

<h3>Titolo di sezione livello 3</h3>
bla bla bla
<h4>Titolo di sezione livello 4</h4>
bla bla bla
<h5>Titolo di sezione livello 5</h5>
bla bla bla

Un tag di titolo html, di apertura o chiusura che sia, ha come pattern il seguente:

   <h\d> oppure <\/h\d>
   od in un unico pattern:
   <\/?h\d>

Marchiamo il numero di livello con una notazione di cui siamo sicuri non presentandosi mai nei file, per esempio racchiudere con tre caratteri chiocciola il numero di livello. Ecco il comando:

$ perl -i-bak -p -e 's/<(\/?)h(\d)>/<$1h@@@$2@@@>/g' test.html

A questo punto il più è fatto e basta dare il secondo comando che ricerca i numeri di livello precedentemente marcati, estrae il valore con un gruppo e lo sostituisce con il valore diminuito di 1:

$ perl -i-bak -p -e 's/@@@(\d)@@@/$1-1/ge' test.html

Il modificatore g cambia tutte le occorrenze, il modificatore e sta per execute e fa si che il testo sia prima valutato e poi inserito.

Ecco come appare il file dopo l’esecuzione dei comandi:

<h2>Titolo di sezione livello 3</h2>
bla bla bla
<h3>Titolo di sezione livello 4</h3>
bla bla bla
<h4>Titolo di sezione livello 5</h4>
bla bla bla

Non sono riuscito a trovare il modo di far eseguire il calcolo mescolandolo con altro testo, probabilmente perché non conosco abbastanza il Perl, perciò chi di voi trova il modo di lanciare un unico comando anziché due, vince un viaggio premio di una settimana per due persone a Juhansic Park…

Esercizio: estrarre indirizzi e-mail

Per esercizio elaborate il comando Perl per estrarre tutti gli indirizzi di posta elettronica presenti nei file di estensione ‘txt’ presenti nella directory corrente e salvarli nel file ‘email.txt’.
Se ci riuscite questa volta non vincete nulla (tempi duri per i viaggi premio), ma come consolazione potete pubblicare la soluzione nei commenti.
Suggerimenti: forse eliminando l’opzione -p e reindirizzando l’output in un file di testo…

Finale

Possiamo rilassarci adesso. Il temibile guazzabuglio di caratteri delle espressioni regolari dovrebbe fare un po’ meno paura dopo aver fatto gli esperimenti.

Rilassarsi d’accordo, ma non dimenticatevi di mandarci i vostri esempi avanzati. Potremo includerli nel post.
Grazie ed alla prossima.
Robitex