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

Jim Idle jimi at temporal-wave.com
Thu Jun 28 08:18:02 PDT 2007


Juergen,

This does look like a bug, but this is actually because of this rule:

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

You are trying to rewrite Identifer and that is not there. I suspect
this is your problem.

You want:

->^(Import packageReference)

The bug is that the tool is awaiting the great error/warning message
upgrade that will arrive when the ANTLR3 parser is written in ANTLR3
:-), which will then tell you about this (probably ;-)).

Jim

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org [mailto:antlr-interest-
> bounces at antlr.org] On Behalf Of Juergen Reuter
> Sent: Thursday, June 28, 2007 3:52 AM
> To: antlr-interest at antlr.org
> Subject: Re: [antlr-interest] How to resolve the left-recursion
> problem?
> 
> 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.



More information about the antlr-interest mailing list