[antlr-interest] Building a tree grammar expression to recognize arithmetic expressions

[John B. Brodie]

On Sun, 2010-08-08 at 17:02 +0100, Alex Storkey wrote:
> Thanks!
> 
> Now I'm getting the error:
> [fatal] rule expression has non-LL(*) decision due to recursive rule
> invocations reachable from alts 1,2. Resolve by left-factoring or using
> syntactic predicates or using backtrack=true option.
> 
> Which I guess kinda makes sense, but how do I go about sorting it? Just to
> reiterate, the rules I have are as follows:
> 
> expression
>     :    term | ^(MINUS term);
> 
> term
>     :    constant | variable | ^(operator expression expression);
> 
> 

i am assuming that the ambiguity is because you are using the MINUS
token in your AST to indicate both the unary operation of Negation and
the binary operation of Subtraction.

i would suggest that you make your parser construct different root node
tokens for these two things. so your *PARSER* rule for expression
becomes something like:

expression : term | ( m=MINUS term -> ^(NEGATE[$m] term) ) ;

where NEGATE is an imaginary token that you have specified in a tokens{}
block before any rules in the parser grammar. and then the *TREE* rule
for expression becomes:

expression : term | ^(NEGATE term) ;

> On 8 August 2010 16:41, John B. Brodie <jbb at acm.org> wrote:
> 
> > Greetings!
> >
> > the ^ meta-operator in the suffix position is a tree construction
> > operation and is NOT valid for tree recognition. you should be getting a
> > warning similar to:
> >
> > warning(149): treeTest.g:0:0: rewrite syntax or operator with no output
> > option; setting output=AST
> >
> > or if you have already set the output=AST in your options{} block then
> > this warning is masked. change your rule to:
> >
> > expression : term | ^(MINUS term) ;
> >
> > On Sun, 2010-08-08 at 15:54 +0100, Alex Storkey wrote:
> > > Okay, sorry to keep posting but I've managed to get the antlrworks
> > debugger
> > > working on my tree grammar and I have discovered the problem.
> > >
> > > It seems like instead of the rule *expression* consuming the MINUS
> > symbol,
> > > the minus symbol is ignore by the expression rule and consumed by the
> > > *term*rule, specifically this part:
> > > ^(operator expression expression)
> > > even when I try it on a really simple AST like (- 1) - obviously there is
> > > only one expression here, so the wrong rule is being invoked. What's up
> > with
> > > that?
> > >
> > >
> > > On 8 August 2010 10:11, Alex Storkey <alex at storkey.co.uk> wrote:
> > >
> > > >
> > > >
> > > > On 7 August 2010 19:19, Junkman <j at junkwallah.org> wrote:
> > > >
> > > >> Hi Alex,
> > > >>
> > > >> Alex Storkey wrote:
> > > >> > Hi, it's my first time posting in a mailing list like this so go
> > easy on
> > > >> me
> > > >> > if I'm breaking some etiquette or anything :)
> > > >> >
> > > >> > I'm trying to construct an expression in my tree grammar to
> > recognize an
> > > >> AST
> > > >> > of simple mathematical expressions like 1+(-(a-b)) in tree format of
> > (+
> > > >> 1 (-
> > > >> > (- a b))) that is generated by my parser grammar.
> > > >> >
> > > >> > I've tried a couple of different approaches and I can't figure out
> > where
> > > >> I'm
> > > >> > going wrong. Could someone explain what's wrong with the following
> > two
> > > >> > expressions:
> > > >> > expression
> > > >> >     :    (MINUS^)? term;
> > > >>
> > > >> If I understand you correctly, you are asking about writing tree
> > parser
> > > >> grammar.
> > > >>
> > > >> Does Antlr even compile the grammar (i.e., generate a tree parser)
> > with
> > > >> the above rule?  I think the rule must be of the form of rewrite
> > rules.
> > > >>
> > > >> J
> > > >>
> > > > Yes, that sounds about right. I have my lexer and parser grammar set up
> > to
> > > > generate an AST and I'm trying to write a tree grammar to read the AST
> > and
> > > > print some information about it, but I'm struggling to construct a tree
> > to
> > > > interpret my AST.
> > > >
> > > > All of my grammars compile fine - is there a reason they shouldn't?
> > > >
> > > > --
> > > > Alex Storkey <alex at storkey.co.uk>
> > > >
> >
> > hope this helps...
> >    -jbb
> >
> >
> >
> >
> 
>