[antlr-interest] could not even do k=1 for decision xx; reason: timed out

[Tomasz Jastrzebski]

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)
 
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.
 
I am stucked. Please advice. The overall goal is to make ANTLR create my own "strongly typed" AST tree structure using, in this case, my BinaryExpression and UnaryExpression nodes.
 
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>, "ANTLR Interest Mailing List" <antlr-interest at antlr.org>
Date: Saturday, August 8, 2009, 6:36 AM


Tomasz Jastrzebski wrote:
> I agree that
> additiveExpression
>   : multiplicativeExpression ('+' | '-') multiplicativeExpression
>   | multiplicativeExpression
>   ;
> is equiwalent to:
>  additiveExpression
>   : multiplicativeExpression (('+' | '-') multiplicativeExpression)?
>   ;
> Why it does not generate the same AST tree I do not know. May be it is a bug - I have to investigate.

It should generate the same AST - both are handled by the default tree rule, and produce a flat list of the tokens. However, if you put the output rule *inside* the optional subrule, it only applies if the optional subrule matches. Thus the case where the subrule doesn't match produces a single node, and where it does it produces the output you specify.

> Goot point about the "a + b + c" case.
>  Thanks,
>  Tomasz
> 
> --- On *Fri, 8/7/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: Friday, August 7, 2009, 6:29 PM
> 
>     Tomasz Jastrzebski wrote:
>      > But this creates a different tree, while what I need is plain and
>     simple structure like this:
>      >   +
>      >  / \
>      > /   \
>      > a   *
>      >    / \
>      >   /   \
>      >  c     d
> 
>     No, it does exactly what the one you provided does. The output rule
>     is only observed if the subrule matches, otherwise it follows the
>     default. It is identical in effect to the rule you provided...
> 
>     additiveExpression
>       : e1=multiplicativeExpression ((o='+'|o='-')
>          e2=multiplicativeExpression ->
>          BINARY_EXPRESSION<BinaryExpression>[$o.text, $e1.tree, $e2.tree])?
>       ;
> 
>     (I've corrected where it should be a question mark, not * - * would
>     accept chained expressions, but the tree rewrite would be awkward)
> 
>     If the subrule matches, the rewrite (which I don't quite understand)
>     applies. If it doesn't, then the default (just emit the token as a
>     single node) takes place.
> 
>     Your grammar doesn't appear to support expressions like
> 
>     3 + 4 - 5
>     or
>     2 * 3 / 5
> 
>     Sam
> 
>      > --- On *Fri, 8/7/09, Sam Barnett-Cormack
>     /<s.barnett-cormack at lancaster.ac.uk
>     <http://us.mc521.mail.yahoo.com/mc/compose?to=s.barnett-cormack@lancaster.ac.uk>>/*
>     wrote:
>      >
>      >
>      >     From: Sam Barnett-Cormack <s.barnett-cormack at lancaster.ac.uk
>     <http://us.mc521.mail.yahoo.com/mc/compose?to=s.barnett-cormack@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
>     <http://us.mc521.mail.yahoo.com/mc/compose?to=tdjastrzebski@yahoo.com>>
>      >     Date: Friday, August 7, 2009, 2:30 PM
>      >
>      >     Tomasz Jastrzebski wrote:
>      >
>      >      > But the problem is that I cannot do that since I need to catch
>      >     reference to each expression and operator to build nice AST tree.
>      >     The real code looks more like this:
>      >      >  additiveExpression
>      >      >  : e1=multiplicativeExpression (o='+' | o='-')
>      >     e2=multiplicativeExpression ->
>      >     BINARY_EXPRESSION<BinaryExpression>[$o.text, $e1.tree, $e2.tree]
>      >      >  | multiplicativeExpression
>      >      >  ;
>      >
>      >     Still left-factor it.
>      >
>      >     additiveExpression
>      >       : e1=multiplicativeExpression ((o='+'|o='-')
>      >     e2=multiplicativeExpression ->
>      >     BINARY_EXPRESSION<BinaryExpression>[$o.text, $e1.tree,
>     $e2.tree])*
>      >       ;
>      >
>      >     This means that the output expression is only considered if the
>      >     optional subrule matches - otherwise it uses the default output
>      >     (just e1).
>      >
>      >     -- Sam Barnett-Cormack
>      >
>      >
> 
> 
>     -- Sam Barnett-Cormack
> 
> 


-- Sam Barnett-Cormack



      
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20090808/556083d1/attachment.html