Flex, bison multifunction calculator

annatsos · #1 03-Jan-2007, 03:58

Hello everyone.My problem is that i have to write a program using flex,bison and devC, and i've never used any of these tools. The teacher wants us to use only devc because it's the one she uses. The program we have to write is a calculator that supports operator presedence and use of 4 standart mathematical functions. Bacically what i need from you guys is to help me if you know flex and bison to create compile and run this example from the bison manual.

Heres the example in the manual for bison

Multi-Function Calculator: mfcalc

Now that the basics of Bison have been discussed, it is time to move on to a more advanced problem. The above calculators provided only five functions, +, -, *, / and ^. It would be nice to have a calculator that provides other mathematical functions such as sin, cos, etc.
It is easy to add new operators to the infix calculator as long as they are only single-character literals. The lexical analyzer yylex passes back all nonnumber characters as tokens, so new grammar rules suffice for adding a new operator. But we want something more flexible: built-in functions whose syntax has this form:
function_name (argument)
At the same time, we will add memory to the calculator, by allowing you to create named variables, store values in them, and use them later. Here is a sample session with the multi-function calculator:
$ mfcalc
pi = 3.141592653589
3.1415926536
sin(pi)
0.0000000000
alpha = beta1 = 2.3
2.3000000000
alpha
2.3000000000
ln(alpha)
0.8329091229
exp(ln(beta1))
2.3000000000
$
Note that multiple assignment and nested function calls are permitted.
• Decl: Bison declarations for multi-function calculator.
• Rules: Grammar rules for the calculator.
• Symtab: Symbol table management subroutines.
________________________________________
Node:Mfcalc Decl, Next:Mfcalc Rules, Up:Multi-function Calc
Declarations for mfcalc
Here are the C and Bison declarations for the multi-function calculator.
%{
#include <math.h> /* For math functions, cos(), sin(), etc. */
#include "calc.h" /* Contains definition of `symrec' */
%}
%union {
double val; /* For returning numbers. */
symrec *tptr; /* For returning symbol-table pointers */
}

%token <val> NUM /* Simple double precision number */
%token <tptr> VAR FNCT /* Variable and Function */
%type <val> exp

%right '='
%left '-' '+'
%left '*' '/'
%left NEG /* Negation--unary minus */
%right '^' /* Exponentiation */

/* Grammar follows */

%%
The above grammar introduces only two new features of the Bison language. These features allow semantic values to have various data types (see More Than One Value Type).
The %union declaration specifies the entire list of possible types; this is instead of defining YYSTYPE. The allowable types are now double-floats (for exp and NUM) and pointers to entries in the symbol table. See The Collection of Value Types.
Since values can now have various types, it is necessary to associate a type with each grammar symbol whose semantic value is used. These symbols are NUM, VAR, FNCT, and exp. Their declarations are augmented with information about their data type (placed between angle brackets).
The Bison construct %type is used for declaring nonterminal symbols, just as %token is used for declaring token types. We have not used %type before because nonterminal symbols are normally declared implicitly by the rules that define them. But exp must be declared explicitly so we can specify its value type. See Nonterminal Symbols.
________________________________________
Node:Mfcalc Rules, Next:Mfcalc Symtab, Previous:Mfcalc Decl, Up:Multi-function Calc
Grammar Rules for mfcalc
Here are the grammar rules for the multi-function calculator. Most of them are copied directly from calc; three rules, those which mention VAR or FNCT, are new.
input: /* empty */
| input line
;

line:
'\n'
| exp '\n' { printf ("\t%.10g\n", $1); }
| error '\n' { yyerrok; }
;

exp: NUM { $$ = $1; }
| VAR { $$ = $1->value.var; }
| VAR '=' 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; }
;
/* End of grammar */
%%
________________________________________
Node:Mfcalc Symtab, Previous:Mfcalc Rules, Up:Multi-function Calc
The mfcalc Symbol Table
The multi-function calculator requires a symbol table to keep track of the names and meanings of variables and functions. This doesn't affect the grammar rules (except for the actions) or the Bison declarations, but it requires some additional C functions for support.
The symbol table itself consists of a linked list of records. Its definition, which is kept in the header calc.h, is as follows. It provides for either functions or variables to be placed in the table.

CPP / C++ / C Code:

/* Fonctions type. */
typedef double (*func_t) (double);

