When/Why Antlr 中有互左递归吗？

Question

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

以下几组规则相互左递归[表达式,数学]

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 可以处理直接左递归，但不能处理间接左递归，其中左递归规则定义为 "either directly or indirectly invokes itself on the left edge of an alternative"（TDAR；第 71 页）。

当在第一个示例中，#mathExpression 替代方案从 expression 规则中分离出来并进入单独的 math 规则时，左直接递归变为间接，即，规则为'mutually left-recursive'.

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

When/Why Antlr 中有互左递归吗？

When/Why Does Mutual Left Recursion Happen in Antlr?

recursion

antlr

antlr4