Solving ANTLR Mutually left-recursive rules

3
votes

the 'expr' rule in the ANTLR grammar below obviously mutually left-recursive. As a ANTLR newbie it's difficult to get my head around solving this. I've read "Resolving Non-LL(*) Conflicts" in the ANTLR reference book, but I still don't see the solution. Any pointers?

LPAREN : ( '(' ) ;
RPAREN : ( ')' );
AND : ( 'AND' | '&' | 'EN' ) ;
OR : ( 'OR' | '|' | 'OF' );
NOT : ('-' | 'NOT' | 'NIET' );
WS :  ( ' ' | '\t' | '\r' | '\n' ) {$channel=HIDDEN;}  ;
WORD :  (~( ' ' | '\t' | '\r' | '\n' | '(' | ')' | '"' ))*;

input : expr EOF;
expr : (andexpr | orexpr | notexpr | atom);
andexpr : expr AND expr;
orexpr :  expr OR expr;
notexpr : NOT expr;
phrase : '"' WORD* '"';
atom : (phrase | WORD);
1
antlrantlr3

1 Answers

5
votes

I would suggest to have a look at the example grammers on the antlr site. The java grammar does what you want.

Basicly you can do something like this:

expr : andexpr;
andexpr : orexpr (AND andexpr)*;
orexpr : notexpr (OR orexpr)*;
notexpr : atom | NOT expr;

The key is, that every expression can end to be an atom.