CODEWITHSUNDEEP
recursionantlrambiguity
Luc
Luc

Reputation: 9

Antlr and left-recursive rules

I am trying to write a grammar using ANTLR, but I can't understand how antlr works with recursive choices.

I read lots of articles and forums, but can't solve my problem...

Here is a small part of my grammar:

grammar MyGrammar;

ComponentRef :
    IDENT ('[' Expression (',' Expression)* ']')?
;

Expression:
    ComponentRef ('(' FunctionArguments ')')?
;

FunctionArguments:
    Expression (',' Expression)*
;

IDENT: ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*;

I still don't understand why it doesn't work... there is no ambiguity! Isn't it?

Here is some examples of code my grammar should work with :

a
a[b,c]
a[b[c], d]
func(a)
func(a,b,c)
func[a](b,c)
func(a[b], c[d])
func[a](b[c])

Thank you by advance!

Upvotes: 0

Views: 4694

Answers (2)

Bart Kiers
Bart Kiers

Reputation: 170148

First, be sure to understand lexer and parser rules. Also read the ANTLR Mega Tutorial.

The code only uses lexer rules, which won't work. Although even lexer rules can be recursive (in ANTLR grammars), they are best avoided. Rather, most rules should be parser rules:

componentRef :
    IDENT ('[' expression (',' expression)* ']')?
;

expression:
    componentRef ('(' functionArguments ')')?
;

functionArguments:
   expression (',' expression)*
;

IDENT: ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*;

The grammar above won't recognize the input you've posted, but there are no error anymore. A grammar that recognizes the input you've posted, could look like this (untested!) grammar:

parse
 : expr* EOF
 ;

expr
 : IDENT (index | call)*
 ;

index
 : '[' expr_list ']'
 ;

call
 : '(' expr_list ')'
 ;

expr_list
 : expr (',' expr)*
 ;

IDENT
 : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'_'|'0'..'9')*
 ;

SPACE
 : (' ' | '\t' | '\r' | '\n')+ {skip();}
 ;

Upvotes: 5

john k
john k

Reputation: 6615

I'm assuming your capitol Expressions is an error. You probably meant to type lowercase.

How can you say there's no ambiguity? expressions call functionArguments, functionArguments calls expressions. -1

Upvotes: 0

Related Questions