Flex+Bison

Transleerimise järgmine etapp on süntaksianalüüs. Selle käigus koostatakse skanneri (leksilise analüsaatori) väljundi (lekseemide jada + nimede tabel) ja transleeritava keele süntaksigrammatika põhjal transleeritava programmi süntaksi puu. Ka selle transleerimise etapi sooritamiseks on olemas programmid, mis koostavad sisendi (skanneri väljund + keele grammatika) põhjal süntaksi puu (pool)automaatselt; tuntuim neist on UNIX-i osa Yacc ja selle paljud modifikatsioonid, näiteks ka DOS-ümbrusesse üle kantud programm Bison, mida tavaliselt kasutatakse koos Flex-iga, s.t. Flex sooritab leksilise analüüsi ja seejärel Bison moodustab süntaksi puu. Lihtsamal juhul võib Bison koostada kogu transleeritava keele interpretaatori (s.t. transleeritud käsud kohe ka täidetakse).

FLEX-i kasutamisel Bison-ile lekseemide leidmiseks väljastatakse FLEX-is leitud lekseemid käsuga return.
Järgnevas on lihtne näide kalkulaatori skannerist (see tekst oleks fail scanner.l):

%option noyywrap
%{
%}
digit [0-9]
%%
"+" return(PLUS); /* s.t. moodustatakse lekseem PLUS */
"-" return(MINUS);
"*" return(MULTIPLY);
"/" return(DIVIDE);
"(" return(LPAR);
")" return(RPAR);
"\n" return(NEWLINE); /*kasutatakse üherealise kalkulaatori rea lõpu tunnistamiseks - kalkulaator peab nüüd väljastama tulemuse, vt vastavaid semantilisi tegevusi Bison-i failis*/

{digit}+ return(NUM); /*moodustatakse täisarvu lekseem */
{digit}+"."{digit}* return(NUM1); /* reaalarv */
{digit}*"."{digit}+ return(NUM1); /* reaalarv */

" \t" { }
"#" return (KOIK); /* töö lõpetamiseks */
. return(UNDEFINED);

%%
/* siin ei toimu midagi, peaprogramm on bison-i failis */

Flex-i käivitamisel selle failiga (> flex scanner.l) saame faili yylex.c, mis lisatakse include-lausega Bison-i programmi parser.y.
Produkstioonide ja nendega seotud semantiliste tegevuste esitamisel Bisonile erineb süntaks veidi Flex-is kasutatavast. Bisonile esitatakse näiteks (tavalise grammatika) produktsioon:
input -> input exp NEWLINE |

kujul (input, exp on mitteterminalid, NEWLINE - terminal, Flex-i lekseem):

input:   input exp NEWLINE { printf("Tulemus: %f\n",$2); }
    |   /* tühi parem pool */
;
s.t noole asemel on ":", produktsiooni lõpus peab olema ";" ja semantilised tegevused tuleb võtta figuursulgudesse { }; mitteterminalidega tähistatud väärtustele viidatakse sümbolitega $$ (produktsiooni vasaku poole mitteterminal), $1 (parema poole esimene mitteterminal), $2 (parema poole teine mitteterminal, näiteks ülaltoodud print-lauses viitab $2 reegli parema poole mitteterminalile exp, milles on kogu kasutaja poolt sisestatud avaldise väärtus) jne Järgnevas on faili "parser.y" tekst:
%{
#include "lexyy.c"
#include <stdio.h>
#include <math.h>
%}
// määrame terminalide (Flex-i lekseemide) ja mitteterminalide andmetüübid:
%union {
float fval;
int ival;
}
//Loetleme kõik terminalid (Flex-i lekseemid) ja määrame terminalide ja mitteterminalide andmetüübid:
%token PLUS MINUS MULTIPLY DIVIDE NUM NUM1 LPAR RPAR NEWLINE UNDEFINED KOIK

%type <fval> exp /* st. mitteterminal exp on float-tüüpi */
%type <ival> NUM /* st. terminal (lekseem) NUM on int */
%type <fval> NUM1
%left MINUS PLUS /* määrame assotsiatiivsuse; selles järjekorras määrates tuleb korrutamise-jagamise prioriteet kõrgem */
%left MULTIPLY DIVIDE

%%
input:   input exp NEWLINE { printf("Tulemus: %f\n",$2); }
    |   /* tühi parem pool */
;

exp:   NUM { $$ = atoi(yytext); /*printf("Integer: %d\n",atoi(yytext));*/}
    |   NUM1 { $$ = atof(yytext); /*printf("Float: %f\n", atof(yytext)); */}
    |   MINUS exp { $$ = -1.0 * $2; }
    |   exp PLUS exp { $$ = $1 + $3; }
    |   exp MINUS exp { $$ = $1 - $3; }
    |   exp MULTIPLY exp { $$ = $1 * $3; }
    |   exp DIVIDE exp { $$ = $1 / $3; }
    |   LPAR exp RPAR { $$ = $2; }
    |   KOIK { return 0;} // return 0 lõpetab töö
;

%%

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

main()
{
yyparse();
}

Nüüd käivitame selle failiga Bison-i:

