Analizzatori lessicali, Linux e HP48G per invogliare l'utente medio all'uso di due strumenti di sviluppo UNIX ingiustamente ritenuti "difficili".

In questo articolo, viene fatta una breve presentazione, assolutamente non-tecnica nè esaustiva, di yacc e lex, con lo scopo di invogliare l'utente medio all'uso di due strumenti di sviluppo UNIX ingiustamente ritenuti "difficili". Per raggiungere lo scopo, l'articolo è corredato dal pacchetto dimostrativo g48, un traduttore dal C all'RPN per HP48G, sviluppato dall'Autore e presentato come esempio di applicazione di yacc&lex ai lettori del Linux Journal).


Gli analizzatori sintattici e lessicali.
Il mondo UNIX basa buona parte della sua forza sull'esistenza di tutta una serie di tools a sostegno della programmazione C, alcuni dei quali forse non molto noti all'utente non-specializzato. Mi riferisco soprattutto a programmi quali lex (analizzatore lessicale) e yacc (analizzatore grammaticale) e alle loro moderne incarnazioni sotto Linux, come Flex e Bison.



Programmi quali lex e yacc (originariamente scritti, rispettivamente da Steve Johnson e da Mike Lesk) sono stati usati in passato per realizzare molti dei compilatori oggi esistenti, compresi il C portabile (PCC), il Pascal, il Fortran-77, nonchè applicativi quali awk, bc, eqn e pic e sono tuttora usati nello sviluppo di quella popolosa famiglia di pacchetti ( quali f2c, b2c, emulatori Dos e Windows e via di seguito) che traducono da un linguaggio all'altro.


Con l'avvento e la diffusione di un sistema operativo come Linux, il mondo UNIX fa prepotentemente capolino dalle nostre scrivanie domestiche, per cui nessun programmatore, neanche quello amatoriale, "della domenica" per così dire, può più prescindere dalla conoscenza, anche solo superficiale, di strumenti di questo genere.


Che cos'è g48?
Com'è noto, l'HP48G è una macchinetta tascabile dalle capacità matematiche (sia simboliche che numeriche) veramente notevoli: numeri complessi, integrali, derivate, eq. differenziali, distribuzioni statistiche, sistemi di equazioni non lineari, tutta l'algebra lineare (inversione, autovalori e autovettori, decomposizioni LU, Schur, ...), 12 tipi di grafici diversi (2d, 3d, polari, ...), protocolli XMODEM, KERMIT, etc. etc.



Ma, ahinoi!, l'HP ha un piccolo visore e una tastiera che non sono certo il massimo per introdurre e testare programmi in RPN, senza parlare della scarsa leggibilità di questo tipo di codice.



Per ovviare a questo problema e poichè non mi è mai sembrato razionale lasciare inutilizzata questa meraviglia, ho pensato di scrivere un programma che girasse su LINUX capace tradurre programmi scritti nella sintassi che è più nota al grande pubblico di questo sistema operativo: la sintassi del linguaggio C.



g48 è un software snello e agile, costituito in effetti da poche centinaia di righe, interamente basato sulla celebre accoppiata YACC&FLEX. Quanto sia davvero "agile" l'Utente lo scoprirà non appena compilerà qualcosa: la risposta è praticamente istantanea! La sintassi ammessa è quella del C, con qualche ovvia eccezione per quanto riguarda le routines dell'I/O, ed altre. Ma si tratta di limitazioni di scarso rilievo, potendosi usare facilmente i potenti comandi di input/output propri di HP, implementabili in opportune librerie da #include-re.



L'intero pacchetto g48 consiste soltanto dei seguenti files: i due sorgenti parser.y (contenente le direttive yacc + un minuscolo main()) e lexer.l (contenente le direttive lex); il makefile per la compilazione, ed alcuni demo ed è stato scritto e testato sotto Linux 2.0.0.



Il software è corredato, inoltre, da una routine in PERL per la comunicazione LINUX-HP tramite porta seriale, basata sul protocollo di trasferimento KERMIT, capace di trasformare Linux in un client HP a tutti gli effetti.


Lex.

Il programma lex traduce una serie di direttive (contenute nel file lexer.l) in frammenti di codice C, producendo una routine di riconoscimento lessicale yylex() (contenuta nel file lex.yy.c) in grado di identificare e restituire le singole "parole" che il linguaggio ammette. Dal punto di vista di lex, l'input non è altro che una sequenza non-strutturata di token (le nostre "parole", appunto); un flusso di numeri interi destinata ad assumere significato soltanto in sede di analisi logica, allorchè yacc chiamerà yylex() e combinerà insieme i vari token per formare "frasi" di senso compiuto.