/* Data type for links in the chain of symbols. */
struct symrec
{
char *name; /* name of symbol */
int type; /* type of symbol: either VAR or FNCT */
union
{
double var; /* value of a VAR */
func_t fnctptr; /* value of a FNCT */
} value;
struct symrec *next; /* link field */
};

typedef struct symrec symrec;

/* The symbol table: a chain of `struct symrec'. */
extern symrec *sym_table;

symrec *putsym (const char *, func_t);
symrec *getsym (const char *);

The new version of main includes a call to init_table, a function that initializes the symbol table. Here it is, and init_table as well:

CPP / C++ / C Code:

#include <stdio.h>

int
main (void)
{
init_table ();
return yyparse ();
}

void
yyerror (const char *s) /* Called by yyparse on error */
{
printf ("%s\n", s);
}

struct init
{
char *fname;
double (*fnct)(double);
};

struct init arith_fncts[] =
{
"sin", sin,
"cos", cos,
"atan", atan,
"ln", log,
"exp", exp,
"sqrt", sqrt,
0, 0
};

/* The symbol table: a chain of `struct symrec'. */
symrec *sym_table = (symrec *) 0;

/* Put arithmetic functions in table. */
void
init_table (void)
{
int i;
symrec *ptr;
for (i = 0; arith_fncts[i].fname != 0; i++)
{
ptr = putsym (arith_fncts[i].fname, FNCT);
ptr->value.fnctptr = arith_fncts[i].fnct;
}
}

By simply editing the initialization list and adding the necessary include files, you can add additional functions to the calculator.
Two important functions allow look-up and installation of symbols in the symbol table. The function putsym is passed a name and the type (VAR or FNCT) of the object to be installed. The object is linked to the front of the list, and a pointer to the object is returned. The function getsym is passed the name of the symbol to look up. If found, a pointer to that symbol is returned; otherwise zero is returned.

CPP / C++ / C Code:

symrec *
putsym (char *sym_name, int sym_type)
{
symrec *ptr;
ptr = (symrec *) malloc (sizeof (symrec));
ptr->name = (char *) malloc (strlen (sym_name) + 1);
strcpy (ptr->name,sym_name);
ptr->type = sym_type;
ptr->value.var = 0; /* set value to 0 even if fctn. */
ptr->next = (struct symrec *)sym_table;
sym_table = ptr;
return ptr;
}

symrec *
getsym (const char *sym_name)
{
symrec *ptr;
for (ptr = sym_table; ptr != (symrec *) 0;
ptr = (symrec *)ptr->next)
if (strcmp (ptr->name,sym_name) == 0)
return ptr;
return 0;
}

The function yylex must now recognize variables, numeric values, and the single-character arithmetic operators. Strings of alphanumeric characters with a leading non-digit are recognized as either variables or functions depending on what the symbol table says about them.
The string is passed to getsym for look up in the symbol table. If the name appears in the table, a pointer to its location and its type (VAR or FNCT) is returned to yyparse. If it is not already in the table, then it is installed as a VAR using putsym. Again, a pointer and its type (which must be VAR) is returned to yyparse.
No change is needed in the handling of numeric values and arithmetic operators in yylex.

CPP / C++ / C Code:

#include <ctype.h>

int
yylex (void)
{
int c;

/* Ignore whitespace, get first nonwhite character. */
while ((c = getchar ()) == ' ' || c == '\t');

if (c == EOF)
return 0;

/* Char starts a number => parse the number. */
if (c == '.' || isdigit ©)
{
ungetc (c, stdin);
scanf ("%lf", &yylval.val);
return NUM;
}

/* Char starts an identifier => read the name. */
if (isalpha ©)
{
symrec *s;
static char *symbuf = 0;
static int length = 0;
int i;

/* Initially make the buffer long enough
for a 40-character symbol name. */
if (length == 0)
length = 40, symbuf = (char *)malloc (length + 1);

i = 0;
do
{
/* If buffer is full, make it bigger. */
if (i == length)
{
length *= 2;
symbuf = (char *)realloc (symbuf, length + 1);
}
/* Add this character to the buffer. */
symbuf[i++] = c;
/* Get another character. */
c = getchar ();
}
while (c != EOF && isalnum ©);

ungetc (c, stdin);
symbuf[i] = '\0';

s = getsym (symbuf);
if (s == 0)
s = putsym (symbuf, VAR);
yylval.tptr = s;
return s->type;
}

/* Any other character is a token by itself. */
return c;
}

This program is both powerful and flexible. You may easily add new functions, and it is a simple job to modify this code to install predefined variables such as pi or e as well.

