venerdì 19 dicembre 2014

L'asteroide che ucciderà questo dinosauro deve ancora arrivare (prima parte)

Disclaimer: l'articolo che segue non è un rant né l'analisi di una qualche vulnerabilità di sicurezza. Si tratta di un articolo su una delle basi teoriche che fanno da fondazione ad una marea di strumenti e di software. Se non siete interessati o avete una fobia per le lezioni che vi portate dietro dai vostri trascorsi da studenti passate oltre.
L'articolo è diviso in tre parti:
Seconda Parte
Terza Parte

Riconoscere un pattern in un testo è un'operazione piuttosto comune: si va dalla ricerca di una parola (o di parte di una parola) in pagine Web o in documenti di testo e si arriva a cose come ricerca e sostituzione di date dal formato americano (MM/GG/AAAA) al formato europeo (GG/MM/AAAA).

Di solito chi si intende di programmazione riconosce immediatamente questi compiti come tipiche operazioni da affidare alla macchina: si tratta infatti di attività tediose, altamente ripetitive e che richiedono l'applicazione pedissequa di una sequenza limitata di istruzioni. Compiti simili hanno risultati disastrosi se affidati ad un essere umano ma sono ideali per un computer.

Ed in effetti questi compiti sono stati oggetto di studio per interi decenni da parte di quel branco di matematici pigri che si chiamano informatici (o Computer Scientists in lingua inglese). Oltre a trovare metodi ottimi per la ricerca di singole parole in un testo (Algoritmo di Knuth, Morris e Pratt) gli informatici del passato hanno studiato attentamente i pattern e i modi di definirli e di riconoscerli.

Automi e Dinosauri

No, non si tratta di Transformers. Gli automi di cui discuteremo sono dei modelli teorici molto comuni in informatica ed ingegneria: gli automi a stati finiti. Sono utilizzati per modellare i processi in termini di stati e transizioni. Più propriamente tratteremo gli automi a stati finiti deterministici; chiamati così perché hanno un numero finito di stati e in ogni momento della loro esecuzione in base all'input e allo stato si avrà una ed una sola transizione verso un altro stato.

Ora che i vostri occhi hanno smesso di roteare cominciamo con la teoria pesante! :-D

Partiremo con l'analisi di un automa che, dato un testo in ingresso, stabilisce se all'interno del testo è presente una sequenza di almeno 3 'a' consecutive. Di seguito il grafico dell'automa:

Dal grafico è facile vedere come l'automa procede nel suo compito: si comincia dallo stato START e si legge un carattere, in base al carattere letto si decide quale transizione seguire. Se si arriva nello stato OK si interrompe la computazione e si comunica il successo, se si esaurisce il testo di input senza essere arrivati allo stato OK l'input non contiene nessuna sequenza di (almeno) tre a.

Nel gergo degli informatici diciamo che ad ogni transizione consumiamo un carattere per indicare il fatto che, dopo ogni passaggio di stato, l'automa legga il carattere successivo del suo input.

Scrivere un programma che legga dallo standard input e stampi "OK" se c'è una sequenza di 3 o più a è un tipico esercizio che viene dato ai principianti di un linguaggio di programmazione. Avendo presente il grafico di prima l'esercizio diventa veramente semplice dal punto di vista concettuale: praticamente il programma È il grafico, si tratta solo di riportarlo in una sequenza di istruzioni comprensibili dalla macchina.

Da quanto scritto poc'anzi si deduce che esiste una nave portacontainer piena di applicazioni che cercano in un testo la sequenza "aaa". Una queste applicazioni è anche uno dei miei strumenti preferiti della shell UNIX: grep.

grep è uno dei dinosauri di UNIX che si rifiutano di estinguersi. Nasce come modalità di ricerca di ex (General Regular Expression Print) ma è stato poi scorporato ed è diventato un tool fondamentale nelle mani di ogni amministratore di sistema e di chiunque debba ricercare pattern particolari in vaste collezioni di file di testo.

