[antlr-interest] How to resolve the left-recursion problem?

[Juergen Reuter]

Hi all,

I have basically the same left-recursion problem as already discussed on 
this list (see 
http://www.antlr.org/pipermail/antlr-interest/2007-June/021061.html). 
Unfortunately, the "NAME ('.'^ NAME)*" trick does not work for me, as 
antlr-3.0 generates Java code, that does not compile.  This is a bug, 
right?

You should be able to reproduce the weired behavior with the following 
sample grammar:

========

grammar Grammar;
options {k=2; backtrack=true; memoize=true; output=AST;}

tokens {
   Import;
}

importDeclaration
 	:	'import' (packageReference '.' '*') ';'
         ->
         ^(Import Identifier*)
 	;

packageReference
     :    Identifier ('.'^ Identifier)*
     ;

Identifier
     :   Letter+
     ;

fragment
Letter
     :  '\u0041'..'\u005a' | '\u005f'
     ;

========

antlr-3.0 then generates the file GrammarParser.java that contains the 
following lines, starting at line 119:

                 // Grammar.g:11:18: ( Identifier )*
                 while (  ) {
                     adaptor.addChild(root_1, adaptor.create(Identifier, "Identifier"));

                 }

Consequently, javac then throws the following error at me:

GrammarParser.java:120: illegal start of expression
                 while (  ) {
                          ^
1 error

So, my question is, is there any working solution for handling 
left-recursion problem?  Or, as a workaround, what would be the correct 
while condition that I should insert into the generated code?

Many thanks for any advice!

Greetings,
Juergen



On Tue Jun 5 2007, Robin Davies wrote:

> > attribute_expression
> >  : NAME | dot_operator_exp
> >  ;
> >
> > dot_operator_exp
> >  : attribute_expression DOT NAME
> >  ;
> 
> 
> The generic way to deal with left-recursive structures is to convert 
> them to match the right side with EBNF loops: "(something)*". See page 
> 275 of the PDF manual for more details.
> 
> attribute_expression
>       :      NAME  ('.' NAME) *
>       ;
> 
> After using LALR grammars this seemed very unnatural, at first. But, 
> after gradually mind-shifting to the LL mind-set, this now seems very 
> natural. And very easy to deal with when you get to actually processing 
> the grammar! To convert this to AST, for example, you write:
> 
> attribute_expression
>       :      NAME  ('.'^ NAME) *
>       ;
> 
> and you will get exactly the tree that you want: a left-recursive tree
> structure.