How to fix mutual left recursion in ANTLR4

Question

I have two rules that are mutually left recursive:

frag : ID
   | NUMBER
   | TRUE
   | FALSE
   | expr
;

expr: frag (PLUS | MINUS) frag
   | LBR expr RBR
   | frag
;

And the issue is: The following sets of rules are mutually left-recursive [frag, expr]

I'm new to ANTLR4 and am having difficulty removing this mutual left recursion.

I understand that left recursion can be removed such that:

A -> Aa | b
-- becomes --
A -> bR
R -> aR | ε

How might I go about this?

Bart Kiers · Accepted Answer · 2020-11-13T07:56:57.880

3

Indirect left recursion isn”t allowed, but direct left recursion is. This will work fine:

expr: expr (PLUS | MINUS) expr
   | LBR expr RBR
   | ID
   | NUMBER
   | TRUE
   | FALSE
;

And if you still want a separate frag rule, you can do this of course:

frag : ID
   | NUMBER
   | TRUE
   | FALSE
;

expr: expr (PLUS | MINUS) expr
   | LBR expr RBR
   | frag
;

edited Nov 13 '20 at 07:56

answered Nov 13 '20 at 06:24

Bart Kiers

2

As shown by Bart, indirect left recursion (ILR) can be "fixed" using unfolding ("inlining" the RHS of a rule into another `a : b c; b : d e f; => a : (d e f) c;`), followed by ungrouping (basically distribution `z : (a b) c => z : a c | b c`), and reordering the alts (`a : b | c => a : c | b`). If it involves only one rule, you only need apply ungrouping and reordering to that rule. You can choose any rule to unfold, but some rules make better choices. As yet, there is no tool that automatically detects and removes ILR, but it could be done automatically for these easy cases. – kaby76 Nov 13 '20 at 11:50

1 Answers1