Espressioni Regolari

Prima di elencarvi i numerosi pregi di grep, però, devo illustrare le espressioni regolari e la loro (torbida) relazione con gli automi deterministici.

Abbiamo visto come gli automi deterministici siano in grado di riconoscere una sequenza di lettere (anche se non particolarmente interessante), ora vedremo quali siano le reali capacità dei nostri automi con un compito decisamente più complesso: riconoscere in un testo la presenza di date in formato americano (MM/GG/AAAA dove MM sono le cifre del mese, GG quelle del giorno e AAAA quelle dell'anno). Non solo! Ci divertiremo ad associare le cifre a dei gruppi e ad accettare tre tipi di separatore: la barra (/), il trattino (-) e il caro buon vecchio spazio (che eviterò di inserire tra parentesi per ragioni che hanno a che fare con il modo in cui i browser interpretano il linguaggio HTML).

Anche in questo caso partirò da un grafico:

Per brevità (e per esigenze di impaginazione) alcune transizioni sono state riunite in un'unica transizione etichettata con "m...n" dove m e n sono due numeri ed m è minore di n.

I più attenti tra di voi avranno immediatamente notato che si tratta di un automa costruito a partire da tre automi concatenati tra loro in maniera opportuna. Si tratta di una tecnica piuttosto comune e molto utilizzata: risolvere prima dei sotto-problemi e poi costruire con le soluzioni trovate una soluzione ad un problema più complesso è un tipico schema di progettazione dei software che prende il nome di Bottom-Up.

Per quanto i grafici visti fin'ora siano una rappresentazione amichevole per noi esseri umani lo sono molto meno per la macchina (oltre ad essere alquanto tediosi da disegnare per il sottoscritto). C'è un metodo più immediato per descrivere un automa a stati finiti deterministico alla macchina?

La risposta a questa domanda è: "Sì, c'è un metodo: le espressioni regolari".

Le espressioni regolari sono stringhe di testo che descrivono dei pattern usando dei caratteri speciali. Permettono di creare le stesse strutture che si possono creare con gli automi a stati finiti deterministici (c'è una dimostrazione formale che lo dice, ma sono troppo pigro per riproporvela: per cui fidatevi oppure andate ad interrogare un motore di ricerca e preparatevi psicologicamente a leggere pagine e pagine in matematichese stretto) e quindi sono interscambiabili con i grafici del tipo che vi ho fatto vedere in questo articolo.

Ad un occhio non allenato le espressioni regolari sembrano parole scritte in una lingua incomprensibile (ed in effetti lo sono), ma una volta apprese consentono di esprimere molto efficacemente tutta la gamma di pattern riconosciuti dagli automi finiti deterministici (che per brevità chiamerò DFA dalle iniziali di Deterministic Finite Automata).

Fatta eccezione per alcuni caratteri particolari (che vedremo in seguito) i caratteri di una espressione regolare corrispondono ai caratteri cercati. Per cui l'spressione regolare aaa corrisponde al primo automa che abbiamo visto in questo articolo.

Il punto (.) indica un carattere qualsiasi (lettera o numero o simbolo di punteggiatura). Per indicare il punto come un carattere a sè occorre aggiungere un backslash (\) davanti al punto. Il \ infatti indica che il carattere che segue deve essere essere considerato diversamente dal solito. La sequenza \t corrisponde al TAB, mentre \n indica l'andare a capo. La sequenza \\ viene sostituita con un singolo backslash.

Se avessimo voluto indicare una sequenza di sole tre a (non tre o più) avremmo dovuto fare uso di un quantificatore: a{3}. I numeri che compaiono tra le parentesi graffe quantificano in numero di volte in cui si deve verificare la presenza del gruppo che li precede (vedremo dopo cosa sono i gruppi).

Tramite le parentesi graffe si può anche indicare che un gruppo possa comparire un numero di volte compreso tra due numeri. Ad esempio se volessimo indicare un numero di a compreso tra due e quattro scriveremmo a{2,4}. Se il secondo numero è omesso viene considerato pari ad infinito, se viene omesso il primo allora viene considerato pari ad uno.

Esistono anche altri quantificatori:

  • + indica una o più occorrenze del gruppo che precede. Equivale a {,}.
  • * indica zero o più occorrenze del gruppo che precede. Equivale a {0,}.
  • ? indica zero od una occorrenza del gruppo che precede. Equivale a {0,1}.
Abbiamo nominato i gruppi in lungo e in largo, è giunta l'ora di definirli: un gruppo consiste in una o più sotto-espressioni regolari racchiuse da parentesi tonde. Nel caso di caratteri singoli le parentesi possono essere omesse: (a){3} equivale ad a{3}.

I gruppi separano un'espressione complessa in diverse sottoespressioni che possono essere trattate singolarmente.

Rimane un'ultimo argomento da trattare prima di provare a convertire l'automa delle date in una espressione regolare: le classi.

Una classe è un insieme di caratteri racchiusi tra due parentesi quadre. Quando si incontra una classe la si può sostituire con una qualsiasi dei caratteri che contiene. Ad esempio: [0123456789] indica tutte le cifre da 0 a 9. Per brevità le classi composte da caratteri che si susseguono in ordine possono essere definite indicando solo il primo e l'ultimo carattere separati da un -. La classe di prima perciò diventa: [0-9].

È possibile utilizzare la notazione compatta anche con classi eterogenee, ad esempio per indicare tutte le lettere maiuscole o minuscole e tutte le cifre da 0 a 9 si può scrivere: [A-Za-z0-9].

All'interno di un gruppo o di una classe è possibile che sia presente il carattere | che si può leggere come "oppure". Ad esempio una classe che indichi una a oppure una b oppure una c si può anche scrivere come [a|b|c].

Adesso armiamoci di pazienza e cominciamo a tradurre l'automa in una regex (da REGular EXpression: espressione regolare).

La prima cosa che notiamo è che dallo stato iniziale possiamo andare in tre rami mutualmente esclusivi: 0, da 2 a 9 e 1. Con il ramo centrale abbiamo già riconosciuto un mese, mentre coi due rami laterali dobbiamo passare per uno stato intermedio. inoltre il passaggio dallo stato MB allo stato MESE può avvenire anche nel caso in cui non ci sia un carattere dopo l'uno (nel grafico si è indicato il carattere nullo con la lettera greca ε). Quindi abbiamo 0 seguito da 1-9 oppure 1 seguito opzionalmente da 0-2 oppure 2-9. In regex diventa: (0[1-9]|1[0-2]?|[2-9]). Ricordatevi che una classe rappresenta UN singolo carattere che fa parte della classe stessa e che i quantificatori agiscono sul gruppo (o sul carattere) che PRECEDONO. Rileggete questo paragrafo e osservate l'espressione finché non vi sarà chiaro cosa significano tutti quei simboli e ne saprete già un bel po' sulle regex.

La transizione tra MESE e START_GIORNO è banale: [-\/\ ]. Il - è stato messo per primo così da non essere confuso con l'indicatore di range di caratteri, seguono lo slash (/) e lo spazio preceduti dal backslash per indicare che vanno interpretati letteralmente.

Il giorno si costruisce in maniera simile al mese (e ve lo lascio come esercizio) mentre l'anno si può indicare molto brevemente tramite l'uso di classi e quantificatori: [0-9]{4}.

Ci salutiamo qui per ora, ma ci sarà un seguito a questo articolo in cui vedremo altra teoria pesante, sempre che gli altri GNUrants non mi rinchiudano e non gettino via la chiave!

Seconda Parte
Terza Parte

Nessun commento:

Posta un commento