CODEWITHSUNDEEP
javarecursionantlrantlr4
Depp
Depp

Reputation: 51

How to fix mutual left recursion in ANTLR4

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 | ε

See this answer here

How might I go about this?

Upvotes: 1

Views: 229

Answers (1)

Bart Kiers
Bart Kiers

Reputation: 170148

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
;

Upvotes: 3

Related Questions