CODEWITHSUNDEEP
recursionantlrantlr4
duc947
duc947

Reputation: 3

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

//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.

Upvotes: 0

Views: 396

Answers (1)

TomServo
TomServo

Reputation: 7409

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.

Upvotes: 1

Related Questions