[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