如何修复 ANTLR4 中的相互左递归

Question

我有两个互左递归的规则：

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

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

问题是： The following sets of rules are mutually left-recursive [frag, expr]

我是 ANTLR4 的新手，很难删除这个相互左递归。

我知道可以删除左递归，这样：

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

见this answer here

我该怎么做？

Answer 1

不允许间接左递归，但允许直接左递归。这将正常工作：

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

如果您仍然想要一个单独的 frag 规则，您当然可以这样做：

frag : ID
   | NUMBER
   | TRUE
   | FALSE
;

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

How to fix mutual left recursion in ANTLR4