davekw7x · #2 03-Jan-2007, 09:42

Quote:

Originally Posted by annatsos

...my problem is that i have to write a program using flex,bison and devC...The program we have to write is a calculator that supports operator presedence and use of 4 standart mathematical functions. Bacically what i need from you guys is to help me if you know flex and bison to create compile and run this example from the bison manual.

What a terrific project!

The "mfcalc" section in the bison manual describes a calculator with operator precedence explained and defined in the example. In addition to +, -, * /, there is the ^ operator, and parentheses and several functions. Etc.

The manual gives a clue how to run things:

1. Put all of the example code in a single file. Name the file mfcalc.y (Note that mfcalc.y will have something like 200 lines of text --- maybe a little more.)

2. Run "bison mfcalc.y" and you get an output file named "mfcalc.tab.c"

3. Run the C compiler on mfcalc.tab.c (link in the math library). If it were going to be run from a command line, the command would be something like

gcc mfcalc.tab.c -lm -o mfcalc

If you are going to run it from the devc integrated development interface, make a project named mfcalc with mfcalc.tab.c as the main file (or you could rename it to mfcalc.c or whatever you want).

In either case, you get an executable named mfcalc. (Since it's Windows, the file will be named mfcalc.exe.)

4. Run the program mfcalc.

If you want to make modifications, then you study the example code in mfcalc.y and the description in the manual.

Regards,

Dave

annatsos · #3 03-Jan-2007, 11:16

Sorry but i'm kind of confused.It's the first time i see such a program.
Is mfcalc.y correct like this?

CPP / C++ / C Code:

%{
#include <math.h>  /* For math functions, cos(), sin(), etc. */
#include "calc.h"  /* Contains definition of `symrec'        */
%}
%union {
double     val;  /* For returning numbers.                   */
symrec  *tptr;   /* For returning symbol-table pointers      */
}

%token <val>  NUM        /* Simple double precision number   */
%token <tptr> VAR FNCT   /* Variable and Function            */
%type  <val>  exp

%right '='
%left '-' '+'
%left '*' '/'
%left NEG     /* Negation--unary minus */
%right '^'    /* Exponentiation        */

/* Grammar follows */

input:   /* empty */
        | input line
;

line:
          '\n'
        | exp '\n'   { printf ("\t%.10g\n", $1); }
        | error '\n' { yyerrok;                  }
;

exp:      NUM                { $$ = $1;                         }
        | VAR                { $$ = $1->value.var;              }
        | VAR '=' 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;                         }
;
/* End of grammar */
%%

/* Fonctions type.                                   */
typedef double (*func_t) (double);

/* Data type for links in the chain of symbols.      */
struct symrec
{
  char *name;  /* name of symbol                     */
  int type;    /* type of symbol: either VAR or FNCT */
  union
  {
    double var;                  /* value of a VAR   */
    func_t fnctptr;              /* value of a FNCT  */
  } value;
  struct symrec *next;    /* link field              */
};

typedef struct symrec symrec;

/* The symbol table: a chain of `struct symrec'.     */
extern symrec *sym_table;

symrec *putsym (const char *, func_t);
symrec *getsym (const char *);

#include <stdio.h>

int
main (void)
{
  init_table ();
  return yyparse ();
}

void
yyerror (const char *s)  /* Called by yyparse on error */
{
  printf ("%s\n", s);
}

struct init
{
  char *fname;
  double (*fnct)(double);
};

struct init arith_fncts[] =
{
  "sin",  sin,
  "cos",  cos,
  "atan", atan,
  "ln",   log,
  "exp",  exp,
  "sqrt", sqrt,
  0, 0
};

/* The symbol table: a chain of `struct symrec'.  */
symrec *sym_table = (symrec *) 0;

/* Put arithmetic functions in table. */
void
init_table (void)
{
  int i;
  symrec *ptr;
  for (i = 0; arith_fncts[i].fname != 0; i++)
    {
      ptr = putsym (arith_fncts[i].fname, FNCT);
      ptr->value.fnctptr = arith_fncts[i].fnct;
    }
}

symrec *
putsym (char *sym_name, int sym_type)
{
  symrec *ptr;
  ptr = (symrec *) malloc (sizeof (symrec));
  ptr->name = (char *) malloc (strlen (sym_name) + 1);
  strcpy (ptr->name,sym_name);
  ptr->type = sym_type;
  ptr->value.var = 0; /* set value to 0 even if fctn.  */
  ptr->next = (struct symrec *)sym_table;
  sym_table = ptr;
  return ptr;
}

