Flex+Bison: poola kuju kasutav kalkulaator

Järgnevas on veidi suurem näide - reaalarvudega arvutav kalkulaator, milles kasutatakse nn "tagurpidi poola kuju" (reverse Polish notation) poola matemaatiku Jan Lukasiewicz-i järgi, kes selle aastal 1920 kasutusele võttis. Tagurpidi poola kujul kirjutatakse matemaatilised operatsioonid lõppjärjestuses: algul operandid ja siis operaator, seega näiteks 2+3 asemel kirjutatakse 2 3 + ja 6 - (2 * 3) esitatakse kujul 6 2 3 * - . Sellisel kirjaviisil on tavalise nn keskjärjestuses (inorder - operaator on operandide vahel) palju eeliseid: operatsioonide prioriteedi kirjeldamiseks pole sulge tarvis, kui valemi liikmed salvestada järjest (vasakult paremale lugedes) magasinis, on arvutuste vahetulemused kohe näha ja nende salvestamiseks pole tarvis lisamälu. Sellepärast on poola kuju kasutavad kalkulaatorid (HP kalkulaatorid) palju kiiremad kui tavalised (kui muud omadused on samaväärsed). Ka translaatorites arvutatakse arimeetiliste avaldiste väärtus, lugedes avalist tagurpidi poola kujul; protsessoritel on magasinmälu selliselt esitatud avalsite arvutamiseks.

Realiseerime järgnevas Flex-i ja Bison-i abil tagurpidi poola kuju kasutava reaalarvudega arvutava kalkulaatori. Kalkulaator peab arvutama järjest eraldi ridadel antud reaalarve sisaldavate avaldiste väärtused, väljastates iga rea järel tulemuse. Vea korral sisendis väljastab kalkulaator vigase rea numbri ja jätkab tööd. Et Bison ei peaks ise hakkama reanumbreid loendama, kasutame Flex-i ja Bisoni globaalmuutujat yylineno, mille väärtuseks on käsitletava rea number; muutuja yylineno väärtustab Flex, kui programmi alguses on rida %option yylineno. Operaatoritele vastavateks lekseemideks kasutame operaatorite endi märke literalidena (literalieraldajate '  ' vahel) - see teeb Bison-i sisendi testimise lihtsamaks. Unaarse miinuse (arvu või avaldise ees oleva miinuse, mitte lahutamistehte) eristamiseks kasutame selle tähistamiseks tähte n (selle ees peab olema tühik !); vastav terminal on 'n'. Seega Flex-i sisendfail on järgmine:

%option noyywrap
%option yylineno

DIGIT [0-9]
ID [A-Z][A-Z0-9]*

%%
"+" return ('+'); /*printf("Plus\n"); */
"-" return ('-'); /* printf("Miinus\n"); */
"*" return ('*'); /* printf("Korda\n"); */
"/" return ('/'); /* printf("Jagamine \n"); */
"^" return ('^');
" n" return ('n'); /* unaarne miinus */
"\n" return('\n');
{DIGIT}+("."{DIGIT}*)? return(ARV); /* arvus võib olla ka punkt
{DIGIT}+ return(ARV);
[ \t]+ { }; /* tyhikud ja tabulatsiooonimärgid real kustutatakse */

%%

Bisoni sisendi algul deklareerime reaga #define YYSTYPE double kõigi terminalide (ARV) ja mitteterminalide semantilise väärtuse tüübiks double. Kalkulaatori sisend koosneb ridadest; iga rea lõpul kalkulaator väljastab reanumbri ja real esitatud avaldise väärtuse; kuna väljastamiskäsuni jõudmisel on reavahetus \n juba loetud, on väljastamise hetkel muutuja yylineno õigest väärtusest ühe võrra suurem, sellepärast peab väljastamiskäsus kasutama avaldist yylineno-1. Et kalkulaator vea korral mingis reas tööd ei katkestaks, on rea alternatiiviks ka error (see on Bison-i sisendkeele võtmesõna ja seda võib produktsioonides kasutada). Väljend error \n tähistab kogu rida, millel viga leiti; sellele vastav semantiline tegevus on yyerrok - see on Bison-i makro, mis hülgab kogu sellel real loetu ja jätkab sisendi lugemist järgmiselt realt. Kuid funktsioon yyerror käivitatakse (automaatselt, iga vea puhul) ja see väljastab vigase rea numbri.

/* poola kujul valemite kalkulaator*/
%{
#define YYSTYPE double /* käik arvud ja avaldised on reaalarvud */
#include <stdio.h>
#include <math.h>
#include <ctype.h>
#include "lex.yy.c"
%}

