home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / compiler / 1415 < prev    next >
Encoding:
Internet Message Format  |  1992-08-20  |  2.1 KB
  1. Path: sparky!uunet!stanford.edu!rutgers!faatcrl!iecc!compilers-sender
  2. From: twpierce@amhux1.amherst.EDU (Tim Pierce)
  3. Newsgroups: comp.compilers
  4. Subject: Re: constant folding at parse time
  5. Keywords: parse, attribute
  6. Message-ID: <92-08-114@comp.compilers>
  7. Date: 19 Aug 92 15:53:46 GMT
  8. References: <92-08-040@comp.compilers> <92-08-097@comp.compilers>
  9. Sender: compilers-sender@iecc.cambridge.ma.us
  10. Reply-To: Tim Pierce <twpierce@amhux1.amherst.EDU>
  11. Organization: Amherst College, Amherst MA
  12. Lines: 40
  13. Approved: compilers@iecc.cambridge.ma.us
  14.  
  15. The discussion about constant folding has intrigued me a little bit, and
  16. I've been a little stumped figuring out how I would implement this in the
  17. general case.  Writing code into mknode() to fold the addition or
  18. multiplication of two nodes with constant value makes sense to me, for
  19. example.  But what about an expression such as "4 + y + 4"?  As I see it,
  20. a shift-reduce parser following the rule
  21.  
  22. expr -> expr + expr
  23.       | CONST
  24.       | ID
  25.  
  26. would process this expression as follows:
  27.  
  28. 4 + y + 4
  29. CONST + y + 4
  30. expr + y + 4
  31. expr + ID + 4
  32. expr + expr + 4
  33. expr + 4
  34. expr + CONST
  35. expr + expr
  36. expr
  37.  
  38. At no time does the parser have any inkling that there are two constant
  39. terms in this expression that can be folded together.  In order to encode
  40. this recognition, I imagine you'd have to fix the parser to rearrange
  41. terms in some order that would permit constant folding.  I've checked the
  42. dragon book (second edition) but they seemed pretty vague on
  43. implementation ideas.  Any thoughts?
  44. -- 
  45. Tim Pierce, twpierce@amherst.edu, (BITnet: TWPIERCE@AMHERST)
  46. [The only approach I've seen is pretty much brute force -- when you have a
  47. subtree with multiple instances of an associative operator, flatten the
  48. tree into a list, sort the list to put all the constants together,
  49. collapse the constants, and remake a tree.  It is my dim recollection that
  50. the Ritchie PDP-11 compiler actually did this, because you can get
  51. significant savings in some kinds of addressing expressions. -John]
  52. -- 
  53. Send compilers articles to compilers@iecc.cambridge.ma.us or
  54. {ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
  55.