Flex and bison coding

lucky88star · #1 20-Dec-2007, 17:02

I need help with correcting my errors of this parse program

scan.l

CPP / C++ / C Code:

%{
/* a pure (reentrant) parser and scanner */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "parse.h"

int my_yy_flex_debug;    /* my flex debug flag */

extern int fileno(FILE *);      /* avoids gcc warning */

static int number(char *, YYSTYPE *);
static int string(char *, YYSTYPE *);


static char *estrdup( const char *s)
{ 
    char *r = malloc( strlen(s) + 1);
    if( r == NULL) 
    abort(); 
    return strcpy( r, s);
}

%}

D	[0-9]
E	[Ee][+\-]?{D}+
A     [A-Za-z_][A-Za-z_0-9]*	
%%

%{
	yy_flex_debug = my_yy_flex_debug;
%}


[ \t\v\f]			{ /* ignore whitespace */ }

[()=+*/\-\n]	        	{ return yytext[0]; }



{D}+({E})?			{ return number(yytext, yylval);   }
{D}*"."{D}+({E})?		{ return number(yytext, yylval);   }
{D}+"."{D}*({E})?		{ return number(yytext, yylval);   }  

'+'                             { return PLUS;                     }
'-'                             { return MINUS;                    }
'*'                             { return MULT;                     }
"/"                             { return DIVI;                     }
"reshape"                       { return RESHAPE;                  }
".+"                            { return DPLUS;                    }
".-"                            { return DMINUS;                   }
".*"                            { return DMULT ;                   }
"./"                            { return DDIVI;                    }
\"[^"]*\"		              { return string( yytext, yylval); }
{A}({A}|{D})*		        { yylval->string = estrdup( yytext); return ID; }
'='                               { return EQUAL;                    }


abs				{ return ABS;  }
avg				{ return AVG;  }

"+/"                            { return SPLUS;                    } 
"*/"                            { return SMULT;                    }
"-/"                            { return SMINUS;                   } 
"//"                            { return SDIVI;                    } 



"#".*				{ /* ignore comments */            }

.				{ return yytext[0]; /* bad token */ }

%%


void (*jj_junk)(int,char *,yyscan_t) = yyunput; /* avoids gcc warning */

int number( char *s, YYSTYPE *y)
{
  if( sscanf( s, "%lf", &(y->number) ) != 1 ) return 0;
  return NUMBER;
}

int string( char *s, YYSTYPE *y)
{
  y->string = estrdup( s);
  return STRING;
}

extern int yyparse( yyscan_t scanner);

int main( int argc, char *argv[])
{
  yyscan_t scanner;

#if YYDEBUG
  yydebug = argc > 1;
#endif
  my_yy_flex_debug = argc > 1;

  yylex_init( &scanner);

  yyparse( scanner);

  yylex_destroy( scanner);

  return 0;
}

/* called at EOF */

int yywrap( yyscan_t scanner)
{
  return 1;
}

/* called for parser syntax error */

void yyerror( yyscan_t scanner, const char *msg)
{
  printf( "error: %s\n", msg);
}

parse.y

CPP / C++ / C Code:

%{

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void yyerror( const char *msg);	    /* called for parser syntax error */

%}

%union{
  int count;
  double number;
  char *string;
}

%token <number> NUMBER
%token <string> ID

%right PLUS MINUS DIVI MULT SPLUS SMINUS SMULT SDIVI DPLUS DMINUS DDIVI DMULT EQUAL ABS AVG RESHAPE

%type <count> elist

%{
%}

%%

expr  : pri 
      | MINUS expr	       { printf( "unary - \n");           }
      | expr MULT expr         { printf( "binary  * \n");         }
      | expr DIVI expr         { printf( "binary  / \n");         }
      | expr MINUS expr        { printf( "binary  - \n");         }
	| expr PLUS expr         { printf( "binary  + \n");         }
      | expr DPLUS expr        { printf( "binary  .+ \n");        } 
      | expr DMINUS expr       { printf( "binary  .- \n");        }
      | expr DMULT expr        { printf( "binary  .* \n");        }         
      | expr DDIVI expr        { printf( "binary  ./ \n");        } 
      | expr SPLUS expr        { printf( "unary  +/ \n");         } 
      | expr SMINUS expr       { printf( "unary  -/ \n");         }         
      | expr SMULT expr        { printf( "unary  */ \n");         } 
      | expr SDIVI expr        { printf( "umary  // \n");         } 
       |expr RESHAPE expr          { printf( "binary reshape \n");    }
      | ABS expr               { printf( "unary abs\n");          } 
      | AVG expr               { printf( "unary avg\n");          } 
      | ID EQUAL expr        { printf( "binary  = \n");       } 
      | expr error '\n'	       { yyerrok;                         }
	;