%token ARV
%%
/* järgnevad grammatikareeglid */ sisend: /* tyhi */
| sisend rida ;
rida: exp '\n' { printf ("Rida %d: \t %f\n", yylineno-1, $1); }
| error '\n' { yyerrok; /* töö peab jätkuma! */}
| '\n' /*tyhi rida */ ;
exp:   ARV { $1 = atof(yytext); $$ = $1; /* numbrite jadast tehakse reaalarv */ }
| exp exp '+' { $$ = $1 + $2; }
| exp exp '-' { $$ = $1 - $2; }
| exp exp '*' { $$ = $1 * $2; }
| exp exp '/' { $$ = $1 / $2; }
| exp exp '^' { $$ = pow ($1, $2); /* astendamine */}
| exp 'n' { $$ = -$1; /* unaarne miinus */ } ;
%%

main ()
{
yyparse (); }
yyerror (s) /* käivitatakse vea korral */
char *s;
{
printf ("Viga %s rida: %d\n", s,yylineno); }

Kalkulaatori katsetamiseks loome sisendfaili test.txt; sisendis on kasutatud reaalarvu erinevaid kujusid (.3, 5., 5.4), unaarset miinust, mitmesuguseid operatsioone ja kus on ka kaks vigast rida, et testida kalkulaatorit veast ülesaamisel:

2 0.3 +
2 2 ^ 3 3 * +
5.0 2 + 3 n -
5.4 + 3.7
2.3 1.2 ^
23 - 3
2 3 +

Käivitame käskudega (ülalesitatud leksikaanalüsaator on salvestatud failis lex.l, süntaksianalüsaator - failis rpcalc.y):

flex lex.l
bison rpcalc.y
gcc rpcalc.tab.c -ocalc
calc < test.txt > tulemus.txt

Rida 1: 2.300000
Rida 2: 13.000000
Rida 3: 10.000000
Viga syntax error rida: 4
Rida 5: 2.716898
Viga syntax error rida: 6
Rida 7: 5.000000

Eelnenud näites oli kõigi arvude tüüp double, kuid sageli on tarvis erinevaid tüüpe: int, float, string jne. . Kui näiteks eelnevas tahetakse sisendis täisarvu kujul (ilma punktita) kirjutatud arvude tüübiks deklareerida int, tuleb need Flex-programmis kirjeldada erineva lekseemiga, s.t. ülalesitatud Flex-programmi  rida {DIGIT}+ return(ARV); tuleks asendada reaga :

{DIGIT}+ return(TARV);

Bison-i sisendis peab mitme tüübi kasutamiseks kõik kasutatavad andmetüübid programmi algul defineerima ühendina (union), s.t. rida #define YYSTYPE double tuleb asendada ühendi deklaratsiooniga; kuna see on Bison-i deklaratsioon, tuleb see kirjutada pärast C-deklaratsioonide lõppu (s.t. C-deklaratsioone lõpetava %} järele):

%union {
double rval;
int ival;
}

%token ARV TARV
%type <ival> TARV
%type <rval> ARV
%type <rval> exp

Kuna avaldised (neid tähistab mitteterminal exp) on tavaliselt samuti reaalarvud, on ka nende tüüp määratud reaalarvuks.

Mitteterminali exp kirjeldusse tuleb lisada võimalus ka uue lekseemi TARV jaoks:

exp:     TARV {$1 = atoi(yytext); $$ = $1;}

Kui tahetakse kasutada ka kompleksarve, võib need esitada (näiteks) lekseemina ARV1iARV2, kus ARV1, ARV2 on kas täis- või reaalarvud, s.t.lekseem on Flex-i sisendis kirjeldatud regulaarse avaldisega:

KARV ({NUM1}|{NUM})"i"({NUM}|{NUM1})

{KOMPLEKS} return(KARV);

Bison-i sisendis on kompleksarvude tüüp kirjeldatud stuktuurina, milles salvestatakse (reaalarvudena) täis- ja reaalosa:

%union {
    float fval;
    int ival;
    struct {
     float real;
     float kompl;
    } cval;
}

Lekseem KARV tuleb lisada Bison-i sisendis lekseemide lotelule; tema tüüp määratakse reaga

%type <cval> KARV

exp:    KARV {$$.real = atof(yytext); $$.kompl = atof(strchr(yytext, 'i')+1);}

Küsimused, probleemid: ©2004-2013 Jaak Henno