Flex (Fast Lexical Analyzer) potente strumento utilizzato per la costruzione di analizzatori lessicali

Flex è un potente strumento utilizzato per la costruzione di analizzatori lessicali o, come si può leggere sul manuale, per la generazione di scanner.
Attraverso questi oggetti è possibile suddividere un flusso di ingresso in token, elementi base a cui sono associate specifiche operazioni predeterminate.
L'uso in combinazione con altri strumenti come bison permette di operare nel campo della generazione di compilatori o interpreti di linguaggio.
La fase di analisi lessicale, in qualunque processo essa sia inquadrata, consiste nel raggruppare insiemi di caratteri e simboli all'interno di unità lessicali dette token che sottostanno a specifiche espressioni regolari.
Lo scanner, strumento attraverso il quale questo processo viene attuato, lo si può immaginare per adesso come una scatola nera che prende come ingresso un flusso di dati e restituisce in uscita un flusso di token generati a partire dagli elementi forniti, associando o meno ad ognuno di essi una operazione specifica.
In un primo momento la cosa può sembrare piuttosto astratta ma nel seguito sarà definito in modo chiaro il ruolo dello scanner e sarà possibile comprendere meglio il lavoro svolto da esso.
Per adesso basta pensare ad uno scanner come ad uno strumento in grado di riconoscere ed estrapolare da un flusso di dati determinati elementi noti, che è capace di riconoscere e sa come trattare correttamente.
Lo Scanner.
Lo scanner è l'elemento chiave di un analizzatore sintattico. Ad esso è demandato tutto il lavoro sopra brevemente descritto e con esso si interfacceranno eventuali oggetti esterni che intendono usare questo strumento per i loro scopi. A titolo informativo e come esempio di quanto detto, si noti che flex è spesso usato in combinazione con altri software, primo fra tutti bison, proprio per la generazione di analizzatori sintattico/lessicali.
Per quanto riguarda le modalità operative di uno scanner, questo dovrà distinguere fra diversi tipi di token ognuno descritto dalla propria espressione regolare, ma di contro potrà disinteressarsi completamente dell'ordine di comparsa dei token come anche della loro reale appartenenza ad uno specifico linguaggio.
Allo scanner, del resto, è affidato l'arduo compito di prendere una decisione laddove esistano più modi per suddividere un dato ingresso in elementi validi. Qualsiasi altro tipo di elaborazione risulta a carico delle procedure a valle, le quali potranno giovare del lavoro svolto dallo scanner risultando più semplici, snelle ed efficienti.
Non è facile chiarire le idee sul come uno scanner sia in grado di individuare specifici elementi all'interno di un flusso dati e tentando di farlo si è obbligatoriamente costretti a percorrere l'affascinante quanto (a volte) complicato mondo delle espressioni regolari.
Una buona padronanza di questo argomento non è assolutamente necessaria, ma senz'altro aiuta in modo notevole tanto la comprensione quanto la futura realizzazione di scanner per l'uso nei propri progetti. In ogni caso, le espressioni regolari sono un argomento che ogni studente di informatica oggi dovrebbe quantomeno conoscere e di seguito sarà data solo una brevissima introduzione, consigliando caldamente a chiunque di approfondire.
Espressioni Regolari
Le espressioni regolari sono un argomento molto vasto e complesso che non sarà discusso in questa sede. Ciò nonostante, è necessaria una breve introduzione che permetta di farsi un'idea sul modo in cui è possibile definire le modalità di suddivisione del flusso di ingresso in token.
Si prenda in considerazione la stringa hal9000. Questa, intuitivamente, può essere suddivisa in svariati modi, come ad esempio:
* un unico token, ovvero hal9000
* due token come ad esempio hal e 9000, ma anche hal9 e 000
* tanti token quante sono le lettere che compongono la scritta, quindi h, a, l e tutti gli altri
Quelli sopra sono solo alcuni esempi, ma in pratica si hanno svariate suddivisioni possibili fra cui scegliere. La domanda è quale scegliere. La risposta consiste nella più lunga stringa che trova corrispondenza con una delle scelte possibili. Ma quali e quante sono queste scelte possibili?
Supponiamo di voler dividere un flusso di ingresso in token rappresentanti rispettivamente stringhe di caratteri e stringhe di numeri: hal rappresenta la più lunga stringa di dati in ingresso che corrisponde ad una delle scelte possibili, così come anche 9000.
Se la suddivisione fosse invece in singoli caratteri e stringhe numeriche otterremmo quattro token, ovvero: h, a, l, 9000.
In pratica le espressioni regolari descrivono le caratteristiche di una delle possibili scelte, evidenziando la struttura dei dati che uno specifico token deve presentare per essere classificato come tale. Ovvero, esse definiscono una sintassi in grado di rappresentare un determinato insieme di stringhe a partire da un flusso di caratteri alfanumerici. Questo permette di estrapolare specifici elementi in base alle loro caratteristiche.
Espressioni Regolari e flex
flex usa un insieme esteso e abbastanza articolato di espressioni regolari e, per approfondimenti, si consiglia di fare riferimento alla documentazione ufficiale.
Alcuni esempi che saranno utili anche nel prosieguo sono riportati di seguito:
* 'x' : senza apici, corrisponde al carattere x
* '.' : senza apici, indica un qualsiasi carattere ad eccezione del carattere di nuova linea
* [abc], [^abc] e [b-o] : indicano rispettivamente uno fra i caratteri a, b e c, ogni carattere ad eccezione di a, b e c e uno dei caratteri compresi fra b e o
* [a|b] : corrisponde ad un carattere a oppure ad un carattere b, indipendentemente
* r*, r+ e r? : indicano rispettivamente un numero nullo o illimitato di caratteri r, uno o più caratteri r e infine uno o nessun carattere
Come detto, questa è solo una parte delle possibili strutture utilizzabili per la costruzione di proprie espressioni in grado di catturare elementi di testo specifici. Attraverso questi elementi di base si possono costruire espressioni più complesse e potenti, in grado di estrapolare dal flusso di dati i diversi token.
Vediamo qualche esempio:
* [a-zA-Z] : indica un qualsiasi carattere alfabetico, maiuscolo o minuscolo
* [a-z]+ : definisce una stringa di uno o più caratteri alfabetici minuscoli
* [0-9] : specifica un carattere numerico compreso fra 0 e 9
* [+|-]?[0-9]+ : rappresenta la classe dei numeri interi con o senza segno, senza limiti di cifre decimali a patto che esse siano in numero maggiore o uguale a una
* [+|-]?[0-9]*"."[0-9]+[[e|E][0-9]+]? : è una espressione più complessa ma che esprime bene le potenzialità delle espressioni regolari, la quale permette di esprimere numeri in virgola mobile con o senza segno in forma esponenziale e non
La potenza di classificazione delle espressioni regolari, a questo punto, dovrebbe essere chiara a tutti. È arrivato il momento di inquadrare quanto detto all'interno di flex e capire come questo possa servire ai nostri scopi. Ovviamente, per approfondimenti sulle espressioni regolari si consiglia di fare riferimento alla letteratura dove queste sono ampiamente discusse e trattate.
Purtroppo l'argomento è talmente vasto da richiedere non una sezione di un semplice articolo ma piuttosto una serie di articoli intera, ciò nonostante per una infarinatura di base bastano poche ricerche e tanta volontà.
flex
Dal manuale ufficiale si legge:
flex is a tool for generating scanners: programs which recognized lexical patterns in text. flex reads the given input files, or its standard input if no file names are given, for a description of a scanner to generate. The description is in the form of pairs of regular expressions and C code, called rules. flex generates as output a C source file, `lex.yy.c', which defines a routine `yylex()'. This file is compiled and linked with the `-lfl' library to produce an executable. When the executable is run, it analyzes its input for occurrences of the regular expressions. Whenever it finds one, it executes the corresponding C code.
flex è uno strumento per la generazione di scanner: programmi che riconoscono modelli lessicali nel testo. flex legge i file forniti in ingresso o lo standard input se nessun file viene indicato, per avere una descrizione dello scanner da generare. La descrizione è nella forma di coppie comprendenti una espressione regolare e codice C, chiamate regole. flex genera in uscita un file di codice sorgente C, `lex.yy.c', che definisce una funzione `yylex()'. Questo file è compilato e collegato con la libreria `-lfl' per produrre un eseguibile. Quando l'eseguibile viene lanciato, analizza il proprio ingresso in cerca di occorrenza delle espressioni regolari. Ogni volta che ne individua una, viene eseguito il corrispondente codice C.
flex è uno degli strumenti più diffusi e utilizzati per la creazione di scanner (o analizzatori lessicali) e rappresenta una soluzione open-source alternativa al più datato lex. Questo software legge un file di ingresso che definisce rigorosamente gli elementi che devono essere riconosciuti nel flusso di dati e produce un file C chiamato lex.yy.c che presenta una funzione denominata yylex(). La funzione citata può essere utilizzata da codice di contorno o direttamente da una ipotetica funzione main per il recupero dei token.
Certo, la descrizione stringata data sopra non rende fede allo strumento in analisi. Ciò nonostante, è più utile (come avviene anche nel manuale ufficiale) dirigere l'attenzione velocemente sul lato tecnico piuttosto che perdersi nei meandri della teoria, in questo caso piuttosto articolati e complessi. Questa sarà anche la linea guida di questo documento, che descriverà in maniera pratica l'uso di flex senza approfondire sulla teoria che vi sta dietro.
File e Sezioni
Il file di ingresso da dare in pasto a flex si divide in tre sezioni separate fra loro con una linea contenente solamente la coppia di caratteri %%. Le tre sezioni rappresentano rispettivamente:
* definizioni, ovvero nomi utili a semplificare le descrizioni seguenti ma anche, in realtà, opzioni e porzioni di codice utente
* regole, ovvero le leggi a cui la suddivisione del flusso in token deve sottostare
* codice utente, ovvero una sezione opzionale che riporta funzioni di supporto sviluppate dall'utente
Le sezioni sopra indicate saranno descritte più dettagliatamente in seguito. Bisogna osservare che nelle sezioni definizioni e regole tutto ciò che viene a trovarsi racchiuso fra %{ e }% è copiato direttamente nel file risultante, come sarà spiegato meglio in seguito con un esempio pratico.
Nella descrizione passo passo delle sezioni sopra citate sarà sviluppato un esempio che, alla fine, potrà essere utilizzato come scanner giocattolo per prendere maggiore familiarità con flex. In particolare, sarà sviluppato uno scanner in grado di classificare i dati in ingresso fra le classi di interi, numeri reali e stringhe di caratteri. Ovviamente una cosa molto semplice ma che possa dare al lettore un'idea di come si opera con questo strumento.
Definizioni.
Questa sezione contiene scorciatoie definite per rendere più semplice il lavoro che segue. Ogni definizione è del tipo: nome definizione.
Il nome sarà lo stesso che, in seguito, potrà essere utilizzato per riferirsi alla specifica definizione attraverso la dicitura {nome}, la quale a sua volta sarà espansa in (definizione).
Alcuni esempi di definizione sono:
* ID [a-zA-Z]+
* SIGN [-|+]
* DIGIT [0-9]
* EXP [e|E][0-9]+
In particolare, vengono definite scorciatoie per identificatori contenenti lettere maiuscole/minuscole (ovvero, in definitiva stringhe), per segni positivo e negativo, per cifre ed esponenti (questi ultimi intesi come notazione esponenziale per numeri reali).
Si memorizzi quanto sopra perché sarà ripreso a breve per implementare ed ampliare lo scanner d'esempio.
Una nota importante in merito a questa sezione che risulterà utile in seguito: tutto ciò che si trova all'interno della coppia di identificatori %{ e %} viene copiato direttamente nel file risultante senza alcuna modifica. Nell'esempio in questione, questa particolarità sarà sfruttata per includere alcuni file utili, ovvero includendo in testa alla prima sezione la linea:
%{
#include
%}
Infine questa sezione, che all'apparenza dovrebbe essere la più semplice e snella, permette fra le altre cose anche il passaggio a flex di opzioni che altrimenti sarebbero dovute essere passate attraverso la riga di comando. Questo lo si può fare attraverso la direttiva %option e le possibilità sono svariate, anche se non c'è modo e spazio di discuterle tutte.
Il fatto per cui, in realtà, l'argomento è stato introdotto è che risulta necessaria, per l'esempio proposto, la direttiva seguente:
%option noyywrap
Questa direttiva comporta che non venga chiamata la funzione yywrap() dopo che è stato raggiunto un carattere di end-of-file (fine file), ma piuttosto sia assunto che non esistano più file da analizzare. La funzione sopra citata dovrebbe, teoricamente, impostare correttamente la variabile globale yyin e ritornare il valore zero se esistono altri file da analizzare, oppure ritornare un valore non zero nel caso in cui il lavoro da compiere sia giunto al termine (e, quindi, ottenere anche la terminazione nell'esecuzione dello scanner). L'opzione di cui sopra porta al non essere obbligati nel definire la funzione yywrap che, quindi, non verrà chiamata come richiesto con le conseguenze descritte.
Regole.
La sezione in esame contiene una lista di regole nella forma: modello azione.
Nello specifico, il modello non è altro che una espressione regolare che permette di avere un riscontro con determinate stringhe di caratteri; il punto di forza di questi modelli è che possono essere resi più compatti (e a volte anche più comprensibili) richiamando in essi i nomi associati alle diverse definizioni come descritto nella sezione precedente.
Per quanto riguarda le azioni, invece, queste rappresentano molto semplicemente porzioni di codice C. In particolare, ogni porzione è associata ad uno specifico modello e solo in presenza di esso sarà eseguita integralmente. Ad esempio volendo creare uno strumento che rende maiuscole tutte le lettere che incontra, potrebbe essere definito come modello l'insieme delle lettere minuscole e come azione quella che restituisce in uscita la corrispondente lettera maiuscola, ovvero poche stringhe in codice C che convertono il codice relativo alla lettera individuata così da renderla maiuscola.
Nell'ottica di costruzione dell'esempio proposto, si possono definire alcune coppie di modello-azione come quelle che seguono, descritte singolarmente.
La prima coppia permette di estrapolare identificatori (sotto forma di stringhe contenenti caratteri maiuscoli e/o minuscoli) dal flusso in ingresso e consiste nelle righe seguenti:
{ID} { printf("IDENTIFICATORE\n"); }
La seconda coppia, invece, aiuta a riconoscere numeri interi con o senza segno:
{SIGN}?{DIGIT}+ { printf("INTERO\n"); }
Come si può notare, il segno è reso opzionale dal punto esclamativo mentre l'insieme di cifre deve contenere uno o più elementi per essere considerato tale (questo lo si indica attraverso il simbolo +). In questa forma compatta si riesce a catturare un insieme teoricamente infinito di elementi come quello dei numeri interi positivi e negativi. Potenza delle espressioni regolari!
L'ultima coppia è la più complessa e rende bene l'idea di quello che si riesce ad ottenere combinando le espressioni regolari con le definizioni come descritte nella sezione precedente:
{SIGN}?{DIGIT}*"."{DIGIT}+{EXP}? { printf("REALE\n"); }
In quest'ultimo esempio si hanno elementi opzionali, altri che possono presentarsi un numero indefinito di volte ma anche nessuna volta e infine è presente una cosa che fino ad ora non aveva fatto la sua comparsa: l'elemento di testo. Infatti, tutto ciò che è compreso fra virgolette sarà ricercato nel flusso di ingresso così come definito, in questo caso un punto rappresentante la virgola del valore reale. L'espressione sopra è in grado di catturare elementi come ad esempio:
* +1.035
* .6
* -3.9e3
* 2.576834353622E-10
Come sopra, la fantasia non ha limiti e l'insieme delle stringhe riscontrate attraverso questa espressione regolare è teoricamente infinito. Ad ogni modo, la sua compattezza la rende chiara e facilmente comprensibile permettendo a chiunque di capirne molto velocemente il ruolo svolto.
In realtà, ci sarebbe una quarta coppia che svolge più che altro un lavoro di ripulitura dai caratteri di spazio e nuova riga. La forma è la seguente:
[ \t\r\n]+
In questo caso l'azione non è riportata volontariamente e non è un errore. Questa forma è equivalente ad aprire e chiudere parentesi graffe, ovvero associare un'azione nulla al modello. In pratica le stringhe corrispondenti all'espressione regolare sopra vengono ignorate e nessuna azione è intrapresa; nel caso specifico, eventuali spazi o caratteri di nuova riga vengono, come detto, saltati a piedi pari.
Sezione Codice utente
Quest'ultima sezione contiene semplicemente codice utente che sarà copiato così com'è nel file ottenuto. Questa sezione è opzionale e viene spesso usata per contenere funzioni richiamate dallo scanner come supporto all'elaborazione. Di fatto, qua possono essere riportate tutte quelle funzioni utili che sono richiamate all'interno di qualche azione nella sezione delle regole sopra descritta.
Nell'esempio discusso, in particolare, non esiste la necessità di alcuna funzione di supporto e pertanto questa sezione può essere eliminata come già accennato. In realtà, però, volendo generare uno scanner che possa vivere di vita propria, bisogna fornirlo di una funziona main o il compilatore si lamenterà del nostro operato, alla fine.
A questo punto, però, è necessaria una piccola parentesi: all'atto della generazione del file .c viene prodotta la funzione yylex(), la quale analizza il flusso di dati in ingresso estrapolando i vari token secondo le regole imposte. Questa funzione, salvo diversa indicazione, non ritorna al chiamante fino a quando non ha esaurito i suoi dati in lettura. A dire la verità, la cosa può (e spesso lo fa) diventare più complessa e i dati in ingresso vengono analizzati solo in parte, un pezzo alla volta: questo è il caso di uso concomitante con strumenti come bison per la generazione di un analizzatore sintattico/lessicale. Nell'esempio proposto, ad ogni modo, tale funzione sarà chiamata all'interno della procedura principale e scorrerà sull'intero insieme di dati fino ad esaurimento scorte per poi tornare alla funzione chiamante.
Ricollegandosi a quanto detto sopra, nella sezione di codice utente sarà riportato ciò che segue:
int
main (int argc, char** argv)
{
++argc; --argv;
if(argc > 0)
yyin = fopen(argv[0], "r");
else yyin = stdin;
yylex();
return 0;
}
Nello specifico, si associa il flusso di ingresso dello scanner ad un file passato come argomento da riga di comando oppure direttamente allo standard input se il primo non è presente. Questo lo si fa semplicemente assegnando alla variabile globale yyin il corretto flusso di ingresso dal quale lo scanner estrapolerà un elemento alla volta fino al carattere di end-of-file (fine file), a seguito del quale ritornerà il valore 0.
Una volta definito il flusso di ingresso, non resta altro che attivare lo scanner e lasciare che compia il suo lavoro.
Il file flex.l
Raccogliendo i pezzi del nostro esempio, il file risultante dovrebbe avere più o meno la forma che segue:
%{
#include
%}
ID [a-zA-Z]+
SIGN [-|+]
DIGIT [0-9]
EXP [e|E][0-9]+
%option noyywrap
%%
{ID} { printf("IDENTIFICATORE\n"); }
{SIGN}?{DIGIT}+ { printf("INTERO\n"); }
{SIGN}?{DIGIT}*"."{DIGIT}+{EXP}? { printf("REALE\n"); }
[ \t\r\n]+
%%
int
main (int argc, char** argv)
{
++argc; --argv;
if(argc > 0)
yyin = fopen(argv[0], "r");
else yyin = stdin;
yylex();
return 0;
}
Il risultato finale sono poche righe e sembra impossibile che il lavoro svolto possa essere tanto, eppure ciò che da queste righe sarà generato sarà uno scanner in grado (come detto) di discriminare fra stringhe di caratteri, interi positivi o negativi e valori reali. A questo punto, non resta che provare per credere!
Per compilare il file flex.l ed ottenere quindi il file lex.yy.c basta passare il primo dei due come argomento al programma flex:
flex flex.l
Dal secondo si può invece ricavare un file eseguibile semplicemente fornendolo in ingresso ad un compilatore come ad esempio gcc. Più in pratica, basterà digitare il comando (il quale produrrà un eseguibile dal nome scanner):
gcc -o scanner lex.yy.c
L'eseguibile ottenuto è un programma a tutti gli effetti che una volta lanciato analizzerà il file fornito in ingresso oppure i dati passati sullo standard input se non sono presenti argomenti. Questo è ciò a cui si aspirava e con poche righe molto semplici è stato possibile ottenere un prodotto efficiente ed efficace in brevi, semplici passi. Per lanciarlo, basterà digitare:
./scanner
Se lanciato senza argomenti in ingresso, si potranno inserire caratteri di ogni tipo e ad ogni pressione del tasto invio questi verranno suddivisi e valutati correttamente. Per terminare l'esecuzione, basterà semplicemente digitare la magica combinazione ctrl+d, oppure la più drastica ma sempre funzionante ctrl+c.
Conclusioni
Com'è stato possibile descrivere brevemente e in modo molto elementare in queste poche righe, flex rappresenta un potente strumento per l'analisi di un flusso di dati e la sua suddivisione in token più facilmente trattabili a valle del processo di elaborazione. Le potenzialità di questo strumento vanno in realtà ben oltre la piccola panoramica di cui sopra e si consiglia di fare riferimento alla documentazione ufficiale per quanto riguarda ogni dubbio o domanda sul funzionamento o anche solo per approfondimenti.
Nella realtà l'esempio di cui sopra è estremamente semplice e di dubbia utilità, ma introduce in modo chiaro le diverse sezioni attribuendo ad ognuna di loro il ruolo che ricopre all'interno di un progetto basato su flex. A partire da questo esempio banale è possibile costruire oggetti di gran lunga più complessi e utili anche in casi reali, ma bisogna dire che spesso flex è usato in combinazione con altri software piuttosto che da solo, anche se quest'ultima alternativa non è sempre da escludere.
Un altro strumento molto utile nel campo dell'analisi sintattica è bison, di cui si consiglia uno studio o approfondimento quasi obbligatorio. Risulta allo stesso tempo semplice ed estremamente utile combinare insieme questi due oggetti per ottenere efficienti ed efficaci analizzatori sintattico/lessicali da introdurre nei propri progetti, così da poter descrivere e gestire grammatiche di ogni tipo e creare parser di qualità in poco tempo

fonte: Pluto