Naturalmente, lex è molto di più che un semplice scanner di token. Utilizzando speciali costrutti (che solo in parte saranno presi in considerazione in questo articolo), lex può prendere decisioni a riguardo dell'associatività e della precedenza degli operatori matematici. Può, inoltre, effettuare delle vere e proprie transizioni di stato, in maniera che le sue regole di riconoscimento possano adattarsi a particolari situazioni, realizzando dei mini-scanners autonomi e indipendenti. Per capirne l'utilità, basta pensare ai token che vanno verso un modem: i codici che vengono subito dopo il token AT non hanno lo stesso significato che altrove, per cui un simulatore lex potrebbe opportunamente effettuare una transizione nello "stato comandi".



E' proprio necessario usare lex per scrivere i nostri scanner? Nei casi più semplici, no. E' sempre possibile scrivere un equivalente di yylex() mediante una serie di chiamate tipo scanf(), ma in generale (specialmente se devono essere identificati oggetti più complicati come numeri reali in formato esponenziale, stringe, matrici, etc.) l'uso di lex può semplificare notevolmente le cose, soprattutto se si tiene conto della riusabilità e della manutenibilità del nostro codice. Secondo me la filosofia più corretta è quella di scrivere scanner più elementari possibili, demandando la comprensione vera e propria del "testo" interamente a yacc, che ha tutte le carte in regola per riuscirci bene.



Il tipico sorgente di lex è fatto di varie parti, la cui struttura è grosso modo la seguente:

  {%  dichiarative C  #include e #define  %}  dichiarazioni lex  %%  regole di lex   %%  codice C dell'utente (routines particolari, etc.) 

La parte dedicata alle dichiarative C serve principalmente per comunicare con yacc. Contiene essenzialmente due informazioni: l'elenco di tutti gli identificativi interi rappresentanti i token (> 256), la dichiarazione di tipo dello stack di yacc più, eventualmente, variabili importate con la specifica extern. I primi due tipi di informazione vengono prodotti automaticamente da yacc mediante l'opzione -d e sono contenute in un file #include-re, zeppo di #define, e che si chiama y.tab.h:

  #define NAME 258  #define NUMBER 259  .....  extern YYSTYPE yylval 

La variabile esterna yylval deve essere riempita, a cura di lex, col "testo" del token letto. Come questo vada fatto, dipende ovviamente dal tipo scelto (YYSTYPE) per lo stack: in genere un struttura complessa di tipo union. In g48 si è scelto di usare il più semplice tipo disponibile, la stringa (char*).

La parte dedicata alle dichiarative lex contiene la definizione di una serie di variabili utili per la scrittura delle regole di riconoscimento stesse, in una sintassi che ricorda molto da vicino quella delle espressioni regolari di UNIX, ma con qualche funzionalità in più. Eccone un esempio tratto direttamente dall'analizzatore lessicale di g48:

  string          \"[^"]*\"  dig  [0-9]  num1            {dig}+\.?([eE][-+]?{dig}+)?  num2            {dig}*\.{dig}+([eE][-+]?{dig}+)?  number          {num1}|{num2} 

Come si può vedere, una variabile x viene valutata mediante la scrittura {x}. E' inoltre possibile raggruppare espressioni con parentesi tonde () ed effettuare operazioni logiche elementari (quali l'or |) tra due espressioni diverse.



Per ultimo, la parte più importante: le regole di riconoscimento vere e proprie. Ogni regola una riga, divisa in due parti: il pattern di riconoscimento (in genere una variabile lex) e un frammento di codice C, come nel seguente esempio:

  \n  /* ignora new-line */  {number} {yylval=yytext; return(NUMBER);}  {string} {yylval=yytext; return(STRING);}  etc. etc.   .  { return(yytext[0])}; 

La scrittura yylval=yytext ha valore essenzialmente formale ed è stata introdotta in questo contesto per illustrare il passaggio di informazioni tra le locazioni lex (la stringa yytext) e le locazioni yacc ( la stringa yylval). Nella realtà, la sua implementazione dipende dai tipi scelti. Nel nostro caso, avendo a che fare con puntatori char* con diversa visibilità, occorrerà allocare nuovo spazio, copiarvi yytext e costringere yylval a puntare ad esso (per maggiori informazioni, vedi il file lexer.l).



Notare la riga costituente l'ultima regola lex: tutti i singoli caratteri alfabetici non riconosciuti da nessuna regola, vengono spediti direttamente a yacc, il quale, li utilizza alla stregua di token non dichiarati e li riconosce in base al loro valore numerico ASCII ( che è minore di 256).

Yacc.

yacc ( che sta per "yet another compiler-compiler") è un generatore di analizzatori sintattici, vale a dire programmi capaci di "comprendere" le "frasi" scritte in un dato linguaggio e di prendere delle decisioni in base al loro significato. Nel nostro caso, essendo g48 un traduttore, comprendere vuol dire riconoscere i costrutti del C e tradurli nei corrispondenti RPN.



