Con questo articolo si vuole mostrare una semplice procedura per la realizzazione di un analizzatore di frequenza delle lettere, attraverso FLEX.
In pratica quello che si vuole ottenere è un software in grado di leggere un file testuale e di contare tutti i caratteri dalla a alla z valutandone la loro frequenza. Esistono tanti modi per creare questo applicatico, uno dei tanti è il classico hand-coded, dove si descrivono le direttive per la lettura di tutti i caratteri fino all’EOF e effettuando così gli opportuni calcoli. Un ulteriore metodo è quello di usare il tool flex, che permette di velocizzare l’implementazione.
FLEX è un noto generatore di scanner, fu sviluppato M. E. Lesk and E. Schmidt degli AT&T Bell Laboratories e costruisce uno scanner in C, da un insieme di espressioni regolari che definiscono i token.
Flex a volte viene combinato con un altro strumento automatico ovvero il BISON, permettendo così di costruire un compilatore. Tuttavia, per gli obiettivi prefissati, si farà soltanto uso di flex.
L’applicativo finale, sarà il compilato da parte di flex che si basa su un file avente estensione *.l (nel nostro caso scanner.l). Il file scanner.l ha un suo formato particolare costituito da tre sezioni, separate dal simbolo %%. Tuttavia questo file altro non è che un collettore di espressioni regolari che riconoscono il testo, ed è in grado di intraprendere delle azioni. Al termine della scrittura del suddetto scanner.l, esso dovrà essere compilato con il tool Flex che genererà una macchina a stati finiti deterministica, in grado di comportarsi come riconoscitore di espressioni regolari.
Nella prima sezione ci sono le definizioni di costanti e macro personalizzate oltre alle espressioni regolari. Le definizioni e le macro sono le seguenti:
%{#include “mystruct.h”#include <stdio.h>#include <stdlib.h>#include <string.h>int intero;struct vect a[26];%}
dove si richiamano librerie standard, la libreria mystruct.h (descritta in seguito) e due variabili, tra cui la struttura dati di 26 elementi che conterrà i valori dei caratteri riconosciuti. Invece, le espressioni regolari sono le seguenti.
NUMBER [0-9]STRING [a-zA-Z]
mentre le azioni da intreprendere (presenti nella seconda sezione) sono quelle di caricare la struttura dati a ( struct vect{ unsigned char value; int elem; float percent; }; ) :
/*Definizioni delle azioni*/{STRING}{intero = *(int *)strdup(yytext);intero -=65;if(intero>=32){intero -=32;}a[intero].elem++;printf(“%s”,yytext);}{NUMBER}+{intero=atoi(yytext);printf(“%s”,yytext);}.{printf(“%s”,yytext);};//qualsiasi carattere!
Quando viene riscontrato un carattere, esso viene riconosciuto attraverso l’espressione regolare STRING e come azione gli si preleva l’indice ASCII per normalizzarlo ed usarlo come indice della struttura dati. Nel caso in cui venisse riscontrato un numero o qualsiasi altro carattere non ci sono particolari azioni intraprese.
Nella terza ed ultima sezione ci sono tutte le funzioni in C per il funzionamento dell’applicativo:
int main(int argc,char **argv){–argc;++argv;int i,value,j;value= 0;for ( i = 0; i < argc; i++){yyin = fopen( argv[i] , “r” );if(yyin!=NULL){inizialize(&a);printf(“+———————–START SCANNING———————–+n”);yylex();printf(“+————————END SCANNING————————+n”);printf(“Calculating…n”);calculate(&a);print(&a);}}return 1;}
L’unica funzione in questo caso è il main che legge i valori passati (argc, argv) e quindi i path dei file, apre un puntatore ai suddetti file e chiama la yylex() che preleva e analizza il testo.
Al termine della fase di scanning vengono chiamate le funzioni calculate() e print() definite ambedue in mystruct.h che ricevono in ingresso la struttura caricata e rispettivamente effettuano il calcolo percentuale dei caratteri e la stampa.
Per compilare il file scanner.l è necessario aprire il terminale, dirigersi nella directory e lanciare i comandi:
flex scanner.lgcc lex.yy.c -o out -lfl
Il file out è un eseguibile, che prelevando il file in input si comporta come analizzatore in frequenza. Per far questo (permettetemi la banalità):
./out prova.txt
TEST
Come caso di test ho scritto un file prova.txt e eseguendo l’applicazione su tale file, si ottengono i seguenti risultati:
+———————–START SCANNING———————–+[John]: Non importa quanto scappi lontano, ci sono demoni a cui non puoi sfuggire. Mi chiamo Johnny Blaze, mi guadagnavo da vivere in sella ad una moto, una volta ho fatto un triplo salto mortale a chiappe scoperte davanti a 22 mila persone, una cosetta divertente, è su YouTube, cercatela! Ma quando mio padre si è ammalato, ho fatto una cosa ancora più folle.[Roarke]: Sembra che tu abbia bisogno di aiuto. Sei disposto a firmare un patto, John?[John]: Si esattamente, io sono il genio che ha firmato un patto con il diavolo. So bene a cosa state pensando! ma non ha mai visto un film? C’è mai stata una volta che è finita bene? Diciamo che all’epoca la mia capacità di giudizio non era il mio forte, da allora sono posseduto da un antico demone, in presenza del male mi trasformo, divento un mostro, i cattivi sono le mie prede, io risucchio la loro anima e non vorreste essere li quando succede. C’è bene e male in ognuno di noi, forse non avete ucciso nessuno ma avete comunque fatto qualcosa che il Rider non dovrebbe vedere. Una piccola bugia, un download illegale. Cosa hai fatto tu? Ho cercato di fermarla, di tenerla a freno, ma l’oscurità che è dentro di me è diventato solo più forte. Per questo sono dovuto scappare all’altro capo del mondo, e continuo a scappare.+————————END SCANNING————————+Calculating…Total char counted = 988+—-+——+————-+| CH | elem | %+—-+——+————-+| a | 118 | 11.943320%+—-+——+————-+| b | 12 | 1.214575%+—-+——+————-+| c | 45 | 4.554656%+—-+——+————-+| d | 38 | 3.846154%+—-+——+————-+| e | 98 | 9.919028%+—-+——+————-+| f | 16 | 1.619433%+—-+——+————-+| g | 10 | 1.012146%+—-+——+————-+| h | 19 | 1.923077%+—-+——+————-+| i | 80 | 8.097166%+—-+——+————-+| j | 4 | 0.404858%+—-+——+————-+| k | 1 | 0.101215%+—-+——+————-+| l | 46 | 4.655870%+—-+——+————-+| m | 37 | 3.744939%+—-+——+————-+| n | 80 | 8.097166%+—-+——+————-+| o | 122 | 12.348178%+—-+——+————-+| p | 28 | 2.834008%+—-+——+————-+| q | 6 | 0.607287%+—-+——+————-+| r | 47 | 4.757085%+—-+——+————-+| s | 49 | 4.959514%+—-+——+————-+| t | 67 | 6.781376%+—-+——+————-+| u | 41 | 4.149797%+—-+——+————-+| v | 18 | 1.821862%+—-+——+————-+| w | 1 | 0.101215%+—-+——+————-+| x | 0 | 0.000000%+—-+——+————-+| y | 2 | 0.202429%+—-+——+————-+| z | 3 | 0.303644%+—-+——+————-+
DOWNLOADS:
Di seguito trovate il repository GitHub dove è possibile scaricare il codice:
Questo applicativo è stato interamente sviluppato da me per la preparazione all’esame di Linguaggi Formali e Compilatori presso il Politecnico di Bari
