Torna alla pagina di Traduttori
Sintassi Bison - YACC
La sintassi per segnare commenti etc. è simile a quella di flex:
definizioni
regole
subroutine
Qui, avremo regole diverse e sub obbligatorie diverse:
Al solito, o le definiamo noi, oppure linkiamo con -ly, anche se qui in laboratorio non si riesce.
Regole
L'idea è simile: si scrive la regola e poi segue l'azione.
Ad esempio, vogliamo scrivere le regole di una grammatica così:
A-> αBγ | δμγ
Si traduce in questo modo:
A: α B γ { action }
| δ μ γ
;
Generare un parser
Non è obbligatorio scrivere un programma da Flex-are per poter poi usarlo col parser: sono due cose indipendenti, anche se poi sarà più comodo usare uno scanner generato da flex piuttosto che scriverlo noi.
In input ho:
bim bum bam
e tradurlo in
qui quo qua
La prima sezione è scritta così:
%start frase
Il simbolo % viene usato per dare comandi a Bison, e in questo caso il comando%start dice qual'è il simbolo iniziale della grammatica. Non è necessario scriverlo: Bison sceglie automaticamente la prima regola.
Vogliamo riconoscere solo bim bum bam e NON bam bum bim o altre combinazioni. Certo, banalmente posso fare un riconoscitore che riconosca direttamente la stringa (frase : bim bum bam), ma sarebbe stata una regola lessicale e non sintattica. Invece noi vogliamo usare i token.
La frase ha quindi un inizio ed una fine, separati da uno spazio vuoto. Andando avanti, definisco come sono fatti sti token.
frase : inizio ' ' ultimo {printf("\nAssioma riconosciuto:
la frase fa parte del linguaggio\n");}
inizio : primo ' ' medio
;
primo : bim
;
medio : bum
;
ultimo : bam
;
bim : 'b' 'i' 'm' {printf("qui");}
bum : 'b' 'u' 'm' {printf("quo");}
bam : 'b' 'a' 'm' {printf("qua");}
int yylex()
{
char ch = getchar();
return (int) ch;
}
int yyerror (char*s)
{
printf("\n %s \n", s);
return 1;
}
int main()
{
yyparse();
return 0;
}
Le ultime funzioni serve per far sì che il programma funzioni anche senza tirare in ballo i files generati da Flex. yylex viene chiamata automaticamente da yyparse, la quale è chiamata automaticamente dalle librerie di Bison. La yyerror server per quando viene trovato un errore sintattico. Le viene passato il carattere reo.
Per compilare:
bison file.y
Poi si compila con gcc.
Quando viene eseguito il parser, prima riconosce (o no) il tutto, e alla fine te lo dice.
Eserczio
Vogliamo che riconosca anche stringhe con più spazi tra una parola e l'altra. Senza usare la sintassi di Flex, scrivo una regola ricorsiva che possa riconoscere più spazi.
frase : inizio spazio ultimo
...
spazi : ' '
| spazi ' '
Ocio: qui ho definito il token spazi. Se per caso in frase non avessi scritto quello che ho scritto sopra, ma avessi scritto questo:
frase : inizio ' ' ultimo
avrei avuto la regola spazi irraggiungibile. Bison però è un bravo ragazzo: compilando, mi direbbe che c'è un non terminale inutile, e due regole inutili (infatti spazi ha una | in mezzo).
Se poi a Bison do l'opzione -v, diventa verboso e mi dice tutto. Crea un file con estensione .output che contiene tutto quello che mi serve, compreso l'automa che ha generato.
Per evitare di scrivere i simboli terminali nelle regole, li posso far leggere al mio scanner. In questo caso, si tratta della funzione yylex.
Ad esempio, una regola sarebbe:
primo : BIM
con BIM definito nelle dichiarazioni:
%token BIM BUM BAM
Nella yylex, avrei cose come:
int yylex()
{
char str[255];
int t;
t = scanf("%s", str);
if (t != 1) return 0;
if (strcmp(str, "bim") == 0)
return BIM
else if (strcmp(str, "bum") == 0)
return BUM
else if (strcmp(str, "bam") == 0)
return BAM
}
La dichiarazione %token crea dei #define automatici, che associano dei numeri a BIM, BUM e BAM, e li mette in un .h.
Per compilare, stavolta utilizzo l'opzione -d. Quando compilo con gcc, viene usato anche il .h in cui i token sono stati definiti.
Combinare Flex e Bison
Nel file di Flex, devo semplicemente mettere, nelle dichiarazioni, l'#include necessario:
%{
#include "parserblabla.tab.h"
}%
"bim" { return BIM; }
int yywrap()
{
return 1;
}
Ovviamente, il main dei due files deve essere unico, e sarà quello del parser. Infatti è il parser che chiama il lexer, e non viceversa. Inoltre, nel file di Bison non occorre più mettere la yylex, perché viene generata automaticamente da Flex.
Per riconoscere spazi multipli, adesso posso ricorrere a Flex. Flex di default quando trova un match lo stampa nell'output. Ma posso scrivere una regola così:
[ ]+ ;
che vuol dire che non ritorno nulla a Bison.
Riconoscere un linguaggio
Vogliamo riconoscere un linguaggio semplice, con poche parole chiave, che rappresenta il controller di un termostato. Accetta solo ste robe:
heat on
heat off
target temperature value
dove valure è il valore numerico della temperatura.
Distinguiamo regole lessicali da regole sintattiche, usando Flex e Bison e combinandoli.
Regole lessicali
Le parole heat, on, off, target, temperature, numero sono gli unici lessemi validi. L'analisi lessicale dovrà riconoscere solo queste parole.
Per questo scopo, utilizzo Flex. Ogni volta che trovo una parola valida, devo ritornare un token.
{%
#include "header di bison.h"
%}
[0-9]+ return NUMBER;
heat return TOKHEAT;
on|off return STATE;
target return TOKTARGET;
temperature return TOKTEMPERATURE;
\n ;
[ \t]+ ;
int yywrap()
{
return 1;
}
Regole sintattiche
Si occupa di come le robe lette siano ben combinate secondo le regole sintattiche del mio linguaggio.
%{
#include "stdio.h"
#include "string.h"
}%
%token NUMBER TOKHEAT TOKSTATE TOKTARGET TOKTEMPERATURE
commands : /* vuota! */
| commands command
;
command : heat_switch
| target_set
;
heat_switch : TOKHEAT STATE { printf("Heat turned on or off\n"); }
;
target_set : TOKTARGET TOKTEMPERATURE NUMBER
{
printf("Temperature set\n");
}
;
void yyerror (const char * str)
{
fprintf(stderr, "%s", str);
}
int main()
{
yyparse();
return 0;
}
Compilare il tutto
Do in input a Flex il suo .l. A Bison do il .y, aggiungendo l'opzione -d così che mi generi il .h necessario. Poi compilo con gcc:
gcc termostato.tab.c lex.yy.c -o termostato.exe
Esercizio
Se scrivo heat on, voglio che mi dica "hai ACCESO", se scrivo heat off deve dirmi "hai SMORSATO"
Devo avere come minimo due token, TOKON e TOKOFF, e quindi modificare l'analizzatore lessicale, e poi anche quello sintattico. In Flex avrò:
on return STATEON;
off return STATEOFF;
e sintatticamente avrò:
% token ... TOKON TOKOFF ...
...
heat_switch : TOKHEAT TOKON { ... } | TOKHEAT TOKOFF { ... };
Ma c'è un'altra via: alla fine, al parser non interessa sapere l'esatta sequenza di comandi, ma solo l'istruzione "accendi" o "spegni". Posso sfruttare il fatto che Flex e Bison possono comunicare tramite la variabile yylval.
In Flex:
on|off yylval = strcmp(yytext, "off"); return STATE;
Infatti, la strcmp ritorna 0 se le stringhe sono uguali.
In Bison:
heat_switch : TOKHEAT STATE
{
if ($2) printf ("Heat ON\n");
else printf("Heat OFF\n");
};
Perché $2? Perché il valore che mi interessa è quello che viene ritornato dal SECONDO token, che è appunto STATE.
Allo stesso modo, posso recuperare, nel parser, la temperatura:
target_set : TOKTARGET TOKTEMPERATURE NUMBER
{
printf("Impostata la temperatura a %d\n", $3):
};
avendo avuto cura, in Flex, di avere una regola così:
[0-9]+ { return atoi(yytext); }
che appunto converte la variabile yytext, che ricordiamo essere la stringa matchata, in numero.
Attenzione la notazione $i conta, nella parte destra della regola, sia i terminali che i non terminali! Ad esempio:
(TOKEN)
vuol dire:
- $1 = (
- $2 = TOKEN
- $3 = )
Esercizio
Frase = Soggetto Verbo Complemento
Soggetto = articolo [nome comune | nome proprio]
Torna alla pagina di Traduttori
