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

[Sam Barnett-Cormack]

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