[antlr-interest] Left recursive grammar

[Sam Harwell]

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