> bison parser.y
ja seejärel kompileerime. Bison moodustab väljundi nime, lisades sisendfaili laiendi asemele "_tab.c"; kui uus nimi tuleb pikem kui 8 tähte, jäetakse lõpust (enne ".") tähti ära; praegu tuleb väljundfaili numeks parser_t.c; kompileerime selle gcc-ga ja anname kalkulaatori nimeks calc.exe:
> gcc parser_t.y -ocalc.exe
Saadud programmi calc.exe testimiseks käivitame selle:

> calc
>2+3
>Tulemus on 5.000
>2.3 + 5*.1
>Tulemus on 2.8000 -- korrutamise prioriteet on kõrgem!!
>2*-1
>Tulemus on -2.00000 -- unaarne miinus!

Veel üks Bison-i näide: kompleksarvudega arvutav (vaid +, -) kalkulaator (autor: Grigori Shpakov).
Flex-i sisend (NB - kompleksarvud sisestatakse veidi erineval kujul, imaginaarühik i on reaal- ja imaginaarosa eraldaja):

%option noyywrap
%{
%}

digit [0-9]
NUM {digit}+
NUM1 ({digit}+"."{digit}*|{digit}*"."{digit}+)
KOMPLEKS ({NUM1}|{NUM})"i"({NUM}|{NUM1})

%%
"+" return(PLUS);
"-" return(MINUS);
"*" return(MULTIPLY);
"/" return(DIVIDE);
"(" return(LPAR);
")" return(RPAR);
"\n" return(NEWLINE); /*kasutatakse üherealise kalkulaatori rea lõpu tunnistamiseks - kalkulaator peab nüüd väljastama tulemuse */

{NUM} return(NUM); /* täisarv */
{NUM1} return(NUM1); /* reaalarv */
{KOMPLEKS} return(KOMPLEKS);

" \t" { }
"#" return (KOIK); /* töö lõpetamiseks */
. return(UNDEFINED);

%%
/* siin ei toimu midagi, peaprogramm on bison-i failis */

Bison-i sisend (NB - kompleksarvude reaal- ja imaginaarosa jaoks defineertitakse andmetüüp struct):

%{
#include "lexyy.c"
#include <stdio.h>
#include <math.h>
#include <string.h>
%}

// määrame terminalide (Flex-i lekseemide) ja mitteterminalide andmetüübi
%union {
float fval;
int ival;
struct {
float real;
float kompl;
} cval;
}

//Loetleme kõik terminalid (Flex-i lekseemid) ja määrame terminalide ja mitteterminalide andmetüübid:
%token PLUS MINUS MULTIPLY DIVIDE NUM NUM1 KOMPLEKS LPAR RPAR NEWLINE UNDEFINED KOIK

%type <cval> exp /* st. mitteterminal exp on complex-tüüpi */
%type <ival> NUM /* st. terminal (lekseem) NUM on int */
%type <fval> NUM1
%type <cval> KOMPLEKS
%left MINUS PLUS /* määrame assotsiatiivsuse; selles järjekorras määrates tuleb korrutamise-jagamise prioriteet kõrgem */
%left MULTIPLY DIVIDE

%%
input: input exp NEWLINE { printf("Tulemus: (%f, %f)\n", $2.real, $2.kompl); }
| /* tühi parem pool */
;

exp: NUM { $$.real = atoi(yytext); $$.kompl = 0; /*printf("Integer: %d\n",atoi(yytext));*/}
| NUM1 { $$.real = atof(yytext); $$.kompl = 0; /*printf("Float: %f\n", atof(yytext)); */}
| KOMPLEKS { /*printf("Complex: %s\n", yytext); printf("Complex: %s\n", strchr(yytext, 'i')+1);*/ $$.real = atof(yytext); $$.kompl = atof(strchr(yytext, 'i')+1); /*printf("Complex: (%f, %f)\n", $$.real, $$.kompl);*/ }
| MINUS exp { $$.real = - $2.real; $$.kompl = - $2.kompl; }
| exp PLUS exp { $$.real = $1.real + $3.real; $$.kompl = $1.kompl + $3.kompl; }
| exp MINUS exp { $$.real = $1.real - $3.real; $$.kompl = $1.kompl - $3.kompl; }
| exp MULTIPLY exp { $$.real = ($1.real * $3.real) - ($1.kompl * $3.kompl); $$.kompl = ($1.real * $3.kompl) + ($1.kompl * $3.real); }
| exp DIVIDE exp { $$.real = (($1.real * $3.real) + ($1.kompl * $3.kompl)) / (($3.real * $3.real) + ($3.kompl * $3.kompl)); $$.kompl = (($1.kompl * $3.real) - ($1.real * $3.kompl)) / (($3.real * $3.real) + ($3.kompl * $3.kompl)); }
| LPAR exp RPAR { $$.real = $2.real; $$.kompl = $2.kompl; }
| KOIK { return 0;} // return 0 lõpetab töö
;

%%

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

main()
{
yyparse();
}

Küsimused, probleemid:
jaak@cc.ttu.ee

Tagasi loengute sisukorra juurde