[antlr-interest] left recursion removal

Sébastien Kirche sebastien.kirche at gmail.com
Wed Jul 6 12:19:39 PDT 2011


Hi,

the language for which I am trying to build the grammar has 2 flavors
of if-then-else constructs
- a single line : if <condition> then <statement> [else <statement>]
- a multi line : if <condition> then <statements> [else <statements>] end if

I have defined the following (partial) :

codeBlock
	:	(compoundStatement)*
	;

compoundStatement
	:	(
			ifStatement
		|	singleStatement
		) (';' | EOL)
	;
	
singleStatement
	:	localVariableDeclaration
	|	funCall
	|	'return' expression
	;

ifStatement
	:	singleLineIf
	|	multiLineIf
	;

singleLineIf
	:	'if' expression 'then' singleStatement EOL
	;

multiLineIf
	:	'if' expression 'then' codeBlock 'end if'
	;


I understand why the naive ifStatement fails with the following "
[fatal] rule ifStatement has non-LL(*) decision due to recursive rule
invocations reachable from alts 1,2.  Resolve by left-factoring or
using syntactic predicates or using backtrack=true option."

I would like to avoid general backtracking, so after searching for a
while and reading the article
http://www.antlr.org/wiki/display/ANTLR3/How+to+remove+global+backtracking+from+your+grammar
I have tried first

ifStatement
	:	'if' expression 'then' (singleStatement EOL)=> singleLineIf
	| 	multiLineIf
	;

or

ifStatement
	:	'if' expression 'then' (singleStatement EOL | codeBlock 'end if')
	;

But they fail both with the same fatality.
How this case should be processed ?
-- 
Sébastien Kirche


More information about the antlr-interest mailing list