<- Flex: Fast Lexical Analyzer - Indice Generale - Copertina - Server Side Java - parte 2 ->

Sistemi Liberi

Bison: The GNU Parser Generator

di Michele Caini

Chomsky analizza delle idee verdi
che dormono furiosamente e
non analizza invece le brillanti stupide idee
che sono più che mai sveglie ed arzille

Carl William Brown

Introduzione

Come tutti sanno, re-inventare la ruota è il passatempo preferito dagli sviluppatori, anche se non sempre riesce proprio tonda! Lo sviluppo di parser pensati ad-hoc per le proprie esigenze è uno dei campi in cui i risultati lasciano più spesso a desiderare: sarà per la teoria complessa e spesso ignorata che vi sta alle spalle, sarà per la difficoltà di riuscire ad ottenere qualcosa che sia allo stesso tempo efficiente ed efficace, insomma sarà quel che sarà ma creare parser dalle buone prestazioni è cosa più ardua di quel che si pensi!
Fortunatamente per gli sviluppatori C esiste Bison, un lavoro nato dal progetto GNU per la generazione automatica di parser a partire dalla definizione di grammatiche.
Grazie a questo strumento è possibile dedicarsi solo ed esclusivamente alla grammatica che si vuole descrivere, concepirla e definirla senza preoccuparsi dei dettagli implementativi e lasciare che un parser di qualità venga prodotto per noi a partire da essa, senza doverlo produrre a mano in funzione di essa.
Ovviamente, un bel vantaggio!

Bison

Premessa

Trattare anche solo in minima parte argomenti di informatica teorica richiederebbe non un articolo ma una serie di articoli, i quali rischierebbero comunque di non riuscire ad approfondire in modo adeguato e sufficiente la questione. Per questo motivo si suppone che il lettore abbia già un'infarinatura sull'argomento e la discussione verterà solamente in minima parte, e senza la pretesa di completezza, sulle grammatiche libere da contesto, ovvero l'area che di fatto interessa maggiormente in questa sede.
Sebbene in gran parte gli argomenti trattati risulteranno comprensibili anche senza approfondimenti della materia, è consigliato a chiunque voglia comprendere a fondo la potenzialità di Bison, a chiunque sia interessato e comunque in genere a chiunque (in quanto senza dubbio componente affascinante dell'informatica), lo studio di tale materia.

Bison in pillole

Come si può leggere dalla documentazione ufficiale:

Bison is a general-purpose parser generator that converts an annotated context-free grammar into an LALR(1) or GLR parser for that grammar. Once you are proficient with Bison, you can use it to develop a wide range of language parsers, from those used in simple desk calculators to complex programming languages.

Bison è un generatore di parser multiuso che converte una specifica grammatica libera da contesto in un parser LALR(1) o GLR per quella grammatica. Una volta presa confidenza con Bison, potrete usarlo per sviluppare una vasta gamma di parser per linguaggi, a partire da quelli usati in semplici calcolatrici da tavolo fino a complessi linguaggi di programmazione.

Gli usi possibili sono evidenti: laddove si vogliano effettuare operazioni di analisi di un file di ingresso per il recupero dei parametri di configurazione del nostro software, così come nel caso in cui si voglia dar vita a quel linguaggio su cui ragioniamo da qualche mese, Bison si presta allo scopo. Gli esempi potrebbero durare a lungo e sfociare in posti dove al momento non si potrebbe neanche immaginare la presenza di una necessità in tal senso.
Durante lo studio dello strumento sarà discusso un esempio di applicazione realizzata con Bison, così da fare pratica in minima parte con questo programma dai mille usi. In particolare, sarà realizzata una piccola calcolatrice tascabile dalle poche funzioni ma che possa servire almeno a capire il funzionamento di Bison.

File di descrizione della grammatica

Il file di input per Bison è diviso in tre macro parti, separate fra loro da una linea contenente una coppia di simboli percentuali (%%) e nient'altro.
La prima parte contiene sostanzialmente due sezioni: il prologo e le dichiarazioni di Bison. La prima delle due sezioni riporta (fra una coppia di %{ e %}) macro e dichiarazioni di funzioni e variabili che verranno copiate così come sono all'inizio del file generato. Questo è, intuitivamente, un ottimo posto per includere altri file o librerie in perfetto stile C. Oltre a quanto accennato, nella seconda sezione sono presenti dichiarazioni che definiscono i simboli terminali e non, appartenenti alla grammatica specifica, e le eventuali precedenze fra di essi. Tutto ciò è come al solito opzionale e potrebbe anche condurre ad una sezione completamente vuota.
La seconda parte del file riporta le regole grammaticali descritte in una forma derivata dal BNF e comprensibile da Bison. Qui è dove viene descritta nella sua integrità la grammatica desiderata e dove vengono definite ed associate le diverse azioni da compiere in base alle produzioni incontrate. Data la natura e lo scopo del software, in questa sezione deve obbligatoriamente essere presente almeno una regola, cosa del resto abbastanza intuitiva.
Nell'ultima parte del file, opzionale anch'essa, si possono includere funzioni di supporto, sviluppo di prototipi definiti nella prima parte e via dicendo. Come vedremo nel seguito, questa sezione è molto importante in alcuni casi mentre può essere del tutto omessa in tanti altri.

Prologo e dichiarazioni

Come detto, il prologo è utile per l'inclusione di file e la definizione di macro, prototipi, variabili globali e quant'altro, il tutto riportato as-is ad inizio file. Non è il caso, quindi, di approfondire ulteriormente.
Di gran lunga più interessante la sezione di dichiarazioni per Bison, dove sono riportati e trattati i simboli terminali e i simboli non terminali. I primi rappresentano una classe di token validi all'interno della grammatica e sono maneggiati attraverso valori numerici (ipoteticamente restituiti da un analizzatore lessicale in questa forma, rappresentato dalla funzione yylex che ritorna un codice di tipo per i token). I secondi sono usati per la scrittura delle regole grammaticali e rappresentano le produzioni valide della grammatica. Ovviamente, in ogni caso sono ammesse solo stringhe alfanumeriche e poco più.
I simboli terminali possono essere scritti in più modi ma sostanzialmente in questa sede interessa solo quello che prevede di definire un nome per tipi di token come:

%token nome

Questa forma porta all'introduzione di macro #define così che la funzione yylex (ovvero, l'analizzatore lessicale che restituisce i token) possa utilizzare il nome indicato per indicare questo specifico codice di tipo per token. Va detto che, come buona norma, i nomi associati ai simboli terminali sono riportati completamente in lettere maiuscole.

Per quanto ci riguarda, la nostra calcolatrice ha bisogno di alcuni simboli terminali che descrivano ciò che è in grado o meno di trattare. In particolare, vorremmo che fosse in grado di elaborare somme e sottrazioni, moltiplicazioni e divisioni, il tutto con o senza parentesi gestendo correttamente le precedenze. Tutto ciò però non porta all'aggiunta di alcun simbolo terminale, i quali sono ridotti al solo simbolo rappresentante un valore numerico in virgola mobile. Inoltre, bisogna includere nella prima sezione alcune direttive utili. La prima parte del file risulterà simile alla seguente (anche se sarà poi completata solo in seguito con prototipi e affini):

%{
#define YYSTYPE double

#include <stdio.h>
%}

%token VAL            //     valore numerico

La direttiva define indica il tipo di dati per i token e i simboli non terminali. Questo tipo è in modalità predefinita un intero, quindi nel nostro caso deve essere specificato esplicitamente che lo si desidera valutato come valore in virgola mobile.
Al momento, forse, questa sezione apparirà un po' oscura e gli interrogativi saranno tanti, soprattutto per chi non ha le dovute basi di teoria che aiutano a comprendere meglio quanto detto. Ciò nonostante, in seguito la cosa dovrebbe schiarirsi e risultare più comprensibile.

Regole Grammaticali

Le regole grammaticali hanno la forma seguente:

risultato: componenti
    ;

Dove si ha che:

• risultato è un simbolo non terminale descritto dalla regola in questione

• componenti sono vari simboli terminali e non terminali accorpati insieme dalla regola descritta

In realtà, tali regole possono presentare (e spesso lo fanno) spezzoni di codice C che deve essere eseguito ogni volta che si ha un riscontro. La forma risultante estesa e più descrittiva è quindi la seguente:

risultato: componenti
    { codice C }
    ;

Ancora, si possono avere più blocchi di componenti separati da un carattere di or (ovvero |) per una singola regola, ad ognuno dei quali può essere associato un diverso spezzone di codice C o nessuna azione. Una forma che riporta i casi sopra elencati è la seguente:

risultato: // nessuna regola
    | componenti_1
      { codice C }
    | componenti_2
      { codice C }
    ;

In questo blocco si ha una regola vuota, la prima: ciò significa che il risultato può riscontrare anche la sola stringa vuota. Se ci si sofferma a riflettere, è facile intuire la potenza di questo tipo di espressioni. Continuando, si hanno altre due regole descritte dalle proprie componenti e associate a blocchi di codice C. La cosa da notare è come queste siano tutte legate allo stesso risultato, il quale è riscontrato quindi per diverse vie e non in un modo unico, attraverso l'operatore |. Un altro costrutto interessante è la regola ricorsiva, brevemente descritta:

risultato: espressione
    | risultato espressione
    ;

Inutile dilungarsi sulla cosa, anche uno sciocco capirebbe la potenza di questo costrutto. Si pensi ad un interprete di regole separate da un punto e virgola, le si possono descrivere come segue, racchiudendo in poche righe la potenza ed espressività di un linguaggio ricorsivo:

regole: regola
    | regole ';' regola
    ;

Tornando al nostro esempio, questo presenta diverse regole per trattare tutti i casi che possono presentarsi. La seconda parte del file da dare in pasto a Bison sfrutta un po' tutto quanto detto in precedenza (o quasi) per poter valutare una o più espressioni matematiche basilari. Nei dettagli, risulterà simile alla seguente:

expression:  // nessuna operazione
    | expr
    { printf("risultato: %f\n", $$); }
    | expression ';' expr
    { printf("risultato: %f\n", $3); }
    ;

expr: expr '+' term
    { $$ = $1 + $3; }
    | expr '-' term
    { $$ = $1 - $3; }
    | term
    { $$ = $1; }
    ;

term: term '*' value
    { $$ = $1 * $3; }
    | term '/' value
    { $$ = $1 / $3; }
    | value
    { $$ = $1; }
    ;

value: '(' expr ')'
    { $$ = $2; }
    | VAL
    { $$ = $1; }
    ;

I simboli $$ e $N, con N numero intero, rappresentano singolarmente il valore del gruppo di token che la regola accorpa insieme per essere riconosciuta e i valori dei singoli elementi della componente nella regola specificata. Nel codice sopra riportato si notano espressioni utili per la somma, la sottrazione e le operazioni di moltiplicazione e divisione, nonché per il riconoscimento di valori numerici e l'uso corretto di parentesi. Inoltre la forma descritta sopra gestisce in modo idoneo anche le precedenze fra i diversi operatori (alla fine dell'articolo potrete testare di persona quanto detto adesso). Infine, si ha un costrutto per la stampa dei risultati di una espressione e per permettere la concatenazione di più espressioni attraverso un punto e virgola.
Come si può osservare dall'esempio precedente è molto facile descrivere una grammatica piccola seppur complessa come quella di una calcolatrice minimale. In poche righe si è riusciti ad esprimere tutta la potenza di un linguaggio che ci permetterà di elaborare valori numerici. Senza ombra di dubbio una via più veloce che non lo sviluppo manuale di automi in grado di esaudire i nostri desideri (spesso, solo utopia)!!

Il parser

Nella terza e ultima sezione, come anticipato, risiede codice di supporto agli spezzoni associati nelle regola grammaticali, sviluppo di prototipi introdotti nella prima sezione e via dicendo. Se non è presente un analizzatore lessicale esterno sviluppato con altri strumenti (qualcuno ha detto flex?) questa è anche la sezione dove sviluppare la funzione che risponde al prototipo:

int yylex (void);

I lettori più attenti avranno riconosciuto in questo prototipo la funzione già citata che a seguito dell'analisi di un flusso dati in ingresso restituisce una serie di token rappresentanti tale flusso sotto altra forma. Questa funzione deve quindi restituire valori numerici positivi ad indicare il diverso token incontrato oppure un valore nullo o negativo ad indicare la fine dei dati in ingresso. Ovviamente, come detto, tali valori possono essere riferiti anche attraverso i nomi associati (e tradotti in macro) nelle sezioni precedenti; l'aspetto interessante è che se all'interno di regole grammaticali ci si riferisce ad un token attraverso un carattere letterale, questa funzione può restituire direttamente il codice associato a tale carattere il quale sarà automaticamente riconosciuto in modo corretto. Di seguito, un esempio preso dalla documentazione ufficiale che riporta quanto detto sopra:

