Re: Fusion-ifying proto parse trees

Joel de Guzman wrote:
> Joel de Guzman wrote:

> Actually, "flattening" is a bit of a misnomer. I think the correct
> word is "collapse". For example:
>
>     a + b + c * d
>
> gives us:
>
>     +
>    / \
>   a   +       plus(a, plus(b, multiply(c, d)))
>      / \
>     b   *
>        / \
>       c   d

Oops, that's wrong. Implicit associativity is from left to
right, so:

        +
      /   \
     +     *    plus(plus(a, b), multiply(c, d))
    / \   / \
   a   b c   d

> If in our language, we know that + is *associative*, we can use
> that knowledge to collapse the + nodes from binary to n-ary:
>
>      +
>    / | \
>   a  b  *     plus(a, b, multiply(c, d))
>        / \
>       c   d
>
> Regards,

--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
Using Tomcat but need to do more? Need to support web services, security?
Get stuff done quickly with pre-integrated technology to make your job easier
Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642