# Re: constant folding at parse time

## Tim Pierce <twpierce@amhux1.amherst.EDU>Wed, 19 Aug 1992 15:53:46 GMT

From comp.compilers

Related articles
Re: Simple constant folding in bison parser drw@kronecker.mit.edu (1992-08-10)
constant folding at parse time wjw@eb.ele.tue.nl (1992-08-17)
Re: constant folding at parse time markh@csd4.csd.uwm.edu (1992-08-17)
Re: constant folding at parse time twpierce@amhux1.amherst.EDU (Tim Pierce) (1992-08-19)
Re: constant folding at parse time scott@bbx.basis.com (1992-08-20)
Re: constant folding at parse time wjw@eb.ele.tue.nl (1992-08-21)
Re: constant folding at parse time buehlman@iwf.mabp.ethz.ch (1992-08-21)
Re: constant folding at parse time drw@euclid.mit.edu (1992-08-24)
Semantics Tools eifrig@beanworld.cs.jhu.edu (1992-08-25)
Re: Semantics Tools db@dcs.ed.ac.uk (Dave Berry) (1992-08-26)
[2 later articles]
| List of all articles for this month |

 Newsgroups: comp.compilers From: Tim Pierce Organization: Amherst College, Amherst MA Date: Wed, 19 Aug 1992 15:53:46 GMT References: 92-08-040 92-08-097 Keywords: parse, attribute

The discussion about constant folding has intrigued me a little bit, and
I've been a little stumped figuring out how I would implement this in the
general case. Writing code into mknode() to fold the addition or
multiplication of two nodes with constant value makes sense to me, for
example. But what about an expression such as "4 + y + 4"? As I see it,
a shift-reduce parser following the rule

expr -> expr + expr
| CONST
| ID

would process this expression as follows:

4 + y + 4
CONST + y + 4
expr + y + 4
expr + ID + 4
expr + expr + 4
expr + 4
expr + CONST
expr + expr
expr

At no time does the parser have any inkling that there are two constant
terms in this expression that can be folded together. In order to encode
this recognition, I imagine you'd have to fix the parser to rearrange
terms in some order that would permit constant folding. I've checked the
dragon book (second edition) but they seemed pretty vague on
implementation ideas. Any thoughts?
--
Tim Pierce, twpierce@amherst.edu, (BITnet: TWPIERCE@AMHERST)
[The only approach I've seen is pretty much brute force -- when you have a
subtree with multiple instances of an associative operator, flatten the
tree into a list, sort the list to put all the constants together,
collapse the constants, and remake a tree. It is my dim recollection that
the Ritchie PDP-11 compiler actually did this, because you can get
significant savings in some kinds of addressing expressions. -John]
--

Post a followup to this message