Come per lex, yacc legge le regole grammaticali da un file di testo la cui struttura è grosso modo la seguente:

         {%         dichiarative C  #include e #define         %}  definizione token         %%         regole grammaticali vere e proprie          %%         /* codice C dell'utente, col main() */  main()  {  ...  yyparse() ...  } 

La sezione dedicata alle dichiarative C contiene essenzialmente la definizione di YYSTYPE, mentre la sezione dedicata ai token, che è del tipo:

  %token NAME STRING NUMBER COMMENT ...   %right '+' '-' '*' '/'  %left NEG  %left NOT   %right POW PROD DIV MOD  etc., etc. 

istruisce yacc sugli identificativi che vogliamo esportare verso lex e delle loro caratteristiche di associatività ( a sinistra, a destra, etc.).



Anche in questo caso la parte del leone la fa la sezione compresa tra i segni %% ... %%, la grammatica vera e propria ma, a differenza di lex, le regole di yacc, a causa del loro carattere intrinsecamente ricorsivo, nascondono trabocchetti e conflitti di natura logica spesso difficili da individuare ed eliminare.



Le regole grammaticali di yacc hanno una struttura semplice e notevolmente espressiva:

  [entita]:  [sequenza token] { azione;}      |[sequenza token] { altra azione;}      | ...      ;     

Esse definiscono ad ogni passo nuove entità, connesse a tutte le altre mediante processi spesso autorefereziali, implicanti sequenze di token logicamente contigui.



Nell'esempio che segue (come al solito, estratto dai listati di g48), viene definita ricorsivamente l'entità expr:

 expr:   NUMBER         |NAME            | '(' expr ')'   { sprintf($$,"%s",$2);}         | expr '+' expr   { sprintf($$,"%s %s +",$1,$3);}         | expr '-' expr   { sprintf($$,"%s %s -",$1,$3);}         | expr '*' expr %prec PROD  { sprintf($$,"%s %s *",$1,$3);}         | expr '/' expr %prec PROD  { sprintf($$,"%s %s /",$1,$3);}  | '-'  expr %prec NEG     { sprintf($$,"-%s ",$2);}  | etc. etc.  

per cui un'espressione algebrica può essere un numero, un nome di variabile, un'espressione racchiusa tra parentesi, e ancora: la somma di due espressioni, il prodotto di due espressioni e via di seguito, nello stile un pò vaporoso tipico di linguaggi come il Lisp, il Prolog, etc. Per districarsi in questo tipo di dichiarazioni, forse può tornare utile ricordare un classico esempio di definizione ricorsiva, la definizione di coda: una coda è una persona oppure una persona seguita da una coda. Se ci riflettiamo un pò su ci accorgiamo subito che la differenza tra questa definizione e la definizione di espressione algebrica, data nell'esempio, è più nella quantità che nella qualità, per cui expr non è realmente più complicata di coda.
Osserviamo ora le regole di riscrittura vere e proprie inserite per ogni tipo di espressione. Con i simboli $1, $2 etc si intedono i token o le entità costituenti il pattern di riconoscimento, mentre con $$ si intende che cosa yacc debba restituire a seguito del riconoscimento stesso. Come si può facilmente intuire, questi simboli rappresentano posizioni nello stack di yacc, per cui vanno trattati come i tipi C corrispondenti. Nel nostro caso, abbiamo a che fare con semplici puntatori a char e quindi $$ viene costruito combinando opportunamente delle stringhe, mediante la sprintf(). Quando non viene specificata nessuna azione, viene restituito il primo token $1. Tornando al nostro esempio, le azioni inserite rappresentano una parte delle regole che g48 utilizza per riscrivere in notazione polacca inversa le espressioni fornite in notazione algebrica ordinaria.

Conclusioni e Raccomandazioni.

Allorchè il Lettore proverà a compilare con g48 il primo ciclo for, otterrà probabilmente un magnifico sintax error e non vorrà più saperne di yacc&lex. Anche a me è successo la prima volta (le prime 10 volte, a dir il vero!) ma poi ho infine capito: benchè sia cosa estremamente naturale per il programmatore C, bisogna rassegnarsi: non si può usare la variabile i per controllare il ciclo. Le iterazioni nel campo dei numeri immaginari porterebbero a risultati imprevedibili!



A parte gli scherzi, g48 traduce davvero dal C e gli "oggetti" prodotti girano effettivamente sull'HP ma forse è più giusto considerare questo tipo di software in una luce meno strumentale, più culturale: come un esercizio, nulla di più, il cui scopo è conoscere ed apprezzare i tanti e potenti tools di sviluppo tipici del mondo UNIX e che ora Linux mette a disposizione di tutti i possessori di un PC.

fonte: Pluto

Se ti è piaciuto l'articolo , iscriviti al feed cliccando sull'immagine sottostante per tenerti sempre aggiornato sui nuovi contenuti del blog: