YACC può analizzare flussi in input consistenti in categorie (token) con certi valori. Si vede qui chiaramente la relazione fra YACC e Lex, YACC non ha alcuna idea di cosa i 'flussi in input' siano, ha necessità di categorie preprocessate. Anche se è possibile scrivere un proprio analizzatore di categorie, qui si lascerà questo compito esclusivamente a Lex.
Una nota sulle grammatiche e sugli analizzatori sintattici. Quando YACC vide la luce, era uno strumento usato per analizzare i file in input ai compilatori: i programmi. I programmi scritti in un linguaggio di programmazione per computer sono tipicamente *non* ambigui - hanno un significato univoco. Per questo motivo, YACC non riesce a fare fronte ad ambiguità e si lamenterà di conflitti spostamento/riduzione o riduzione/riduzione. Qualcosa di più a riguardo di ambiguità e di "problemi" di YACC può essere trovato nel capitolo 'Conflitti'.
Supponiamo di avere un termostato che si vuole controllare usando un semplice linguaggio. Una sessione con il termostato potrebbe essere di questo tipo:
riscaldamento acceso
Riscaldamento acceso!
riscaldamento spento
Riscaldamento spento!
obiettivo temperatura 22
Nuova temperatura impostata!
Le categorie (token) che dobbiamo essere in grado di riconoscere sono: riscaldamento, acceso/spento (STATO), obiettivo, temperatura, NUMERO.
L'individuazione dei simboli di Lex avviene (Esempio 4) secondo:
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+ return NUMERO;
riscaldamento return TOKRISCALDAMENTO;
acceso|spento return STATO;
obiettivo return TOKOBIETTIVO;
temperatura return TOKTEMPERATURA;
\n /* ignora fine linea */;
[ \t]+ /* ignora spazi bianchi */;
%%
Si notano due cambiamenti importanti. Primo, viene incluso il file 'y.tab.h', e in secondo luogo, non viene stampato nulla, vengono restituiti i nomi delle categorie. Questo cambiamento è necessario perché si passerà tutto a YACC che si disinteressa di quello che viene stampato sullo schermo. y.tab.h contiene le definizioni di queste categorie.
Ma da dove proviene y.tab.h? Viene generato da YACC dal file di grammatica che si è in procinto di creare. Visto che il linguaggio è molto semplice, lo stesso vale per la grammatica:
comands: /* vuoto */
| comandi comando
;
comando:
interruttore_riscaldamento
|
imposta_obiettivo
;
interruttore_riscaldamento:
TOKRISCALDAMENTO STATO
{
printf("\tRiscaldamento acceso o spento\n");
}
;
imposta_obiettivo:
TOKOBIETTIVO TOKTEMPERATURA NUMERO
{
printf("\tTemperatura impostata\n");
}
;
La prima parte è quella che io chiamo la 'radice' ('root'). Stabilisce che ci sono dei 'comandi', e questi comandi sono composti da comandi singoli, ognuno dei quali è un 'comando'. Come si vede questa regola è molto ricorsiva, perché contiene anche la parola 'comandi'. Il che significa che il programma è in grado di ridurre una serie di comandi uno a uno. Per dettagli importanti sulla ricorsività leggere il capitolo 'Come lavorano internamente Lex e YACC'.
La seconda regola definisce che cosa è un comando. Noi supportiamo solo due tipi di comandi, un 'interruttore_riscaldamento' e un 'imposta_obiettivo'. Questo è quello che significa il simbolo | (or) - 'un comando consiste o di un interruttore_riscaldamento o di un imposta_obiettivo'.
Un interruttore_riscaldamento consiste nella categoria RISCALDAMENTO, che è semplicemente la parola 'riscaldamento', seguita da uno stato (che si è definito nel file di Lex come 'acceso' e 'spento').
In qualche modo più complicato è imposta_obiettivo, che consiste della categoria OBIETTIVO (la parola 'obiettivo'), la categoria TEMPERATURA (la parola 'temperatura') e un numero.
La sezione precedente ha mostrato solo la parte di grammatica del file per YACC, ma c'è di più. È la testata che abbiamo omesso:
%{
#include <stdio.h>
#include <string.h>
void yyerror(const char *str)
{
fprintf(stderr,"errore: %s\n",str);
}
int yywrap()
{
return 1;
}
main()
{
yyparse();
}
%}
%token NUMERO TOKRISCALDAMENTO STATO TOKOBIETTIVO TOKTEMPERATURA
%%
La funzione yywrap() può essere usata per continuare a leggere da un ulteriore file. Viene richiamata alla fine di un file e si può allora aprire un altro file e restituire 0. Oppure si può restituire 1, indicando così che questa è effettivamente la fine di tutti i file di input. Per maggiori informazioni su questo, vedere il capitolo 'Come lavorano internamente Lex e YACC'.
Infine c'è la funzione main(), che non fa nulla se non mettere tutto in movimento.
L'ultima linea definisce semplicemente le categorie che verranno usate. Queste vengono prodotte nel file di output y.tab.h se YACC è richiamato con l'opzione '-d'.
lex esempio4.l
yacc -d esempio4.y
cc lex.yy.c y.tab.c -o esempio4
NOTA: nel caso otteniate un errore legato al fatto che il compilatore non è in grado di
trovare 'yylval' aggiungere in esempio4.l, appena sotto #include <y.tab.h>,
questa riga:
extern YYSTYPE yylval;
Per spiegazioni, vedere la sezione 'Come lavorano internamente Lex e YACC'.
Una sessione di esempio:
$ ./esempio4
riscaldamento acceso
Riscaldamento acceso o spento
riscaldamento aspento
Riscaldamento acceso o spento
obiettivo temperatura 10
Temperatura impostata
obiettivo umidità 20
errore: syntax error
$
Non è proprio quello che si voleva ottenere, ma per mantenere abbordabile la curva di apprendimento non si possono presentare tutte in una volta le belle cose che si possono fare.
Come si è visto, ora i comandi del termostato vengono analizzati correttamente e pure gli errori vengono individuati in modo appropriato. Ma come si può indovinare dalla formulazione ambigua, il programma non ha alcuna idea di quello che dovrebbe fare, non gli viene passato nessuno dei valori inseriti.
Cominciamo con aggiungergli la capacità di leggere il nuovo obiettivo di temperatura. Per fare questo, si deve insegnare alla corrispondenza NUMERO nell'analizzatore sintattico (Lexer) come convertirsi in un valore intero che possa poi essere letto da YACC.
Quando Lex trova una corrispondenza dell'obiettivo mette il testo della corrispondenza trovata nella stringa di caratteri 'yytext'. YACC a sua volta si aspetta di trovare un valore nella variabile 'yylval'. Nell'Esempio 5, vediamo l'ovvia soluzione:
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+ yylval=atoi(yytext); return NUMERO;
riscaldamento return TOKRISCALDAMENTO;
acceso|spento yylval=!strcmp(yytext,"acceso"); return STATO;
obiettivo return TOKOBIETTIVO;
temperatura return TOKTEMPERATURA;
\n /* ignora fine linea */;
[ \t]+ /* ignora spazi bianchi */;
%%
Come si vede, si esegue un atoi() su yytext, e si mette il risultato in yylval, da dove YACC può utilizzarlo. Si fa qualcosa di molto simile per la corrispondenza di STATO, che viene paragonato a 'acceso', e si imposta yylval a 1 se viene trovato uguale. Va notato che separando le corrispondenze di 'acceso' e 'spento' Lex produrrebbe un codice più veloce, ma si vuole qui mostrare una regola e una azione più complicata, tanto per cambiare.
Si deve insegnare a YACC come comportarsi in questo caso. Quello che viene chiamato 'yylval' in Lex ha un nome differente in YACC. Esaminiamo la regola che imposta il nuovo obiettivo di temperatura:
imposta_obiettivo:
TOKOBIETTIVO TOKTEMPERATURA NUMERO
{
printf("\tTemperatura impostata a %d\n",$3);
}
;
Per accedere al valore della terza parte della regola (cioè NUMERO), è necessario usare $3. Al termine dell'esecuzione di yylex(), i contenuti di yylval vengono resi disponibili al terminale, e a quei valori si può accedere con il costrutto $.
Per spiegare ulteriormente la cosa si osservi la nuova regola 'interruttore_riscaldamento':
interruttore_riscaldamento:
TOKRISCALDAMENTO STATO
{
if($2)
printf("\tRiscaldamento acceso\n");
else
printf("\tRiscaldamento spento\n");
}
;
Se ora si esegue esempio5 darà in output correttamente quello che si inserisce.
Rivediamo una parte del file di configurazione usato precedentemente:
zone "." {
type hint;
file "/etc/bind/db.root";
};
Si ricordi che si è già scritto un Analizzatore lessicale (Lexer) per questo file. Tutto quello che ora è necessario fare è scrivere una grammatica per YACC, e modificare l'Analizzatore lessicale così che restituisca valori in un formato adatto a YACC.
Nell'Analizzatore lessicale dall'Esempio 6 si vede:
%{
#include <stdio.h>
#include "y.tab.h"
%}
%%
zone return ZONETOK;
file return FILETOK;
[a-zA-Z][a-zA-Z0-9]* yylval=strdup(yytext); return PAROLA;
[a-zA-Z0-9\/.-]+ yylval=strdup(yytext); return NOMEFILE;
\" return DOPPIOAPICE;
\{ return APERTAGRAFFA;
\} return CHIUSAGRAFFA;
; return PUNTOEVIRGOLA;
\n /* ignora fine linea */;
[ \t]+ /* ignora spazi bianchi */;
%%
Se si osserva attentamente si può vedere che yylval è cambiato! Non ci si aspetta più che sia un numero intero, ma in effetti si assume che sia un char *. Per amor di semplicità si è invocato strdup sprecando molta memoria. Si noti che ciò può non essere un problema in molti casi dove è solo necessario analizzare un file una volta e poi uscire.
Si vogliono memorizzare stringhe di caratteri perché qui si ha a che fare principalmente con nomi: nomi di file e nomi di zone. In un capitolo successivo si spiegherà come trattare dati di tipi differenti.
Per informare YACC riguardo al nuovo tipo di yylval, va aggiunta questa linea alla testata della grammatica di YACC:
#define YYSTYPE char *
La grammatica in sé è ancora più complicata. La vediamo a piccole dosi per renderla più facilmente digeribile.
comandi:
|
comandi comando PUNTOEVIRGOLA
;
comando:
imposta_zone
;
imposta_zone:
ZONETOK nomefradoppiapici contenutozone
{
printf("Zone completa trovata per '%s'\n",$2);
}
;
Questa è l'introduzione, inclusa la 'radice' ricorsiva già menzionata più sopra. Notare che si è specificato che i comandi sono terminati (e separati) da ";". Si è definito un tipo di comando, 'imposta_zone'. Consiste della categoria ZONETOK (la parola 'zone'), seguita da un nome racchiuso tra doppi apici e 'contenutozone'. Questo contenutozone comincia in modo abbastanza semplice:
contenutozone:
APERTAGRAFFA dichiarazionizone CHIUSAGRAFFA
È necessario che cominci con una APERTAGRAFFA, una {. Poi segue una dichiarazionizone, seguita da una CHIUSAGRAFFA, }.
nomefradoppiapici:
DOPPIOAPICE NOMEFILE DOPPIOAPICE
{
$$=$2;
}
Questa sezione definisce cosa sia un 'nomefradoppiapici': è un NOMEFILE tra due DOPPIOAPICE. Poi dice qualcosa di speciale: il valore di un simbolo di tipo nomefradoppiapici è il valore del NOMEFILE. Questo significa che nomefradoppiapici ha come suo valore il valore di filename senza i doppi apici.
Questo è quello che il comando magico '$$=$2;' fa. Dice: il mio valore è il valore della mia parte seconda. Quando si fa riferimento a nomefradoppiapici in altre regole e si accede al suo valore con il costrutto $, si vede il valore che si è impostato qui con $$=$2.
NOTA: questa grammatica s'inceppa con nomi di file che non contengono né un '.' né
una '/'.
dichiarazionizone:
|
dichiarazionizone dichiarazionezona PUNTOEVIRGOLA
;
dichiarazionezona:
dichiarazioni
|
FILETOK nomefradoppiapici
{
printf("Nome di file zone '%s' trovato\n",$2);
}
;
Questa è una dichiarazione generica che intercetta tutti i tipi di dichiarazione all'interno del blocco 'zone'. Notiamo ancora la ricorsività.
blocco:
APERTAGRAFFA dichiarazionizone CHIUSAGRAFFA PUNTOEVIRGOLA
;
dichiarazioni:
| dichiarazioni dichiarazione
;
dichiarazione: PAROLA | blocco | nomefradoppiapici
Questo definisce un blocco e le 'dichiarazione' che vi si possono trovare.
Quando viene eseguito il risultato in uscita appare come:
$ ./esempio6
zone "." {
type hint;
file "/etc/bind/db.root";
type hint;
};
Nome di file zone '/etc/bind/db.root' trovato
Zone completa trovata per '.'