Bison

Bison on programm kontekstivabadele grammatikatele süntaksianalüsaatorite loomiseks. Bisoni sisendiks on kontekstivaba grammatika (transleeeritava programmeerimiskeele süntaksit kirjeldav grammatika): reeglid (produktsioonid), mitteterminalid (grammar groupings) ja terminalid (tokens). Nende põhjal genereerib Bison selle grammatika jaoks süntaksianalüsaatori, s.t. C-keeles kirjutatud programmi, mis iga selle grammatika poolt genereeritud sõna (programmeerimiskeeles kirjutatud programmi) jaoks leiab selle sõna derivatsioonipuu. Grammatika reeglitega saab siduda semantilisi tegevusi, seega on võimalik genereerida (näiteks) programeerimiskeele interpretaator või translaator.

Grammatika kirjeldus tuleb Bisonile esitada formaadis, mis meenutab Flex-i sisendit.

%{
C deklaratsioonid
%}
Bisoni deklaratsiooonid
%%
Grammatika reeglid
%%
Täiendav C-keelne programmiosa

Esimeses eraldajate %{, %} vahelises C deklaratsioonide osas defineeritakse muutujad ja makrod, mida hiljem kasutatakse grammatika reeglitele lisatud semantilistes tegevustes. Need deklaratsioonid kopeerib Bison genereeritava programmi algusesse; kui midagi pole deklareerida, võib eraldajad %{, %} ära jätta.

Bisonile esitatava grammatika terminalid (tokens) on skanneri (leksilise analüsaatori) poolt leitud lekseemid. Need esitatakse Bison-ile võtmesõna %token järel ja nad tuleb kirjutada suurtähtedega. Terminalidena võib kasutada ka tekstikonstante (need kirjutatakse nagu c-keele literalid): '+', '*' jne.

Grammatika mitteterminalid kirjutatakse väiketähdedega; neid eraldi ei loetleta, Bison tunneb nad ära grammatikareeglitest. Grammatika algussümboliks loetakse (vaikimisi) esimeses reeglis vasakul olev mitteterminal.

Vaatleme väikest näidet: interpretaatorit, mis arvutab sisestatud matemaatilise avaldise väärtuse. Avaldises kasutatakse vaid täisarve ja liitmist-lahutamist ja ta on määratud grammatikaga

sisend read #
read read rida | rida
rida   | avaldis ARVUTA
avaldis ARV | avaldis + ARV | avaldis - ARV |

Esimene reegel lubab kuitahes mitu rida; real on avaldis, kuid rida võib olla ka tühi; avaldise väärtus väljastatakse lekseemi (terminali) ARVUTA lugemisel (selle genereerib reavahetus sisendtekstis); sümbol # on töö lõpetamiseks.

Defineerime algul leksilise analüsaatori:

%option noyywrap
%{
%}
digit [0-9]
tyhikud [ |\t]
%%
"+" return(PLUS);
"-" return(MIINUS);
"\n" return(ARVUTA); /*rea lõpp - kalkulaator peab väljastama tulemuse */
{digit}+ return(ARV); /* täisarv */
{tyhikud} { }; /* tühikud ja tabulatsiooonimärgid real kustutatakse */
"#" return (KOIK); /* töö lõpetamiseks */
. return(VIGA);
%%
/* siin ei toimu midagi, peaprogramm on bison-i failis */

Selle teksti põhjal genereerib Flex leksilise analüsaatori teksti lex.yy.c, mis asendab sisendtekstis arvud lekseemiga ARV, märgid +, -, # vastavalt lekseemidega PLUS, MIINUS, KOIK ja reavahetused - lekseemiga ARVUTA (see on käsk real oleva avaldise väärtuse väljastamiseks)

Bisoni sisendtekstis calc.y muutub Flex-i poolt selle kirjelduse alusel genereeritud leksikaanalüsaatori C-keelne tekst lex.yy.c include-failiks:

%{
#include "lex.yy.c"
#include <stdio.h>
#include <math.h>
#define YYSTYPE int /* kõigi mitteterminalide tüüp tulen int */
%}

//Loetleme kõik terminalid (Flex-i lekseemid) :
%token PLUS MIINUS ARV ARVUTA VIGA KOIK

%left MIINUS PLUS /* määrame assotsiatiivsuse - kui järjest on mitu operatsiooni, algab nende sooritamine vasakult */

%%
/*järgnevad grammatika produktsioonid */ sisend: sisend avaldis ARVUTA { printf("Tulemus: %d\n",$2); }
| /* tühi rida */ ;
arv: ARV {$$ = atoi(yytext); /* numbrite jada teisendamine täisarvuks */}
avaldis: arv { $$=$1; /* printf("Integer: %d\n",atoi(yytext));*/}
| avaldis PLUS arv { $$ = $1 + $3; /* printf("Liitmine: %d = %d + %d\n",$$,$1, $3);*/ } | avaldis MIINUS arv { $$ = $1 - $3;/* printf("Lahutamine: %d = %d - %d\n",$$,$1, $3); */ } | KOIK { printf("Valmis.\n");return 0;} // return 0 lõpetab töö | ;

%%

yyerror(char *str)
{
printf("Viga: %s kohal %s\n",str,yytext);
/*exit(1);*/ }

main()
{
yyparse();
}

Siin loetletakse algul lekseemid (reserveeritud sõna %token järel) ja määratakse kõigi arvväärtust omavate lekseemide tüübiks int. Seejärel on loetletud grammatika reeglid (produktsioonid); produktsioonide tavalises kirjaviisis kasutatava asemele tuleb koolon : . Reeglid kirjeldatakse koos reeglile vastava semantilise tegevusega, mis on kirjeldatud figuursulgude { } vahel. Reeglile vastavas tegevustes on reeglis esinevate sümbolite (terminalide ja mitteterminalide) väärtused (vasakult paremale) tähistatud $$, $1, $2,.... Seega näiteks reeglis

avaldis : avaldis PLUS arv

arv: ARV { $$ = atoi(yytext); }

tähendab, et produktsiooni vasakul pool oleva mitteterminali arv väärtus saadakse paremal pool olevale lekseemile ARV vastava teksti yytext teisendamisel täisarvuks; mitteterminal arv on sisse toodud vaid selleks, et seda teisendust poleks vaja kirjeldada kõigis produktsioonides.

Reegli

avaldis: avaldis PLUS avaldis { $$ = $1 + $3; }

Kui ülalesitatud Bison-i sisendtekst on salvestatud näiteks failis calc.y, siis käsk

bison calc.y

gcc calc_tab.c -ocalc

saame faili calc.exe. Selle testimiseks võib kasutada näiteks faili calc_in.txt:

2+3-1
2-4-6
4
#

Kui käivitada calc.exe selle sisendiga

calc < calc_in.txt > calc_out.txt

tekib väljundfailis calc_out.txt järgmine tekst:

Tulemus: 4
Tulemus: -8
Tulemus: 4
Valmis.

Küsimused, probleemid: ©2004 Jaak Henno