non trivial constant folding

Hi.
I've been searching on the web for information about this
particular problem, as well as in my books ("Compiler
Construction" - Niklaus Wirth, and "Crafting a Compiler
with C" - Fisher/LeBlanc) but does not find anything
clear about it.


I'm parsing expression to create a tree made of nodes
that contains either "operators" or "values". This works
fine, so I've started to "optimise" the resulting tree with
a code that recursively compute all the operators that
have immediate childs that are two immediate numerical
values.


This works fine for an expression like this:


eval(1+2+3/2+4+5*8)


is translated in this tree:


+(+(+(+(1.000000,2.000000),/(3.000000,2.000000)),4.000000),*(5.000000,8.0000
00))


And optimised like this:


  Optimise + (1.000000+2.000000=3.000000)
  Optimise / (3.000000/2.000000=1.500000)
  Optimise + (3.000000+1.500000=4.500000)
  Optimise + (4.500000+4.000000=8.500000)
  Optimise * (5.000000*8.000000=40.000000)
  Optimise + (8.500000+40.000000=48.500000)


Giving this final evaluate expression:


48.500000


My problem is that I do not manage to find a clean solution
to optimise this:


eval(1+var+1)


is translated as:


+(+(1.000000,var),1.000000)


And I do not manage to optimise it.


(Of course eval(1+1+var) is optimised in "+(2.000000,var)")


I've been looking extensively on how I can reorganise my
expression tree, but do not manage to find any explanation.
I believe it's a question that's often ask (I found a question
on this subject by "Tim Pierce" in 1992 in this newsgroup,
but do not find the answer...)


Thanks in advance for any help


        Mickael Pointier


PS: Happy new year
[I've seen compilers that do that. With associative operators like +
they combine all of the operands of a set of cascaded operators into
a list or array, then sort that array to get the constants together.
-John]

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