Error about left-recursive in ANTLR . Need to do what now?

Question

//Expression

exp: exp1 ASS_OP exp | exp1;

exp1: exp1 OR_OP exp2 | exp2;

exp2: exp2 AND_OP exp3 | exp3;

exp3: exp4 (EQUAL_OP | NOT_EQUAL_OP) exp4 | exp4;

exp4: exp5 (LESS_OP|GREATER_OP|LESS_EQUAL_OP|GREATER_EQUAL_OP) exp5 | exp5;

exp5: exp5 (ADD_OP | SUB_OP) exp6 | exp6;

exp6: exp6 (MUL_OP | DIV_OP | MOD_OP) exp7 | exp7;

exp7: (ADD_OP | SUB_OP | NOT_OP) exp7 | exp8;

exp8: LB exp RB | expl;

expl: invocation_exp | index_exp | ID | INTLIT |FLOATLIT | BOOLEANLIT | STRINGLIT;

index_exp: exp LSB exp RSB;

invocation_exp: ID LB (exp (COMMA exp)*)? RB;

[error] error(119): MC.g4::: The following sets of rules are mutually left-recursive [exp, index_exp, exp1, exp2, exp3, exp4, exp5, exp6, exp7, exp8, expl]

[trace] Stack trace suppressed: run last *:Antlr generates lexer and parser for the full output.

Hi, I'm new. I read some topics so that ANTLR4 supports only direct left-recursion. And authors seem don't want to change that. So anyone can help me fix my code? Thank for reading this.

Hi and welcome to Stack Overflow, please take a time to go through the welcome tour to know your way around here (and also to earn your first badge), read how to create a Minimal, Complete, and Verifiable example and also check How to Ask Good Questions so you increase your chances to get feedback and useful answers. — DarkCygnus
This could be rewritten to just: expr '*' expr | expr '+' expr | ...etc etc — john ktejik

TomServo TomServo · Accepted Answer · 2017-07-05T18:03:14

One of the great things about ANTLR4 as opposed to some of the older tools is that you don't often have to "chain" your operator precedence like this:

exp: exp1 ASS_OP exp | exp1;
exp1: exp1 OR_OP exp2 | exp2;
exp2: exp2 AND_OP exp3 | exp3;

I remember those days of chaining expression rules for strict BNF grammars. But in ANTLR4, we can do better and have a clearer grammar too. Since the rules are evaluated top to bottom, the highest-predecence rules are listed first like in this snippet:

expr
 : expr POW<assoc=right> expr           #powExpr
 | MINUS expr                           #unaryMinusExpr
 | NOT expr                             #notExpr
 | expr op=(MULT | DIV | MOD) expr      #multiplicationExpr
 | expr op=(PLUS | MINUS) expr          #additiveExpr
 | expr op=(LTEQ | GTEQ | LT | GT) expr #relationalExpr
 | expr op=(EQ | NEQ) expr              #equalityExpr
 | expr AND expr                        #andExpr
 | expr OR expr                         #orExpr
 | atom                                 #atomExpr

This might solve your operator precedence issues without wrangling with mutual left recursion. Highest precedence at top, with power (exponentiation) in this example (and by mathematical convention) having the highest binding in an expression.

Error about left-recursive in ANTLR . Need to do what now?

1 Answers