[antlr-interest] Re: Building trees with the correct associativity

[Dean Tribble]

I'm replying to a message that I saw in the archives.  I recently
struggled with building left-associative trees (for the E language), and
stumbled upon a minimal approach that works nicely.

<pauljlucas at m...> wrote:
>     If I have:
>
>         addExpr
>             : e1:mulExpr
>               (ao:addOp! e2:mulExpr!
>                   {
>                 ## = #([ADD_EXPR,"ADD_EXPR"], ao, e1, e2);
>             }
>               )*
>             ;
>
>     then my trees get built the wrong way, e.g.:
>
>         5 - 2 + 3
>
>     is as if it were:
>
>         5 - (2 + 3)
>
>     which is wrong.  Maybe I'm being a but slow, but it's not
>     immediately clear how to build the tree the other way, i.e.:
>
>         (5 - 2) + 3


I wanted "5 - 2 + 3" to result in:

#([CallExpr], ([CallExpr], 5, "-", 3), "+", 3)

so I did not need to reorder the operator.  Here's what finally worked
for me:

//+ and - are left associative
add         :   mult ({##=#([CallExpr],##);}    ("+" | "-") mult)*   ;

// *, /, //, %, and %% are left associative
mult        :   pow ({##=#([CallExpr],##);}     ("*" | "/" | "//" | "%"
| "%%") pow)*  ;
...

Note that since I do not use the caret for those operators, they could
easily be pushed into their own addOp rule.