symrec *
getsym (const char *sym_name)
{
  symrec *ptr;
  for (ptr = sym_table; ptr != (symrec *) 0;
       ptr = (symrec *)ptr->next)
    if (strcmp (ptr->name,sym_name) == 0)
      return ptr;
  return 0;
}

#include <ctype.h>

int
yylex (void)
{
  int c;

  /* Ignore whitespace, get first nonwhite character.  */
  while ((c = getchar ()) == ' ' || c == '\t');

  if (c == EOF)
    return 0;

  /* Char starts a number => parse the number.         */
  if (c == '.' || isdigit (c))
    {
      ungetc (c, stdin);
      scanf ("%lf", &yylval.val);
      return NUM;
    }

  /* Char starts an identifier => read the name.       */
  if (isalpha (c))
    {
      symrec *s;
      static char *symbuf = 0;
      static int length = 0;
      int i;

      /* Initially make the buffer long enough
         for a 40-character symbol name.  */
      if (length == 0)
        length = 40, symbuf = (char *)malloc (length + 1);

      i = 0;
      do
        {
          /* If buffer is full, make it bigger.        */
          if (i == length)
            {
              length *= 2;
              symbuf = (char *)realloc (symbuf, length + 1);
            }
          /* Add this character to the buffer.         */
          symbuf[i++] = c;
          /* Get another character.                    */
          c = getchar ();
        }
      while (c != EOF && isalnum (c));

      ungetc (c, stdin);
      symbuf[i] = '\0';

      s = getsym (symbuf);
      if (s == 0)
        s = putsym (symbuf, VAR);
      yylval.tptr = s;
      return s->type;
    }

  /* Any other character is a token by itself.        */
  return c;
}

I'm asking because it gives me a lot of errors when i run it.
I really appreciate the fact that you read my post thanks a lot

davekw7x · #4 03-Jan-2007, 14:55

Quote:

Originally Posted by annatsos

Sorry but i'm kind of confused.It's the first time i see such a program.

Yes, I'm guessing why you were given the assignment: "normal" amateur programmers don't do stuff like this much. Some years ago, someone decided to write a program that would write a compiler from a set of rules of grammar.

Several people thought of this, and there were a number of "compiler compiler" programs published: a compiler that would compile compilers. Bison is the GNU organization's equivalent to one of the more successful ones: yacc. The name yacc means "yet another compiler compiler". In fact, that's why the source file is called "mfcalc.y". The ".y" is from standard yacc usage.

Anyhow, back to reality:

When I run bison on your file, I get one error:

Code:

mfcalc1.y:22.1-5: syntax error, unexpected identifier:

Here are your lines 20-23:

CPP / C++ / C Code:

/* Grammar follows */

input:   /* empty */
        | input line

Here is the stuff from the manual:

CPP / C++ / C Code:

/* Grammar follows */

%%
input:   /* empty */

I know it's tough when you are just trying to cobble something together from some language(s) that you haven't been trained for. But everything is significant. The "%%" line makes a whale of a lot of difference.

When I put that line in, then I got lots of errors, too.

1. The example uses a header file "calc.h" that looks like this:

CPP / C++ / C Code:

/* Data type for links in the chain of symbols.      */
struct symrec
{
  char *name;  /* name of symbol                     */
  int type;    /* type of symbol: either VAR or FNCT */
  union {
    double var;           /* value of a VAR          */
    double (*fnctptr)();  /* value of a FNCT         */
  } value;
  struct symrec *next;    /* link field              */
};

typedef struct symrec symrec;

/* The symbol table: a chain of `struct symrec'.     */
extern symrec *sym_table;

symrec *putsym ();
symrec *getsym ();

Since your mfcalc.y includes "calc.h" you had better have it also. Bison won't complain, but gcc will.

