Когда/Почему в 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 может обрабатывать прямую левую рекурсию, но не косвенную левую рекурсию, где левое рекурсивное правило определяется как правило, которое «прямо или косвенно вызывает себя на левом краю альтернативы» (TDAR; pg 71).

Когда, как и в первом примере, #mathExpression альтернативы вынесена из expression правил, и в отдельную math правило, левая прямая рекурсия становится косвенной, т.е., правила «взаимно левыми-рекурсивные».

Как показано на втором и третьем примерах, типичным решением является простое объединение непрямых леворекурсивных правил в одном правиле.