Simple constant folding in bison parser (Jeremy Fitzhardinge)
Wed, 5 Aug 1992 05:59:15 GMT

          From comp.compilers

Related articles
Simple constant folding in bison parser (1992-08-05)
Re: Simple constant folding in bison parser (1992-08-10)
Re: Simple constant folding in bison parser (1992-08-17)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Jeremy Fitzhardinge)
Organization: Softway Pty Ltd
Date: Wed, 5 Aug 1992 05:59:15 GMT
Summary: Can a bison grammar do this?
Keywords: yacc, optimize, question

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

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.
-- 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]

Post a followup to this message

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