How to solve “The following sets of rules are mutually left-recursive” ANTLR error

Question

The following sets of rules are mutually left-recursive [valeurBooleene, valeur]

I know that ANTLR handle well left-recursive rules but only in one rule, not between rules.

I have to rewrite my rules to solve the mutually left-recursive problem but I don't see how...

grammar minimal;

constante:
   bool  = BOOLEAN
 | intgr = INTEGER
;
valeurBooleene:
   '(' val = valeurBooleene ')'
 | bool       = BOOLEAN
 | 'non'  not = valeur
 | leftValue = valeur '=' rightValue = valeur
;
valeur:
   '(' val = valeur ')'
 | cst          = constante
 | booleanValue = valeurBooleene
 | '|' absolute = valeur '|'
 | '-' opposite = valeur
;
condition:
   '(' cond = condition ')'
 | bool = valeurBooleene
;
si:
   'Si' cond = condition 'alors' ( thenActions += action )+
      ( 'sinon' ( elseActions += action )+ )?
;
system:
   ( actions += action )+
   EOF
;
action:
   ifClause = si
;
BOOLEAN:
   'false'
 | 'true'
 | 'faux'
 | 'vrai'
;
INTEGER:
   [0-9]+
;
WS:
   [ \n\t\r]+ -> skip
;

I would merge valeurBooleene and valeur into one rule and leave the type checking to the type checker (or the interpreter or runtime system if your language is dynamically typed). — sepp2k
What I'm suggesting is to make condition use valeur instead and leave it to the type checker to make sure that only Boolean expressions are used as conditions. — sepp2k
Writing the grammar in such a way that ill-typed expressions don't parse is often not a solvable problem (just think about what happens if you add variables and/or function calls for example). You might be able to do it in some cases, but it's usually brittle (meaning future additions to your language can make everything break down), almost always painful and rarely, if ever, the right approach. If you look at the grammars of any existing programming languages, you'll note that none of them define separate expression rules for each type. — sepp2k

Aubin Aubin · Accepted Answer · 2020-06-23T20:09:41

Finally, I follow the advices provided by sepp2k like this:

grammar minimal;

value:
   '(' val = value ')'     # Parenthesis
   
 | b = BOOLEAN             # Boolean
 | 'non' not = value       # Boolean
 | l = value '=' r = value # Boolean
 
 | i = INTEGER             # Numeric
 | '|' abs = value '|'     # Numeric
 | '-' opposite = value    # Numeric
;
condition:
   '(' condition ')'
 | cond = value
;
ifStmnt:
   'IF' condition 'THEN' ( actionsThen += action )+
      ( 'ELSE' ( actionsElse += action )+ )?
;
system:
   ( actions += action )+
   EOF
;
print:
   'print' val = value 
;
action:
   ifs = ifStmnt
 | pr  = print
;
BOOLEAN:
   'false'
 | 'true'
;
INTEGER:
   [0-9]+
;
WS:
   [ \n\t\r]+ -> skip
;

The labels create classes which extends ValueContext, I use them like this:

package com.thalesgroup.dms.stimulus.factories;

import minimal.minimalParser.BooleanContext;
import minimal.minimalParser.ConditionContext;
import minimal.minimalParser.NumericContext;
import minimal.minimalParser.ParenthesisContext;
import minimal.minimalParser.ValueContext;

public class Sample {

   void analyze( ValueContext ctxt ) {
      if( ctxt instanceof ParenthesisContext ) {
         analyze(((ParenthesisContext)ctxt).val );
      }
      else if( ctxt instanceof BooleanContext ) {
         final BooleanContext bc = (BooleanContext)ctxt;
         analyze( bc );
      }
      else if( ctxt instanceof NumericContext ) {
         final NumericContext nc = (NumericContext)ctxt;
         analyze( nc );
      }
   }

   void analyze( ConditionContext ctxt ) {
      if( ctxt.cond instanceof BooleanContext ) {
         final BooleanContext boolCtxt = (BooleanContext)ctxt.cond;
         // build a condition from a BooleanContext
         analyze( boolCtxt );
      }
      else {
         throw new IllegalStateException();
      }
   }

   void analyze( BooleanContext ctxt ) {
      if( ctxt.b != null ) {
         final String literal = ctxt.b.getText();
         if( literal.equals( "true" )) {
            // deal with a boolean literal 'true'
         }
         else if( literal.equals( "false" )) {
            // deal with a boolean literal 'false'
         }
      }
      else if( ctxt.not != null ) {
         final BooleanContext bCtxt = (BooleanContext)ctxt.not;
         // deal with a 'not' operation
      }
      else if( ctxt.l != null ) {
         final ValueContext left  = ctxt.l;
         final ValueContext right = ctxt.r;
         // deal with 'equals'
      }
      else {
         // ???
      }
   }

   void analyze( NumericContext ctxt ) {
      if( ctxt.abs != null ) {
         // deal with abs( x )
      }
      else if( ctxt.opposite != null ) {
         // deal with - x
      }
      else if( ctxt.i != null ) {
         // deal with literal integer
      }
   }
}

How to solve “The following sets of rules are mutually left-recursive” ANTLR error

1 Answers