Now, locate the place in your mfcalc.y that has those lines and delete them. (Or, you could probably simply move them to the top of the file and put them in the place of the #include "calc" line, and delete the #include "calc" thing.)

I put things together pretty much in the same order as in the example. I think we are pretty much in agreement until about line 45 (/* End of grammar */)

The next things I put were the definitions of yylex(), getsym() and putsym()

Now, bison ran OK, but gcc gave me some errors about EOF and printf(), so I decided that it needed to #include <stdio.h> somewhere before the errors. You could put it anywhere, maybe at the very top of mfcalc.y. (Remember, you make changes in mfcalc.y and use bison to generate a new mfcalc.tab.c each time. Don't try to "fix" mfcalc.tab.c itself, but use gcc's messages to give you clues as to where to look.

Now, with #include <stdio.h> just above the #include <math.h> line, I was down to only a couple of errors:

One of them looked like this:

Code:

mfcalc.y:151: error: conflicting types for 'yyerror'
mfcalc.tab.c:1444: error: previous implicit declaration of 'yyerror' was here

Now we are into specific C messages. It is possible to use command-line switches to overcome some errors about lack of prototypes, and in this case, it wouldn't hurt, but I would rather fix the error.

Here's the offending function in your mfcalc.y

CPP / C++ / C Code:

void
yyerror (const char *s)  /* Called by yyparse on error */
{
  printf ("%s\n", s);
}

Now, I don't see how this could cause an error, since nothing in your program calls yyerror explicitly, but, in fact the way the whole thing is put together, you have to have a prototype for this somewhere. I vote for putting it at the top:

CPP / C++ / C Code:

%{
#include <stdio.h>
#include <math.h>  /* For math functions, cos(), sin(), etc. */
#include "calc.h"  /* Contains definition of `symrec'        */
void yyerror(char const *);
%}

Now, bison-gcc leaves exactly one error:

Code:

mfcalc.y:179: error: conflicting types for 'init_table'
mfcalc.y:146: error: previous implicit declaration of 'init_table' was here

Either give a prototype for init_table somewhere before it is used (in main()) or move the entire function init_table() before main() in mfcalc.y

Now, if you don't do things exactly the same way and in the same sequence, you might see different manifestations of some of these messages and that's ok. The important thing is: Don't Panic. Look at the error messages and see if you can figure a reasonable way around them.

When lots of stuff like this was written, the versions of gcc and other system tools were probably more tolerant of certain pecadillos of C programmers of the day (maybe even before the first C standard in 1989). There is (almost) always some cleanup required unless you have the exact same version of the tools that were used when the author wrote the manual.

It's not easy, I know, to keep your head when things like this give you lots of errors. (How the heck does it keep track of the things in mfcalc.y when it is compiling mfcalc.tab.c??? It's astounding.)

Regards,

Dave

"Don't Panic"
---Douglas Adams
The Hitch Hiker's Guide to the Galaxy
http://www.mindgazer.org/dontpanic/thehitch.htm

annatsos · #5 04-Jan-2007, 03:46

Thanks a lot Dave

Everything works perfectly now.

asac · #6 03-May-2007, 10:38

hi! who can help me with a complete source code of this yacc calculator ... because i'm trying to learn...

pls!!! or send me an email at: asac_cool at yahoo dot com (at = @ and dot = . for those that don't know)

davekw7x · #7 03-May-2007, 10:50

Quote:

Originally Posted by asac

hi! who can help me with a complete source code of this yacc calculator

As the Original Poster mentioned, the example is in the Bison manual. Different versions of Bison may have slightly different documentation, but you can find a current version of the manual here: http://www.gnu.org/software/bison/manual/.

Download the 144-page pdf version if you want to print it out, or use the html version for on-line reference (or both).

I respectfully suggest that you not just jump to section 2.5 (where the mfc is presented), but work your way through the previous examples, too.

If you have problems, then show us what you are working with and ask specific questions about what it is that you don't understand.

Quote:

Originally Posted by asac

i'm trying to learn

Me too.

Quote:

Originally Posted by asac

send me an email

It's an open forum. Things discussed in public give others a chance to learn also. I think that learning Bison is best accomplished by starting with the text and the examples in the excellent Bison manual rather than having someone send me a complete program that just works, although working examples are very valuable (that is why they are in the manual).

After all, the objective isn't just having a calculator program (there are some excellent calculator programs that come free with versions of Windows and Linux that I have). It's all about learning, Right?

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Try to post the code of this program plzzz..Calculator is hard to solve!!!	albert_123	C Programming Language	3	21-Sep-2006 02:41
Simple Calculator Application	MOHAMMEDALI1989	Java Forum	1	06-Oct-2005 17:00

Flex, bison multifunction calculator

Re: Flex, bison multifunction calculator

Re: Flex, bison multifunction calculator

Re: Flex, bison multifunction calculator

Re: Flex, bison multifunction calculator

Re: Flex, bison multifunction calculator

Re: Flex, bison multifunction calculator