elist	: expr			{ $$ = 1; }
	| elist ',' expr	      { $$ += 1; }
	;

pri
	: NUMBER		{ printf( "push: %f\n", $1);}
	| '(' expr ')'
	| '{' 			{ printf( "list start:\n"); }
            elist '}'		{ printf( "list end \n"); }
	| ID
	  {
	    printf( "push: %s\n", $1);
          }
	  ;

%%

Code:

"scan.l", line 50: warning, rule cannot be matched
"scan.l", line 61: warning, rule cannot be matched
"scan.l", line 62: warning, rule cannot be matched
gcc -ansi -pedantic -Wall -DDEBUG=1    -c -o scan.o scan.c
scan.l: In function `yylex':
scan.l:43: incompatible type for argument 2 of `number'
scan.l:44: incompatible type for argument 2 of `number'
scan.l:45: incompatible type for argument 2 of `number'
scan.l:56: incompatible type for argument 2 of `string'
scan.l:57: invalid type argument of `->'
scan.l: At top level:
scan.l:78: parse error before "yyscan_t"
scan.l: In function `string':
scan.l:89: `STRING' undeclared (first use in this function)
scan.l:89: (Each undeclared identifier is reported only once
scan.l:89: for each function it appears in.)
scan.l: At top level:
scan.l:92: parse error before "scanner"
scan.l: In function `main':
scan.l:96: `yyscan_t' undeclared (first use in this function)
scan.l:96: parse error before "scanner"
scan.l:103: warning: implicit declaration of function `yylex_init'
scan.l:103: `scanner' undeclared (first use in this function)
scan.l:107: warning: implicit declaration of function `yylex_destroy'
scan.l: At top level:
scan.l:114: parse error before "scanner"
scan.l:121: parse error before "scanner"

I am unable to correct the errors. Please help me out with this.

inevitable · #2 20-Dec-2007, 19:36

Based on my understanding of the parsers
I had comment on this as of now.

CPP / C++ / C Code:

{D}+({E})?			{ return number(yytext, yylval);   }

It should be

CPP / C++ / C Code:

({D}+({E})?			{ return number(yytext, yylval);   }

akshara.sinha · #3 21-Dec-2007, 15:12

I am new to the parser coding. I have written a code but am unable to understand the errors. Can someone please help me out with it.

My code:
scan.l

CPP / C++ / C Code:

%{
/* a pure (reentrant) parser and scanner */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int my_yy_flex_debug;    /* my flex debug flag */

extern int fileno(FILE *);      /* avoids gcc warning */

static int number(char *, YYSTYPE *);
static int string(char *, YYSTYPE *);


static char *estrdup( const char *s)
{
    char *r = malloc( strlen(s) + 1);
    if( r == NULL)
    abort();
    return strcpy( r, s);
}

%}

D       [0-9]
E       [Ee][+\-]?{D}+
A     [A-Za-z_][A-Za-z_0-9]*


%%

%{
        yy_flex_debug = my_yy_flex_debug;
%}
[ \t\v\f]                       { /* ignore whitespace */ }
    
[()=+*/\-\n]                    { return yytext[0]; }
 

{D}+({E})?                      { return number(yytext, yylval);   }
{D}*"."{D}+({E})?               { return number(yytext, yylval);   }
{D}+"."{D}*({E})?               { return number(yytext, yylval);   }

'+'                             { return PLUS;                     }
'-'                             { return MINUS;                    }
'*'                             { return MULT;                     }
"/"                             { return DIVI;                     }
"reshape"                       { return RESHAPE;                  }
".+"                            { return DPLUS;                    }
".-"                            { return DMINUS;                   }
".*"                            { return DMULT ;                   }
"./"                            { return DDIVI;                    }
\"[^"]*\"                       { return string( yytext, yylval); }
{A}({A}|{D})*                   { yylval->string = estrdup( yytext); return ID; }
'='                               { return EQUAL;                    }
 
abs                             { return ABS;  }
avg                             { return AVG;  }

"+/"                            { return SPLUS;                    }
"*/"                            { return SMULT;                    }
"-/"                            { return SMINUS;                   }
"//"                            { return SDIVI;                    }



"#".*                           { /* ignore comments */            }

.                               { return yytext[0]; /* bad token */ }

%%
void (*jj_junk)(int,char *,yyscan_t) = yyunput; /* avoids gcc warning */
 
int number( char *s, YYSTYPE *y)
{
  if( sscanf( s, "%lf", &(y->number) ) != 1 ) return 0;
  return NUMBER;
}

int string( char *s, YYSTYPE *y)
{
  y->string = estrdup( s);
  return STRING;
}

extern int yyparse( yyscan_t scanner);

int main( int argc, char *argv[])
{
  yyscan_t scanner;
 
#if YYDEBUG
  yydebug = argc > 1;
#endif
  my_yy_flex_debug = argc > 1;
 
  yylex_init( &scanner);

  yyparse( scanner);
  
  yylex_destroy( scanner);
 
  return 0;
}

/* called at EOF */
int yywrap( yyscan_t scanner)
{
  return 1;
}

parse.y

CPP / C++ / C Code:

%{

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef void *yyscan_t;

%}

%union{
  int count;
  double number;
  char *string;
}

%token <number> NUMBER
%token <string> ID

%token PLUS MINUS DIVI MULT SPLUS SMINUS SMULT SDIVI DPLUS DMINUS DDIVI DMULT EQUAL ABS AVG RESHAPE

%type <count> elist

%{
%}

%%

expr  : pri
      | MINUS expr             { printf( "unary - \n");           }
      | expr MULT expr         { printf( "binary  * \n");         }
      | expr DIVI expr         { printf( "binary  / \n");         }
      | expr MINUS expr        { printf( "binary  - \n");         }
        | expr PLUS expr         { printf( "binary  + \n");         }
      | expr DPLUS expr        { printf( "binary  .+ \n");        }
      | expr DMINUS expr       { printf( "binary  .- \n");        }
      | expr DMULT expr        { printf( "binary  .* \n");        }
      | expr DDIVI expr        { printf( "binary  ./ \n");        }
       |expr RESHAPE expr          { printf( "binary reshape \n");    }
      | ABS expr               { printf( "unary abs\n");          }
      | AVG expr               { printf( "unary avg\n");          }
      | ID EQUAL expr        { printf( "binary  = \n");       }
       ;

      
elist   : expr                  { $$ = 1; }
        | elist ',' expr              { $$ += 1; }
        ;
        
pri
        : NUMBER                { printf( "push: %f\n", $1);}
        | '(' expr ')'
        | '{'                   { printf( "list start:\n"); }

       elist '}'           { printf( "list end \n"); }
        | ID
          {
            printf( "push: %s\n", $1);
          }
          ;
      
%%

Although I declared PLUS, MINUS, ... I still get these errors:

Code:

/usr/share/bison/bison.simple: In function `yyparse':
/usr/share/bison/bison.simple:573: warning: implicit declaration of function `yylex'
/usr/share/bison/bison.simple:799: warning: implicit declaration of function `yyerror'
gcc -ansi -pedantic -Wall -DDEBUG=1    -c -o scan.o scan.c
scan.l:12: parse error before "YYSTYPE"
scan.l:13: parse error before "YYSTYPE"
scan.l: In function `yylex':
scan.l:44: `yylval' undeclared (first use in this function)
scan.l:44: (Each undeclared identifier is reported only once
scan.l:44: for each function it appears in.)
scan.l:48: `PLUS' undeclared (first use in this function)
scan.l:49: `MINUS' undeclared (first use in this function)
scan.l:50: `MULT' undeclared (first use in this function)
scan.l:51: `DIVI' undeclared (first use in this function)
scan.l:52: `RESHAPE' undeclared (first use in this function)
scan.l:53: `DPLUS' undeclared (first use in this function)
scan.l:54: `DMINUS' undeclared (first use in this function)
scan.l:55: `DMULT' undeclared (first use in this function)
scan.l:56: `DDIVI' undeclared (first use in this function)
scan.l:58: `ID' undeclared (first use in this function)
scan.l:59: `EQUAL' undeclared (first use in this function)
scan.l:61: `ABS' undeclared (first use in this function)
scan.l:62: `AVG' undeclared (first use in this function)
scan.l:64: `SPLUS' undeclared (first use in this function)
scan.l:65: `SMULT' undeclared (first use in this function)
scan.l:66: `SMINUS' undeclared (first use in this function)
scan.l:67: `SDIVI' undeclared (first use in this function)
scan.l: At top level:
scan.l:78: parse error before "yyscan_t"
scan.l:80: parse error before "YYSTYPE"
scan.l: In function `number':
scan.l:82: `s' undeclared (first use in this function)
scan.l:82: `y' undeclared (first use in this function)
scan.l:83: `NUMBER' undeclared (first use in this function)
scan.l: At top level:
scan.l:86: parse error before "YYSTYPE"
scan.l: In function `string':
scan.l:88: `y' undeclared (first use in this function)
scan.l:88: `s' undeclared (first use in this function)
scan.l:89: `STRING' undeclared (first use in this function)
scan.l: At top level:
scan.l:92: parse error before "scanner"
scan.l: In function `main':
scan.l:97: `yyscan_t' undeclared (first use in this function)
scan.l:97: parse error before "scanner"
scan.l:104: warning: implicit declaration of function `yylex_init'
scan.l:104: `scanner' undeclared (first use in this function)
scan.l:108: warning: implicit declaration of function `yylex_destroy'
scan.l: At top level:
scan.l:115: parse error before "scanner"
make: *** [scan.o] Error 1

