Simple constant folding in bison parser

I'm writing an experimental compiler for a C-like language, mainly to
experiment with optimisation. I'm not very interested in writing my own
scanner and parser, so I'm using flex and bison.


One thing that occured to me was that the grammar can be made to recognize
simple constant expressions, and generate a parse tree node for the value
of the expression rather than the nodes for the operator and constant
arguments.


The restult looked something like this (much abbreviated):


%left '+'
%left '*'
%right UNARY


expr : factor
| expr '+' expr { $$ = mknode(Add, $1, $3); }
| expr '*' expr { $$ = mknode(Mult, $1, $3); }
/* etc */


factor : VAR { $$ = mkvar($1); }
| const { $$ = mknum($1); }
| '-' expr %prec UNARY { $$ = mkun(Neg, $2); }


const : INT { $$ = $1; }
| const '+' const { $$ = $1+$3; }
| const '*' const { $$ = $1*$3; }


This has a number of problems. Firstly, it immedately introduces
reduce/reduce conflices, because something like "2+3" can reduce to either
(+ 2 3) or (5). The other problem is that an expression like 3+x will not
parse, because the parser gets to a state like


const '+' . const


so the VAR token is a parse error. What I would like it to do for such an
input is to keep shifting until it gets the third token and can thus tell
whether it should reduce to "const '+' const" or "expr '+' expr". I have
a suspicion that this is something an LR parser can't do...


Is there some way this can be done using this or another approach with
yacc (or even some other freely available parser generator - this is less
popular, since I don't really want to rewrite what I have).


Thanks. Mail me replies, I'll summarize later.
--
jeremy@softway.sw.oz.au ph:+61 2 698 2322-x122 fax:+61 2 699 9174
[I never tried to do in in the parser, but rather in the routines that build
the parse tree, mknode() in this case. -John]
--

Return to the comp.compilers page.
Search the comp.compilers archives again.