[antlr-interest] How to resolve the left-recursion problem?
Juergen Reuter
reuter at ipd.uka.de
Thu Jun 28 03:51:34 PDT 2007
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