Can someone please look into it.

davekw7x · #4 24-Dec-2007, 10:00

Quote:

Originally Posted by lucky88star

I need help

I have been waiting to see whether any bison/yacc experts or lex/flex experts (lexperts? flexperts?) would respond, since I haven't played with these for years.

Seeing no other volunteers, I will have a shot at it, and hope that it isn't too late to offer help.

First of all, I will say that i find lex/flex a lot of fun, and people writing compilers or parts of compilers have used it over the years along with yacc to resolve and implement various types of grammars. See Footnote. I will walk through a few steps with flex and bison as I use them on my Linux system.

Since you posted something.l and something.y and you showed error messages for something.c, I will try to fill in a few blanks for people playing at home:

The file scan.l has a statement #include parse.h. That statement is not processed by flex, but will be processed by gcc. Since gcc didn't complain, I will assume that you, indeed, have a file named parse.h

Where does parse.h come from?

Well we run bison on parse.y with a "-d" command line switch to get bison to create a header file and a C source file:

bison -d parse.y

Bison creates two files:

parse.tab.h
parse.tab.c

Here is one difference between bison and yacc:

yacc would create the following two files:

y.tab.h
y.tab.c

If we run bison with "-y" it creates the same file names as yacc---that's handy for users with old scripts or makefiles that use the yacc names.

