Wed, 19 Aug 1992 15:53:46 GMT

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

Newsgroups: | comp.compilers |

From: | Tim Pierce <twpierce@amhux1.amherst.EDU> |

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.