antlr4 - 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*
    ;

现在可以将rule 中的bidentifier 替换为 rulea的主体b：

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

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

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

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