在Antlr中什么时候/为什么会发生相互左递归

Question

我有一个expression，它是我的其他顶级事物的集合。在expression中，有math，也就是expression (op) expression。我得到

下列规则集是相互左递归的[expression, math]

compileUnit : expression EOF;
expression
    : parens                                                            
    | operation                                                         
    | math  
    | variable                                                          
    | number                                                            
    | comparisonGroup                                                   
    ;
math : expression op=( ADD | SUBSTRACT | MULTIPLY | DIVIDE ) expression     #mathExpression;

然而

!

这不是问题-

expression
    : parens                                                            
    | operation                                                         
    | expression op=( ADD | SUBSTRACT | MULTIPLY | DIVIDE ) expression  
    | variable                                                          
    | number                                                            
    | comparisonGroup                                                   
    ;

这也不是!-

math : op=( ADD | SUBSTRACT | MULTIPLY | DIVIDE ) expression expression     #mathExpression;

那么为什么我的第一个代码块的行为与其他两个例子不同呢?

Answer 1

Antlr4可以处理直接左递归，但不能处理间接左递归，其中左递归规则定义为"直接或间接在替代的左边缘调用自身"的规则(TDAR;pg 71)。

与第一个示例中一样，当#mathExpression选项从expression规则中分离出来并进入单独的math规则时，左直接递归变为间接递归，即。，规则是'相互左递归'。

正如在第二个和第三个示例中实现的那样，典型的解决方案是简单地将间接左递归规则组合到单个规则中。