"The following sets of rules are mutually left-recursive"

Question

我尝试编写一个语法来识别像这样的表达式：

(A + MAX(B) ) / ( C - AVERAGE(A) )
IF( A > AVERAGE(A), 0, 1 ) 
X / (MAX(X)

不幸的是，antlr3 因这些错误而失败：

error(210): The following sets of rules are mutually left-recursive [unaryExpression, additiveExpression, primaryExpression, formula, multiplicativeExpression]

error(211): DerivedKeywords.g:110:13: [fatal] rule booleanTerm has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2. Resolve by left-factoring or using syntactic predicates or using backtrack=true option.

error(206): DerivedKeywords.g:110:13: Alternative 1: after matching input such as decision cannot predict what comes next due to recursion overflow to additiveExpression from formula

我花了几个小时试图解决这些问题，如果有人至少可以帮助我解决第一个问题，那就太好了。谢谢

代码：

    grammar DerivedKeywords;
options {
output=AST;
//backtrack=true;
}
WS    : (    ' ' | '\t' | '\n' | '\r' )
            { skip(); }
      ;

//for numbers
DIGIT
      :     '0'..'9'
      ;
//for both integer and real number
NUMBER
      :     (DIGIT)+ ( '.' (DIGIT)+ )?( ('E'|'e')('+'|'-')?(DIGIT)+ )?
      ;

// Boolean operatos
AND : 'AND';
OR : 'OR';
NOT : 'NOT';
EQ : '=';
NEQ : '!=';
GT : '>';
LT : '<';
GTE : '>=';
LTE : '<=';
COMMA : ',';

// Token for Functions
IF : 'IF';
MAX : 'MAX';
MIN : 'MIN';
AVERAGE : 'AVERAGE';


VARIABLE :   'A'..'Z' ('A'..'Z' | '0'..'9')*
         ;
// OPERATORS

LPAREN      :     '('   ;     
RPAREN            :     ')'   ;

DIV         :     '/'   ;     
PLUS              :     '+'         ;
MINUS       :     '-'   ;     
STAR              :     '*'         ;


expression : formula;

formula 
        :   functionExpression
        |   additiveExpression 
        |   LPAREN! a=formula RPAREN! // First Problem
        ;

additiveExpression 
      : a=multiplicativeExpression ( (MINUS^ | PLUS^ )   b=multiplicativeExpression )* 
      ;


multiplicativeExpression
      : a=unaryExpression ( (STAR^ | DIV^ ) b=unaryExpression )* 
        
      ;

unaryExpression
      :     MINUS^ u=unaryExpression 
      |     primaryExpression 
      ;

functionExpression 
        : f=functionOperator LPAREN e=formula RPAREN 
        |  IF LPAREN b=booleanExpression COMMA p=formula COMMA s=formula RPAREN
        ; 


functionOperator : 
    MAX | MIN | AVERAGE;


primaryExpression
      :     NUMBER 
      // Used for scientific numbers
      |     DIGIT 
      |     VARIABLE 
      |     formula
    ;

// Boolean stuff
booleanExpression 
            : orExpression;

orExpression :  a=andExpression (OR^ b=andExpression )*
                ;
andExpression 
            :   a=notExpression (AND^ b=notExpression )*
                ;

notExpression
            : NOT^ t=booleanTerm 
            | booleanTerm
            ;

booleanOperator :
    GT | LT | EQ | GTE | LTE | NEQ; 

booleanTerm : a=formula op=booleanOperator b=formula                 
            | LPAREN! booleanTerm RPAREN! // Second problem
;

Answer 1

error(210): The following sets of rules are mutually left-recursive [unaryExpression, additiveExpression, primaryExpression, formula, multiplicativeExpression]

-这意味着如果解析器输入unaryExpression规则，它有可能匹配additiveExpression、primaryExpression、formula、multiplicativeExpression和unaryExpression 再次从输入中消耗单个标记 - 所以它无法决定是否使用这些规则，因为即使它使用规则，输入也将是相同的。

您可能试图通过此规则序列允许表达式中的子表达式 - 您需要确保该路径将占用子表达式的左括号。可能 primaryExpression 中的 formula 选项应该更改为 LPAREN formula RPAREN，其余语法也相应调整。