This approach was borrowed right from Terence's book, page 187. He even stated that it looked odd, but made sense - explanation follows. Anyway, I tested it. With rewrite like (multExpr -> multExpr) it works as expected, without it does not. The point is that I need binary tree. Rewrite like: multExpr : primaryExpr ((o='*' | o='/') e=primaryExpr -> ^($o $e) )* ; or:
multExpr : (primaryExpr -> primaryExpr) ( (o='*' | o='/') e=primaryExpr -> ^($o $multExpr $e) )* ; produces desired default AST binary tree. Just how modify it so it builds my binary tree... I cannot figure this out. Thanks, Tomasz --- On Sat, 8/8/09, Sam Barnett-Cormack <[email protected]> wrote: From: Sam Barnett-Cormack <[email protected]> Subject: Re: [antlr-interest] could not even do k=1 for decision xx; reason: timed out To: "Tomasz Jastrzebski" <[email protected]> Cc: "antlr-interest" <[email protected]> Date: Saturday, August 8, 2009, 2:50 PM Tomasz Jastrzebski wrote: > Thanks. > Now I understand that the only reasonable such declaration must look like: > multExpr > : primaryExpr (('*' | '/') primaryExpr)* > ; > After adding rewrite rules this may look like that: > addExpr > : (multExpr -> multExpr) ( (o='+' | o='-') e=multExpr -> ^($o $addExpr $e) )* > ; > multExpr > : (primaryExpr -> primaryExpr) ( (o='*' | o='/') e=primaryExpr -> ^($o >$multExpr $e) )* > ; > (tested, it works) Well, you don't need "-> primaryExpr" in the first subrule there - it's implicit. To make your tree nodes binary only, I don't think you can use EBNF like that, I think you'll need to use recursion. After all, you want 3 + 2 - 4 to produce a tree like + / \ 3 - / \ 2 4 (Whether the - or + is at the root doesn't matter) I don't think this is possible with just EBNF constructs. You need it to parse 2-4 as an expression that produces a subtree, and that expression be picked up by the match of the + operator. Alternatively, you could produce a non-binary tree like + /|\ 3 2 -4 Because subtraction is associative, this is viable. Same for multiplication/division, with '/ a' becoming '* a^-1', if you care to model them via inverses as is typical in group/ring theory in mathematics. Personally, I think a binary tree is cleaner, but you have to do something much cleverer than normal EBNF to produce that, AFAICT. > I would think that now I can simply replace: > -> ^($o $addExpr $e) > with > -> ^(BIN_EXPR<BinaryExpression>[o.text, $addExpr.tree, $e.tree]>) > - but not. $addExpr.tree in the second version is always NIL. Well, $addExpr is the result of the current parser rule, as that expression appears to appear in the addExpr: rule. Of course it's going to produce odd results. -- Sam Barnett-Cormack --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "il-antlr-interest" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/il-antlr-interest?hl=en -~----------~----~----~----~------~----~------~--~---
List: http://www.antlr.org/mailman/listinfo/antlr-interest Unsubscribe: http://www.antlr.org/mailman/options/antlr-interest/your-email-address
