[antlr-interest] deleting a left-recursive

Jim Idle jimi at temporal-wave.com
Sat May 3 09:07:35 PDT 2008


Basically you need to step away from the grammar you have and consult one of the example grammars (the one that is closest to your problem, perhaps Java or C). In this example grammar, find the expression rule and note how this is a set of or rules starting with expression, that descends in order of lowest to highest precedence of operators, and that the end of the sequence is the set of things that don't break down any further such as ID, INTEGER and so on.

This is where you are going wrong as your basic construct for the expressions is wrong. Look in the Wiki for articles on expression trees as well. You are possibly trying to type in your grammar from some spec and you should note that such specs are generally written with tools like yacc/bison more in mind than antlr and you need to mind translate them :-). If you can afford it, then the ANTLR book would be a good idea for you and will tell you a lot before you get to the compiler lessons :-)

Jim


> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of jabon
> Sent: Saturday, May 03, 2008 8:18 AM
> Cc: ANTLRDev Interest
> Subject: Re: [antlr-interest] deleting a left-recursive
> 
> oki, I ve reduce the prob,
> now I have this
> 
> expression
>     :      (
>            expression
> 
> (T_Ne|T_Eq|T_Ge|T_Le|T_Lt|T_Gt|T_And|T_Mod|T_Star|T_Slash|T_Iff|T_Impli
> es|T_Or|T_Plus|T_Minus)
> 
>            expression
>        )
>          ;
> 
> it's a simple left recuse but in the doc this become this.
> a : a b |b; ==> a : b+;
> 
> So I ve tried
> 
> 
> expression
>     :      (
> 
> (T_Ne|T_Eq|T_Ge|T_Le|T_Lt|T_Gt|T_And|T_Mod|T_Star|T_Slash|T_Iff|T_Impli
> es|T_Or|T_Plus|T_Minus)
> 
>            expression+
>        )
>          ;
> 
> but That doesn't work.
> any idea??
> 
> thanks
> 
> a++
> 
> Johannes Luber a écrit :
> > jabon schrieb:
> >> hi all,
> >>
> >> I have a little probleme with my grammar , I have a left recursive
> >> and I have lot of diffcult to remove this.  I need a little help (I
> m
> >> not an expert sorry and compilations lessons are far away)
> >>
> >> expression
> >>    : T_LParent expression T_RParent
> >>    | binaryExpression
> >>    | castExpression
> >>    | desig | literal
> >>    | newExpression
> >>    | quantifierExpression
> >>    | unaryExpression
> >>    ;
> >>
> >>
> >> binaryExpression
> >>    : (expression (T_Ne|T_Eq|T_Ge|T_Le|T_Lt|T_Gt) expression)
> >>    |(expression (T_And|T_Mod|T_Star|T_Slash) expression)
> >>    |(expression (T_Iff|T_Implies|T_Or|T_Plus|T_Minus) expression);
> >>
> >> thanks a lot
> >>
> >> a+++
> >>
> >
> > You've reminded me that I didn't posted my tutorial about
> > left-recursion removal yet. After 1 hour or so intense formatting you
> > can see the result here:
> > <http://www.antlr.org/wiki/display/ANTLR3/Left-Recursion+Removal>.
> > Hopefully it is helpful enough. :)
> >
> > Johannes






More information about the antlr-interest mailing list