[antlr-interest] Left recursive grammar

[Bart Kiers]

Hi Sam,

But of course, with the inline tree rewrite operators it looks so straight
forward! Nice one!

Regards,

Bart.


On Thu, Jul 21, 2011 at 3:52 PM, Sam Harwell <sharwell at pixelminegames.com>wrote:

> Your example is ambiguous as well as left recursive. I assume you meant one
> of the following:
>
> a : a B | A;
> a : A* B | A;
>
> The first can be written as:
>
> a : A (B^)*;
>
> The second can be written as
>
> a : A (A* B^)? | A | B;
>
> Sam
>
> -----Original Message-----
> From: antlr-interest-bounces at antlr.org
> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Luigi Iannone
> Sent: Thursday, July 21, 2011 8:00 AM
> To: ANTLR
> Subject: [antlr-interest] Left recursive grammar
>
> Hi all,
>
> I have this simple grammar
>
>
> grammar test;
> options {
>  language = Java;
>  output = AST;
> }
>
> a
>        :
>                a*B  ->^(B a*)
>                | A
>        ;
>
> B       :
>                '.B'
>        ;
>
> A       :
>                'A'
>        ;
>
>
>
>
> and I get the following output when I try to generate the parser in
> ANTRLWorks
>
> [13:48:53] error(210):  The following sets of rules are mutually
> left-recursive [a]
>
> I read on the Web that there are solutions to solve this, however they will
> mess up the associativity, which I need to keep instead.
> So, for instance, for the input
>
> A.B.B
>
> the AST tree should be
>
> ^(B ^(B A))
>
> Is there any way to change the grammar in order to eliminate the left
> recursion and obtain the above tree. I am afraid I do not get how to do it
> by just looking at what is there online about left recursive grammars.
>
> Thanks a lot for your help,
>
> Luigi
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>
>
> List: http://www.antlr.org/mailman/listinfo/antlr-interest
> Unsubscribe:
> http://www.antlr.org/mailman/options/antlr-interest/your-email-address
>