int
yylex (void)
{
  ...
  if (c == EOF)    /* fine dei dati in ingresso */
    return 0;
  ...
  if (c == '+' || c == '-')
    return c;      /* il tipo del token '+' si suppone essere '+' */
  ...
  return INT;      /* restituzione esplicita del tipo di token */
  ...
}

Per quanto riguarda il valore associato ai diversi token, basti sapere che questo va memorizzato nella variabile yylval prima di ritornare al chiamante il tipo di token incontrato. In realtà, diversi token potrebbero avere anche tipi diversi di dati (interi, virgola mobile, etc.) e questi si possono accedere attraverso una struttura yylval piuttosto che una variabile, previo dichiarazione nella prima sezione di una union apposita. Questo aspetto non è stato preso in considerazione in questa sede anche se, di fatto, si rivela molto importante e utile. Per approfondimenti è consigliato fare riferimento alla documentazione ufficiale.

Un'altra funzione che trova ospitalità in questa sezione e che dovrebbe essere definita, è descritta dal prototipo seguente:

void yyerror (char const *str);

Questa funzione serve per riportare gli errori laddove il parser sviluppato rilevi errori interni o sintattici (come la presenza di token fuori posto). La stringa ricevuta in ingresso descrive più o meno specificatamente l'errore incontrato e spesso, se non si prevedono metodologie di recupero da errori, è sufficiente stampare questa stringa a video e terminare il programma, risultando così in una funzione piuttosto semplice. Questo sarà, per brevità e semplicità, anche il comportamento adottato nel nostro specifico caso (volenti o meno).

Infine, dato che stiamo sviluppando un parser capace di vivere di vita propria, in questa sezione deve essere riportata la funzione main (nota e cara ai programmatori C) dalla quale si richiama una funzione che risponde al prototipo:

int yyparse (void);

Questa altro non è che la funzione che avvia il parsing dei dati in ingresso, valutandoli ed agendo di conseguenza a seconda della grammatica definita e dei dati ricevuti. Da notare che, prima della chiamata, bisogna associare alla variabile yyin un flusso in ingresso da cui leggere tali dati, sia esso la standard input o un file o qualsiasi altra cosa si scelga come fonte. A seguito di questa operazione, sarà eseguito il parsing fino alla fine del flusso o al sollevamento di un errore; terminata l'operazione, è possibile effettuare nuovamente il parsing dei dati associando alla variabile yyin un'altra fonte e chiamando la funzione sopra citata ripetutamente. Va detto, e sarà utile in seguito, che la variabile yyin può non venire impostata, il che porterà ad avere come flusso di ingresso predefinito lo standard input.

Ricollegandoci all'esempio proposto e a quanto detto in quest'ultima parte, si osservi la terza sezione del file di ingresso per Bison riportato di seguito. Da notare che deve essere prima completata la sezione iniziale, aggiornando la precedente come segue:

%{
#define YYSTYPE double

#include <stdio.h>
#include <ctype.h>

int yylex (void);
int yyparse (void);
void yyerror (char const* str);
%}

%token VAL            //     valore numerico

A questo punto, è possibile completare l'analisi della terza sezione:

int
yylex (void)
{
  int c;
  while ((c = getchar ()) == ' ' || c == '\t' || c == '\n');
  if (c == '.' || isdigit (c)) {
    ungetc (c, stdin);
    scanf ("%lf", &yylval);
    return VAL;
  }
  if (c == EOF)
    return 0;
  return c;
}

void
yyerror (char const *str)
{
  fprintf (stderr, "%s\n", str);
}

int
main (void)
{
  return yyparse ();
}

Come accennato nei paragrafi precedenti, si hanno le tre funzioni che descrivono l'analizzatore lessicale, la funzione di stampa degli errori e la funzione principale del programma. Data la semplicità delle ultime due, rimane solo da soffermarsi sulla prima funzione: l'analizzatore lessicale. Infatti la funzione di errore si limita a stampare la stringa passata in ingresso e niente più, oltre al fatto che in questo esempio giocattolo non è prevista alcuna forma di recupero da errori, mentre la funzione principale non fa altro che invocare il parser e aspettare che questo termini. Niente di più facile. Concentriamo l'attenzione, allora, sulla funzione di analisi lessicale.
Come si può vedere, vengono scartati tutti gli spazi bianchi o le tabulazioni presenti, in qualsiasi punto essi si trovino. Si hanno poi tre tipi di valutazione dell'input: nel caso in cui sia incontrato un valore numerico o un punto, questi vengono reinseriti nel flusso di dati in ingresso il quale viene passato in lettura per estrapolare proprio il dato associato (in virgola mobile); nel caso in cui sia incontrato un carattere di fine file, viene ovviamente resa notifica dell'evento al chiamante; in tutti gli altri casi, il carattere incontrato è restituito così com'è, sperando che il chiamante sappia come trattarlo.
Questo è quanto, tutto ciò che serve a fare da supporto per la nostra idea, per la nostra piccola, banale ma esemplificativa calcolatrice tascabile.

