Re: constant folding at parse time

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

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