[antlr-interest] could not even do k=1 for decision xx; reason: timed out
Sam Barnett-Cormack
s.barnett-cormack at lancaster.ac.uk
Sat Aug 8 03:36:10 PDT 2009
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
More information about the antlr-interest
mailing list