Home > Blockchain >  Antlr4 saying my rule is mutually left recursive with itself
Antlr4 saying my rule is mutually left recursive with itself

Time:03-18

I'm working on an assignment where we make a compiler for a simple language and we are using ANTLR4 for Java. After finally getting my grammar working i had to add some Java code to the language parser to build an AST. Here's where i get confused. Antlr is supposed to throw an error if rules are mutually left recursive and as i understand it it happens when one rule references another rule and the second rule reference the first rule. What i don't understand is why antlr is telling me that my rule is mutually left recursive with itself? Here is the error message i keep getting: error(119): PrevParser.g4::: The following sets of rules are mutually left-recursive [expr]. I looked around and noone seems to be having this issue. I did find someone saying that mutually left recursive rules have in common that their first token is another rule so i tried putting a regular . token right before the rule token and now it magically compiles. Why does it do that when the rule is only referencing itself? Heres the bit of code thats causing the issue:

expr returns [AstExpr ast] 
     : (VOID_CONST {$ast = new AstAtomExpr(loc($VOID_CONST), AstAtomExpr.Type.VOID, $VOID_CONST.text);}) 
     | (INT_CONST {$ast = new AstAtomExpr(loc($INT_CONST), AstAtomExpr.Type.INT, $INT_CONST.text);}) 
     | (CHAR_CONST {$ast = new AstAtomExpr(loc($CHAR_CONST), AstAtomExpr.Type.CHAR, $CHAR_CONST.text);}) 
     | (POINT_CONST {$ast = new AstAtomExpr(loc($POINT_CONST), AstAtomExpr.Type.POINTER, $POINT_CONST.text);}) 
     | (STRING_CONST {$ast = new AstAtomExpr(loc($STRING_CONST), AstAtomExpr.Type.STRING, $STRING_CONST.text);}) 
     | (BOOL_CONST {$ast = new AstAtomExpr(loc($BOOL_CONST), AstAtomExpr.Type.BOOL, $BOOL_CONST.text);}) 
     | (IDENTIFIER {$ast = new AstNameExpr(loc($IDENTIFIER), $IDENTIFIER.text);}) 
     | ( e1=expr O_OKLEPAJ e2=expr O_ZAKLEPAJ {$ast = new AstArrExpr(loc($e1.ast, $O_ZAKLEPAJ), $e1.ast, $e2.ast);} ) 
;

The error appears in the last line where the rule expr references itself as e1=expr. If i change the rule to look like this: ( DOT e1=expr O_OKLEPAJ e2=expr O_ZAKLEPAJ {$ast = new AstArrExpr(loc($e1.ast, $O_ZAKLEPAJ), $e1.ast, $e2.ast);} ) the whole thing compiles normally. Does anyone know how i can resolve this issue? Any help is aprecciated.

CodePudding user response:

I've seems this on stackoverflow before (but can't find it anymore). This seems to be a bug that is caused by the parenthesis before the left-recursive expr. Just remove the parenthesis (which are redundant anyway).

So not:

expr returns [AstExpr ast] 
 : ...
 | ( e1=expr O_OKLEPAJ e2=expr O_ZAKLEPAJ {$ast = new AstArrExpr(loc($e1.ast, $O_ZAKLEPAJ), $e1.ast, $e2.ast);} )
 ;

but this instead:

expr returns [AstExpr ast] 
 : ...
 | e1=expr O_OKLEPAJ e2=expr O_ZAKLEPAJ {$ast = new AstArrExpr(loc($e1.ast, $O_ZAKLEPAJ), $e1.ast, $e2.ast);}
 ;
  • Related