Left-recursion in ANTLR

Question

The stm and stmList gives me this error, it seems that ANTLR see it like a possible infinite recursion loop. How can I avoid it? The following sets of rules are mutually left-recursive [stmList]

stmList: stm stmList | ;
stm: ifStm | whStm;

ifStm: ifPart elifPart* elsePart?;
ifPart: IF LB exp RB CLB stmList CRB;
elifPart: ELIF LB exp RB CLB stmList CRB;
elsePart: ELSE CLB stmList CRB;

whStm: WHILE LB exp RB CLB stmList CRB;

LB: '(';
RB: ')';
CLB: '{';
CRB: '}';
WHILE: 'While';
IF: 'If';
ELIF: 'Elif';
ELSE: 'Else';

The stmList rule is right-recursive. There's no left recursion here. — Chris Dodd
@DuyDuy that could be, but not with the rules you posted. You've trimmed down the grammar too much. If you decide to strip the code/grammar and post it on SO, always make sure the original error is still being produced. I recommend posting the entire grammar. — Bart Kiers
@BartKiers you're right. I haven't define production for forStm that has been trimmed down — Duy Duy

Mike Lischke Mike Lischke · Accepted Answer · 2021-04-15T07:08:34

This is probably because of the empty alt in stmList, though I also wonder why this error comes up. It doesn't seem right. However, I recommend not to use empty alts anyway, unless you guard the other alt(s) with a predicate and "call" the containing rule unconditionally. This can easily lead to problems when you forget that. Instead remove the empty alt and make the call optional:

stmList: stm stmList;
elsePart: ELSE CLB stmList? CRB;

Additionally, stmList looks pretty much like you would do such a definition in yacc, where no EBNF suffixes are possible. Instead just write:

stmList: stm+;

Left-recursion in ANTLR

1 Answers