(Note that versions of yacc ported to DOS systems might actually create file with the old 8.3 names, so you might actually get parse.h and parse.c)

However, I will just run bison -d and rename the files.

bison -d parse.h
mv parse.tab.c parse.c
mv parse.tab.h parse.h

(For people on Windows, use "ren" to rename the files, instead of "mv", unless they are using a bash-like shell.)

Now, when you run flex on a file, it creates a file named lex.yy.c. I will rename that file, as follows:

flex scan.l
mv lex.yy.c scan.c

At this point there are three new files:

parse.c
parse.h
scan.c

When I run gcc on scan.c, I get all of your errors and one more

Code:

scan.l:33: error: ‘yy_flex_debug’ undeclared (first use in this function)
scan.l:33: error: (Each undeclared identifier is reported only once
scan.l:33: error: for each function it appears in.)
.
. Others are same as yours.
.

So, either your makefile (or other script) did something about yy_flex_debug that I don't know about, or your version of bison or flex does something that I don't know about.

For now, I will simply put the following line in the scan.l, just before your "int my_yy_flex_debug;" statement. (We might have to do something more useful later.)

Code:

extern int yy_flex_debug; /* New line number 9 */
int my_yy_flex_debug;    /* my flex debug flag */

OK, now we are ready to look at the errors.

First of all, the following three messages come from flex:

Code:

"scan.l", line 51: warning, rule cannot be matched
"scan.l", line 62: warning, rule cannot be matched
"scan.l", line 63: warning, rule cannot be matched

This is a significant indicator that your scan.l file has some functional shortcomings. It will (probably) not work as you intended. They do not, however interfere with gcc, and do not cause anything that we worry about just yet. They may very well play a big part in debugging the bloomin' thing after we get it to compile.

Now, the "good stuff". This is the "C" stuff (although this is the C++ forum).

First of all note that although we are compiling scan.c, the messages refer back to scan.l. What a great thing they they have done for us!!! The hundred or so lines of scan.l have given us over 1500 lines of C code, most of which came from flex, not from scan.l. Just showing us what line of the C file it was having a problem with wouldn't be nearly as useful as showing us what line of scan.l created the problem

Look (yes, look) at the first message, and the line in scan.l that it refers to:

Here's my message (my line number is one greater than yours, since I had to add a line):

Code:

scan.l:43: error: incompatible type for argument 2 of ‘number’

Here's line 43 of my scan.l

CPP / C++ / C Code:

{D}+({E})?			{ return number(yytext, yylval);   }

Question: What is argument 2 of number?
Answer: It is yylval

Question: What is the variable type of argument 2 ofg number(), as defined in scan.l?

Answer: it is a pointer to some data type YYSTYPE

