ANTLR4 自互左递归

Question

是否有简单的转换或解决方法来使它在 ANTLR4 中工作？

a : a p
  | b q
  | c
  ;

b : b r
  | a s
  | d
  ;

即a和b是自左递归和互左递归，其他规则（c、d、p、q、r、s) 只是简单规则的占位符。

Answer 1

首先，从两个规则中删除直接左递归。让我们考虑规则 a:

a
    : (b q | c) p+
    | b q
    | c
    ;

简化：

a
    : (b q | c) p*
    ;

对规则做类似的转换b:

b
    : (a s | d) r*
    ;

现在可以将规则 a 中的 b 标识符替换为规则主体 b:

a
    : (c | (a s | d) r* q) p*
    ;

或者将规则 b 中的 a 标识符替换为规则主体 a:

b
    : ((b q | c) p* s | d) r*
    ;

如果需要，也可以摆脱直接左递归。