[antlr-interest] could not even do k=1 for decision xx; reason: timed out
Tomasz Jastrzebski
tdjastrzebski at yahoo.com
Sat Aug 8 12:47:47 PDT 2009
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 <s.barnett-cormack at lancaster.ac.uk> wrote:
From: Sam Barnett-Cormack <s.barnett-cormack at lancaster.ac.uk>
Subject: Re: [antlr-interest] could not even do k=1 for decision xx; reason: timed out
To: "Tomasz Jastrzebski" <tdjastrzebski at yahoo.com>
Cc: "antlr-interest" <antlr-interest at antlr.org>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20090808/b9a66e55/attachment.html
More information about the antlr-interest
mailing list