Now, without even knowing what the heck YYSTYPE is, a good guess might be that the problem may be that we should supply a pointer as argument 2 to number(), and we have supplied a variable that is not a pointer.
Looking a little closer, I find the following in parse.h

CPP / C++ / C Code:

extern YYSTYPE yylval;

So, indeed, the data type of yylval is YYSTYPE, and argument 2 of number requires a pointer to YYSTYPE.

Bottom line: As much fun as flex and bison are, you still have to use your finely-honed debugging skills (that you learned when studying C) to get to the bottom of things. After all, people writing compilers (or parts of compilers, like parsers) should know something about the language they are dealing with. I can't imagine someone with no C programming knowledge or experience trying to make some sense out of a flex-based scanner and a bison-based parser. (But that's just me: I have a somewhat limited imagination.)

It's a detective story. Look at the clues. Follow the clues. You might even look for complete examples on the web or in books (or class notes or whatever) that actually do useful (or at least functional) things with lex-based scanners and bison-based parsers.

If you have further questions, then post your progress and ask specific questions. Examine the messages and examine the code. Ask about anything that you don't understand, but be specific

Regards,

Dave

Footnote: The original Lexical expression scanner, named lex, has been implemented on many systems. The GNU version, called flex, is available on Linux systems and also cygwin/Window systems. On my systems, "lex" is just a symbolic link to "flex."

The "yacc" program (yet another compiler-compiler) has also been implemented on many systems. My Linux system has Bison, the GNU spinoff of yacc. It differs in some details, but the funcitonality is more-or-less upward compatible. There is also a separt "yacc", not just a symbolic link to Bison. I don't know its pedigree.

Anyhow, these programs and their spinoffs have undergone lots of changes over the years in varyingly-successful attempts to keep compatible with later revisions of currently-available C compilers.

Bottom line: unless you are using the exact same versions of lex/flex and yacc/bison as the original authors, some of the examples that you find on the web or in books may not work. (Some of them might not have been very good to start with. Don't get me started...)

They may require minor fixups or they may require major surgery, or they may be best handled by throwing them away and starting with documentation for your version of the tools.

A final note:
My compiler-writing friends (from back in the 70's) tell me that as much as they enjoyed playing with lex. serious efforts would have most of the functionality (the state machines associated with the grammar productions) would be handled by (the much more powerful) yacc. Debugging was easier when the scanner was very simple. Or that's how I remember it from so long ago.

davekw7x · #5 24-Dec-2007, 10:13

Quote:

Originally Posted by akshara.sinha

I...I have written a code...My code... I declared PLUS, MINUS, ... I still get these errors:

Where did you declare those things? In parse.y? How the heck would you think gcc could find them when you compile scan.c?

What operating system are you using? Where did your version of flex (or is it lex?) come from. What about bison? How are you compiling? What the heck is bison.simple?

Look at my previous post to see how to get bison to create a header file. If you put an #include statement in scan.l as was shown in the other scan.l post in this thread, it will make the definitions from parse.y available to gcc when it compiles scan.c.

Then you will, maybe, see the errors of the original post in this thread. Go from there.

Regards,

Dave

Footnote: I hope you two guys give credit for the scan.l and parse.y files that you posted. Saying "i have written..." and "My code..." implies some originality.

P.S.
Note to moderator: If there are any additional posts in this thread, I respectfully suggest that the thread be moved to the "Miscellaneous Program Forum," since I think further issues may be more related to flex and bison rather than C. (And definitely not C++, since there is no C++ involved.) If you do move the thread, then this P.S. can be deleted.)

davekw7x · #6 24-Dec-2007, 11:57

Quote:

Originally Posted by davekw7x

Now, when you run flex on a file,...

flex scan.l

.
.
.

Code:

scan.l:33: error: ‘yy_flex_debug’ undeclared (first use in this function)
scan.l:33: error: (Each undeclared identifier is reported only once
scan.l:33: error: for each function it appears in.)

Note that I did not claim to be a flexpert. If I were, I would have immediately recognized that to use yy_flex_debug, you invoke flex with a "-d" command-line option (lex didn't have this option or variable in the olden days, as I recall---but I could be wrong).

So, you don't have to add the extra line that I showed if you do the following:

flex -d scan.l

This will be very useful to find the numerous bugs in the lexer, if we ever get that far. You really don't want to debug a lexer that was compiled without the "-d" (at least I don't).

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
Flex, bison multifunction calculator	annatsos	C Programming Language	6	03-May-2007 10:50

Flex and bison coding

Re: Flex and bison coding

Flex and bison coding

Re: Flex and bison coding

Re: Flex and bison coding

Re: Flex and bison coding