Nel presente articolo cercheremo di approfondire che cosa sono gli analizzatori lessicali e quali attività essi svolgono. Vedremo di cosa è costituito un ipotetico output di dati diretto ad un parser e proveremo a realizzare un semplice analizzatore lessicale mediante il generatore di codice Flex.
Prerequisiti
Si presume che il lettore abbia dimistichezza con il generatore di parser Bison, che conosca approfonditamente la programmazione in linguaggio C ed abbia una conoscenza generale circa la struttura dei compilatori.
Iniziamo con un esempio
Gli analizzatori lessicali svolgono compiti che possiamo così sintetizzare:
- suddividere un testo in token (frammenti di testo);
- codificare i token ed inviarli al parser;
- analizzare il testo secondo delle metodologie specifiche.
Dei punti elencati i primi sono di facile comprensione e nel prosieguo dell’articolo ne daremo evidenza. L’ultimo punto invece richiede un approfondimento. L'analizzatore lessicale è sempre il primo stadio di un compilatore, proviamo ad immaginarne il flusso: il testo viene analizzato carattere per carattere, ogni volta che viene trovata una sequenza valida (presente nella lista dei token validi) questi continua ad analizzare fino a quando non viene trovata una parola chiave(o sequenza valida) e concludere "token trovato". In tale condizione, sembrerebbe logico, si può immaginare che l'analizzatore possa trasmettere il token al parser e passare ad analizzare i caratteri successivi. Non si può affermare a priori che questo sia il comportamento corretto. Dipende dai criteri di analisi stabilti. Nell'esempio che segue vedremo come in certi casi l'analizzatore non può terminare l'attività nelle condizioni proposte ma debba proseguire nella ricerca. Si consideri il seguente codice scritto in linguaggio C(my_test.c):
1 int main ( void )
2 {
3 int i=10,h=0;
4 i = i+++h;
5 printf( "il calcolo vale %d\n", i);
6 return 0 ;
7 }
Osserviamo fin da subito che tale codice non è compilabile a meno di non inserire prima della funzione main() l’include del file stdio.h. Dimentichiamoci per un attimo di questo dettaglio che esula dal contesto(non è nei nostri interessi compilare il file my_test.c). Osserviamo la riga 3. Tale dichiarazione, per quanto insolita, è corretta(nello standard C99). Abbiamo un operatore somma ‘+’ ed uno di incremento ‘++’ in sequenza, ma in quale ordine vanno interpretati tali operatori? Abbiamo due possibilità:
- i= (i++) + h;
- i = i + (++h);
Si potrebbe argomentare che la prima è preferibile in quanto gli operatori incremento ‘++’ sono prioritari rispetto all’operatore somma ‘+’. Diciamo che l’interpretazione corretta è la prima ma non a causa della priorità degli operatori. La soluzione va ricercata nelle specifiche del C99 dove vengono definite anche le modalità di analisi lessicale che qui riportiamo(tradotta):
Se il flusso di ingresso è stato analizzato e tokenizzato in pre-elaborazione fino ad un dato carattere, il token pre-elaborato successivo è la più lunga sequenza di caratteri che potrebbero costituire un token pre-elaborato.
In conclusione abbiamo che l’interpretazione corretta è la prima(i= (i++) + h) in quanto ‘++’ è una sequenza di caratteri (un token) più lunga di ‘+’ e non a causa di priorità degli operatori!
Appare quindi ovvio che problematiche di questo tipo devono essere dipanate dall’analizzatore lessicale in quanto il flusso dati diretto al parser deve essere sequenziale e stabilito in tale ambito. Sarà pertanto compito dell’analizzatore dover trovare prima l’operatore incremento e successivamente l’operatore somma, in caso contrario si avrebbe un comportamento non rispettoso dello standard del linguaggio proposto(C99). E’ quindi evidente che, oltre ai compiti descritti, l’analizzatore lessicale deve anche poter individuare parole chiave, operatori e terminatori secondo un ordine preferenziale. Si pensi bene a questi dettagli prima di intraprendere la realizzazione di codice ad hoc per realizzare analizzatori lessicali.
Grammatica di esempio per flex, mflex.flex
Nell’esempio che segue, mediante Flex, realizzeremo un analizzatore utile a comprendere la problematica di interfacciamento con il parser. Consideriamo la seguente grammatica(che chiameremo mflex.lex):
%{
enum yytokentype {
CONSTANT = 258,
IDENTIFIER = 259,
LE_OP = 260,
INT = 261,
CHAR = 262,
FOR = 263,
INC = 264,
STRING = 265,
RETURN = 266
};
%}
%option noyywrap
DIGIT [0-9]
ID [a-zA-Z][a-z0-9]*
%%
"int" { printf( "Token: INT(%3d), semantic NULL\n", INT ); }
"char" { printf( "Token: CHAR(%3d), semantic NULL\n", CHAR ); }
"for" { printf( "Token: FOR(%3d), semantic NULL\n", FOR ); }
"return" { printf( "Token: RETURN(%3d), semantic NULL\n", RETURN ); }
"<=" { printf( "Token: LE_OP(%3d), semantic NULL\n", LE_OP ); }
"++" { printf( "Token: INC(%3d), semantic NULL\n", INC ); }
"(" { printf( "Token: '%s', semantic NULL\n", yytext ); }
")" { printf( "Token: '%s', semantic NULL\n", yytext ); }
"{" { printf( "Token: '%s', semantic NULL\n", yytext ); }
"}" { printf( "Token: '%s', semantic NULL\n", yytext ); }
"[" { printf( "Token: '%s', semantic NULL\n", yytext ); }
"]" { printf( "Token: '%s', semantic NULL\n", yytext ); }
";" { printf( "Token: '%s', semantic NULL\n", yytext ); }
"+" { printf( "Token: '%s', semantic NULL\n", yytext ); }
"=" { printf( "Token: '%s', semantic NULL\n", yytext ); }
"," { printf( "Token: '%s', semantic NULL\n", yytext ); }
{DIGIT}+ { printf( "Token: CONSTANT(%3d), semantic %d\n", CONSTANT, atoi( yytext ) ); }
{ID} { printf( "Token: IDENTIFIER(%3d), semantic '%s'\n", IDENTIFIER , yytext ); }
\".*\" { printf( "Token: STRING(%3d), semantic '%s'\n", STRING , yytext ); }
[ \t\n]+ /* elimina spazi nulli */
printf( "Unrecognized character: %s\n", yytext );
%%
main( argc, argv )
int argc;
char **argv;
{
++argv, --argc; /* skip over program name */
if ( argc > 0 )
yyin = fopen( argv[0], "r" );
else
yyin = stdin;
yylex();
}
Nella presente trattazione non desideriamo approfondire gli aspetti di programmazione Flex (si rimanda alla lettura del relativo manuale per ulteriori informazioni). Possiamo tuttavia osservare alcuni aspetti generali. Flex, come tutti generatori di codice, deve essere istruito mediante un file di input per poter realizzare il codice desiderato. Tali file di input sono costituiti sostanzialmente di tre parti suddivise dai terminatori %%, cioè abbiamo:
definizioni
%%
regole
%%
codice utente
Nel nostro caso, nell’area delle definizioni, abbiamo presente l’enumerativo ‘yytokentype’. Si osservi che nella generalità dei casi troveremo tale enumerativo sotto forma di include di un file *.tab.h (creato da bison).
Lo scopo che ci prefiggiamo è quello di creare un analizzatore in grado di tokenizzare uno stream di dati come descritto nell’esempio (my_test.c). Per chi volesse verificarne la funzionalità basta eseguire le istruzioni:
flex mflex.lex: viene generato il file (adatto alla compilazione) lex.yy.c;
gcc lex.yy.c: per compilare il file ottenuto ed ottenere il file eseguibile a.out;
mediante il comando ./a.out my_test.c: si esegue il programma realizzato, dando come input il file di test dell’esempio;
Tracciato di test
Quando eseguiamo l’analisi test proposta(./a.out my_test.c) ecco che cosa otteniamo in output:
Token: INT(261), semantic NULL
Token: IDENTIFIER(259), semantic 'main'
Token: '(', semantic NULL
Token: IDENTIFIER(259), semantic 'void'
Token: ')', semantic NULL
Token: '{', semantic NULL
Token: INT(261), semantic NULL
Token: IDENTIFIER(259), semantic 'i'
Token: '=', semantic NULL
Token: CONSTANT(258), semantic 10
Token: ',', semantic NULL
Token: IDENTIFIER(259), semantic 'h'
Token: '=', semantic NULL
Token: CONSTANT(258), semantic 0
Token: ';', semantic NULL
Token: IDENTIFIER(259), semantic 'i'
Token: '=', semantic NULL
Token: IDENTIFIER(259), semantic 'i'
Token: INC(264), semantic NULL
Token: '+', semantic NULL
Token: IDENTIFIER(259), semantic 'h'
Token: ';', semantic NULL
Token: IDENTIFIER(259), semantic 'printf'
Token: '(', semantic NULL
Token: STRING(265), semantic '"il calcolo vale %d\n"'
Token: ',', semantic NULL
Token: IDENTIFIER(259), semantic 'i'
Token: ')', semantic NULL
Token: ';', semantic NULL
Token: RETURN(266), semantic NULL
Token: CONSTANT(258), semantic 0
Token: ';', semantic NULL
Token: '}', semantic NULL
Nella lista ottenuta abbiamo che ogni token della sequenza contiene un valore semantico ed uno grammaticale. Il valore semantico in alcuni casi presenta valore NULL. In tali casi esso non ha alcun significato e possiamo dire che il valore grammaticale è “sufficientemente easustivo”. Per capire più agevolmente questo concetto consideriamo la porzione di codice “i = 0” all’interno del ciclo for che qui sotto riportiamo:
Token: IDENTIFIER(259), semantic 'i'
Token: '=', semantic NULL
Token: CONSTANT(258), semantic 0
Da un punto di vista grammaticale viene verificata la seguente regola:
IDENTIFIER ‘=’ CONSTANT
Cioè tale dichiazione è corretta indipendentemente dal valore(0) che CONSTANT può assumere. Dal punto di vista del generatore di codice invece, tale dichiarazione è rilevante. Diciamo quindi che Bison verfica che ciò che viene scritto deve corrispondere ad una data grammatica mentre la gestione dei valori semantici non è legata all’attività di parsing.
Conclusioni
Nel nostro tracciato ottenuto possiamo notare la presenza dei due valori semantico e lessicale cui in taluni casi abbiamo volutamente settato a NULL il dato semantico. Tale scelta è dovuta al fatto che abbiamo voluto dare enfasi al fatto che in tali casi il valore semantico non é in alcun modo rilevante ne per il parser e nenache per gli stadi successivi.
Flex, è un generatore di codice molto comune ed estremamente affidabile. Ricordiamo che non è l’unico. In taluni casi risulta inoltre inadatto. Talvolta per svolgere l’attività di analisi lessicale si sceglie di realizzare del codice ad hoc per renderne più rapida l’esecuzione.
