| |
|
|
|
Järgnevas on Bison-i abil realiseeritud mäluga kalkulaator - kasutaja võib omistada muutujatele väärtusi ja neid siis järgmistes operatsioonides kasutada. Muutujad ja funktsioonid salvestatakse nimede tabelis, mis on realiseeritud linkidega nimistuna; kogu see andmestruktuur on kirjeldatud header-failis tabel.h:
/* lingitud symbolite andmetyyp */
struct nimi
{
char *name; /* muutuja nimi */ int type; /* symboli tyyp: kas IDENT või FNCT
*/ union {
double var; /* IDENT väärtus - reaalarv */ double (*fnctptr)(); /* FNCT väärtus */
} value; struct nimi
*next; /* link */ };
typedef struct nimi nimi; /* et poleks tarvis kasutada 'struct' */
/* Nimede tabel: ahel `struct nimi' -st */
extern nimi *sym_table;
nimi *putsym ();
nimi *getsym ();
Bison-i sisendfailis lisatakse see andmestruktuuri kirjeldus #include-failina.
Kalkulaatori sisendis võivad esineda kolme tüüpi lekseemid: muutujad (lekseem IDENT), arvud (lekseem NUM) ja funktsioonide tähistused ( lekseemid tüübiga FNCT), millega on seotud semantiline väärtus. Väärtuse tüüp on lekseemidel IDENT, NUM - double (see on ka mitteterminali exp tüüp) ja lekseemil FNCT - viit selle funktsiooni kirjeldusele. Erineva tüübiga lekseemide ja mitteterminalide kasutamisel tuleb defineerida Bison-i programmi algul tüüpide ühend union ja siis määrata, mis tüüpi mingi lekseem või mitteterminal on:
%union{
double val;
nimi *tptr; }
%token <val> NUM
%token <tptr> IDENT FNCT
%type <val> exp
Sisendis esinevatel ülejäänud lekseemidel ( aritmeetilised operatsioonid, sulud ja omistamismärk =) semantilist väärtust ja tüüpi ei ole.
Erinevate tüüpide tõttu moodustab Bison lekseemi infot sisaldava muutuja yylval kirjeldamiseks andmetüübi YYSTYPE:
typedef union YYSTYPE {
double val;
nimi *tptr; } YYSTYPE;
extern YYSTYPE yylval;
Et YYSTYPE ja yylval kirjeldus oleks ka (eraldi kompileeritavas) Flex-i poolt moodustatud skanneris kättesaadav, tuleb lasta Bisonil need kirjeldused käsuga %defines eraldi h-faili kirjutada ja siis #include -lausega Flex-i sisendprogrammi lisada. Kui Bison-i sisendprogramm on (näiteks) failis calc.y, annab Bison kirjeldusi sisaldava h-faili nimeks calc.tab.h
Omistamisi võib korraga (samal real) teha mittu s.t. kalkulaatorile võib sisestada a = b = 1.3, sellepärast on ka võrdusmärk = defineeritud aritmeetilise operaatorina. Kuna eespooltoodud reas väärtuste omistamised peavad toimuma paremalt vasakule (s.t. operatsioonide sooritamist sulgude abil määrates tuleks eelnevat omistamiste rida tõlgendada nii: a = (b = 1.3)), peab võrdusmärgi assotsiatiivsus olema määratud parempoolseks. Järgnevas on Bison-i sisendfail calc.y:
/*mäluga kalkulaator */
%{
#include <math.h> /* Matemaatiliste funktsioonide cos(), sin(),
jne. kasutamiseks*/
#include "tabel.h" /* Andmestruktuuri `nimi' kirjeldus */
#include <stdio.h>
#include "lex.yy.c"
int i;
nimi *nextid; /* kasutatakse testimisel nimede tabeli trykkimiseks */
%}
%defines
%union {
double val; /* arvud */
nimi *tptr; /* viidad nimede tabelisse */
}
%token <val> NUM /* arvud */
%token <tptr> IDENT FNCT /* identifikaatorid ja funktsioonid */
%type <val> exp
%right '=' /* omistamised toimuvad paremalt vasakule! */
%left '-' '+'
%left '*' '/'
%left NEG /* unaarne miinus */
%right '^' /* astendamine */
/* algab grammatika */
%%
input: /* empty */
| input line
;
line:
'\n'
| exp '\n' { printf ("%d: \t%.10g\n",yylineno-1,
$1); /* reavahetus on juba olnud! */ }
| error '\n' { yyerrok; }
;
exp: NUM { $$ = $1; }
| IDENT { $$ = $1->value.var; }
| IDENT '=' exp { $$ = $3; $1->value.var =
$3; }
| FNCT '(' exp ')' { $$ =
(*($1->value.fnctptr))($3); }
| exp '+' exp { $$ = $1 + $3; } | exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1, $3); }
| '(' exp ')' { $$ = $2; }
;
%%
main ()
{
init_table (); /* funktsioonide sin, exp jne
tabelisse lisamine - need loeb ka lekseem IDENT */ yyparse ();
/* trykime (testimiseks nimede tabli; muutujate puhul ka muutuja
väärtuse */
extern nimi *sym_table;
nextid = sym_table;
i=1; /* reanumber */
do {
printf( "%d: %s",i, nextid->name );
if (nextid->type == IDENT)
printf("\t: %f",nextid->value.var);
printf("\n");
i++;
nextid = nextid->next;
} while ( nextid->next != NULL );
printf( "%d: %s\n",i, nextid->name );
}
yyerror (s) /* yyparse käivitab vea korral */
char *s;
{
printf ("%s\n", s);
}
Flex-i sisendfailis on C-deklaratsioonide osas #include lausete järel kirjeldatud symboltabel sym_table kui struktuuride struct nimi lingitud nimistu, seejärel kantud sinna viidad funktsioonidele sin, cos jne ja kirjeldatud funkstioonid putsym tabelisse identifikaatori lisamiseks ja getsym - identifikaatori väärtuse saamiseks tablist:
%option noyywrap
%option yylineno
%{
#include "calc.tab.h"
#include <ctype.h>
#include <math.h>
#include <stdio.h>
YYSTYPE yylval;
struct init
{
char *fname;
double (*fnct)(); };
struct init arith_fncts[] /* loetelu kasutatavatest funktsioonidest */
= {
"sin", sin,
"cos", cos, "atan", atan, "ln", log, "exp", exp,
"sqrt", sqrt, 0, 0
};
/* Nimede tabel - struktuuride `struct nimi' ahel */
nimi *sym_table = (nimi *)0;
init_table () /* ka aritmeetilised funktsioonid pannakse tabelisse */
{
int i; nimi *ptr;
for (i = 0; arith_fncts[i].fname != 0; i++)
{ ptr = putsym
(arith_fncts[i].fname, FNCT);
ptr->value.fnctptr = arith_fncts[i].fnct; } }
nimi * putsym (char *sym_name, int sym_type)
{
nimi *ptr; ptr =
(nimi *) malloc (sizeof (nimi));
ptr->name = (char *) malloc (strlen (sym_name) + 1); strcpy (ptr->name,sym_name); ptr->type = sym_type;
ptr->value.var = 0; /* algväärtustamine - ka fctn jaoks */
ptr->next = (struct nimi *)sym_table;
sym_table = ptr;
return ptr; }
nimi * getsym (char *sym_name)
{
nimi *ptr;
for (ptr = sym_table; ptr != (nimi *) 0; ptr = (nimi *)ptr->next)
if (strcmp (ptr->name,sym_name) == 0)
return ptr;
return 0; }
%}
Lekseemide kirjeldus on üsna tavaline; veidi "nipitama" peab vaid arvude ja identifikaatorite puhul:
DIGIT [0-9]
ID [A-Za-z][A-Za-z0-9]*
TYHIK [ \t]+
%%
"+" return ('+');
"-" return ('-');
"*" return ('*');
"/" return ('/');
"^" return ('^');
"=" return('=');
"(" return('(');
")" return(')');
"\n" return('\n');
{DIGIT}+("."{DIGIT}*)? {yylval.val=atof(yytext);return(NUM);}
"."{DIGIT}+ {yylval.val=atof(yytext);return(NUM);}
{ID} {nimi *s;s = getsym (yytext);
if (s == 0)
s = putsym (yytext, IDENT);
yylval.tptr = s;
return s->type;};
{TYHIK} ; /* tyhikud ja tabulatsiooonimärgid kustutatakse */
%%
Testime sisendfailiga:
5+2*4
pi = 3.141592653589
sin(pi)
a = b = 1.3
a + 2*b
- ln(a)
c = exp(ln(b))
b = 2*b
1: 13
2: 3.141592654
3: 7.932657894e-013
4: 1.3
5: 3.9
6: -0.2623642645
7: 1.3
8: 2.6
1: c : 1.300000
2: b : 2.600000
3: a : 1.300000
4: pi : 3.141593
5: sqrt
6: exp
7: ln
8: atan
9: cos
10: sin
exp + exp | exp - exp | exp * exp jne). Asenda avaldise exp
grammatika ühesega (sellisega, nagu näiteks peatükis
"Kiire alt-üles analüüs: eelnevusgrammatikad"
ülesande 1 osas 1. või 2. on esitatud. 
©2004 Jaak
Henno