Il file parser.y

Il file risultante dal lavoro fatto fino ad ora dovrebbe essere il seguente:

%{
#define YYSTYPE double

#include <stdio.h>
#include <ctype.h>

int yylex (void);
int yyparse (void);
void yyerror (char const* str);
%}

%token VAL            //     valore numerico

%%

expression:  // nessuna operazione
    | expr
    { printf("risultato: %f\n", $$); }
    | expression ';' expr
    { printf("risultato: %f\n", $3); }
    ;

expr: expr '+' term
    { $$ = $1 + $3; }
    | expr '-' term
    { $$ = $1 - $3; }
    | term
    { $$ = $1; }
    ;

term: term '*' value
    { $$ = $1 * $3; }
    | term '/' value
    { $$ = $1 / $3; }
    | value
    { $$ = $1; }
    ;

value: '(' expr ')'
    { $$ = $2; }
    | VAL
    { $$ = $1; }
    ;

%%

int
yylex (void)
{
  int c;
  while ((c = getchar ()) == ' ' || c == '\t' || c == '\n');
  if (c == '.' || isdigit (c)) {
    ungetc (c, stdin);
    scanf ("%lf", &yylval);
    return VAL;
  }
  if (c == EOF)
    return 0;
  return c;
}

void
yyerror (char const *str)
{
  fprintf (stderr, "%s\n", str);
}

int
main (void)
{
  return yyparse ();
}

Supposto che il file sia stato salvato con nome parser.y, mancano pochi elementari passi per arrivare al nostro prodotto finale. Più precisamente:

• digitare il comando bison seguito dal nome del file

• compilare il file parser.tab.c ottenuto a seguito del passo precedente

• eseguire il file parser ottenuto

Ovvero, il tutto si traduce nel comando (da shell):

bison parser.y && gcc -o parser parser.tab.c && ./parser

A questo punto si potrà digitare la nostra espressione fatta di interi, valori in virgola mobile e operatori, terminando la singola espressione con un punto e virgola o, nel caso in cui si voglia uscire dal programma, digitando la combinazione Ctrl+D.

Conclusioni

Come illustrato in questo breve articolo, realizzare analizzatori sintattici per le nostre grammatiche non è cosa poi tanto difficile se si conoscono gli strumenti giusti. In particolare Bison slega lo sviluppatore dai dettagli implementativi e permette di concentrarsi sulla sola grammatica, cosa assai ben più importante. Sicuramente, percorrendo questa via si riuscirà ad ottenere un qualcosa di estremamente efficiente ed allo stesso tempo efficace, cosa assai difficile volendo codificare una automa a mano da zero.

Una cosa appena accennata nel corso di questo articolo è il fatto che Bison può essere combinato con flex, uno strumento che serve per lo sviluppo di analizzatori lessicali. Questi due software sono concepiti per l'interazione e lo sviluppo di analizzatori sintattico/lessicali di qualità e vengono spesso combinati per questo scopo. Quindi, non resta che consigliare di restare in ascolto e documentarsi su come sia possibile un matrimonio fra i due software in cui sia il terzo (lo sviluppatore) a godere.

Ovviamente quanto descritto in queste poche righe non è che la punta dell'iceberg di un software dalle grandi possibilità, quindi si consiglia di non soffermarsi a questo articolo ma piuttosto fare riferimento alla documentazione ufficiale per scoprire come fare cosa e realizzare i propri analizzatori sintattici personalizzati.

Riferimenti bibliografici

[1] Bison, documentazione ufficiale
http://www.gnu.org/software/bison/manual/html_mono/bison.html

[2] Compiler Construction using Flex e Bison,
Anthony A. Aaby, Walla Walla College, April 22, 2005

[3] Basic of Compiler design,
Torben Mogensen, University of Copenhagen, April 25, 2007

<- flex: Fast Lexical Analyzer - Indice Generale - Copertina - Server Side Java - parte 2 ->