[antlr-interest] Re: Building trees with the correct associativity
Dean Tribble
tribble at e-dean.com
Sun Jan 16 12:05:21 PST 2005
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.
More information about the antlr-interest
mailing list