1

I am getting the error: The following sets of rules are mutually left-recursive [symbolExpression]. In my grammar, symbolExpression is directly left-recursive so shouldn't ANTLR4 be handling this?

Here are the relevant parts of my parser:

operation: 
       OPERATOR '(' (operation | values | value | symbolExpression) ')'                       #OperatorExpression
     | bracketedSymbolExpression                                                              #BracketedOperatorExpression
     ;

symbolExpression:
     (operation | values | value | symbolExpression) SYMBOL (operation | values | value | symbolExpression);

bracketedSymbolExpression:
     '(' (operation | values | value | symbolExpression) SYMBOL (operation | values | value | symbolExpression) ')';

list: '[' (operation | value) (',' (operation | value))* ']';

values: (operation | value) (',' (operation | value))+;

value:
     NUMBER
   | IDENTIFIER
   | list
   | object;
Corey Wu
  • 1,209
  • 1
  • 22
  • 39

1 Answers1

0

The elements 'symbolExpression' and 'operation' in the rule 'symbolExpression' are interdependently left recursive.

Without knowing the language specification, it is impossible to say whether the language itself is irrecoverably ambiguous.

Nonetheless, one avenue to try is to refactor the grammar to move repeated clauses, like 

( operation | value )

and 

(operation | values | value | symbolExpression)

to their own rules with the goal of unifying the 'operation' and 'symbolExpression' (and perhaps 'bracketedSymbolExpression') rules into a single rule -- a rule that is at most self left-recursive. Something like

a : value
  | LPAREN a* RPAREN
  | LBRACK a* LBRACK
  | a SYMBOL a
  | a ( COMMA a )+
  ;
GRosenberg
  • 5,843
  • 2
  • 19
  • 23
  • Why are ```symbolExpression``` and ```operation``` interdependently left recursive? ```SymbolExpression``` expands into ```operation```, but ```operation```'s rules start with either ```OPERATOR``` or ```(```. – Corey Wu Jun 22 '15 at 14:26
  • Mutual left recursion is as Antlr defines it, which includes the indirect recursion of `symbolExpression` depending on `operation` and `operation` depending on `symbolExpression`. IIRC, the docs note that a left recursive rule cannot reference another rule that references the left recursive rule (though I cannot find it at the moment). See also this [answer](http://stackoverflow.com/questions/20791690/how-to-avoid-mutual-left-recursion-in-antlr-4). – GRosenberg Jun 22 '15 at 22:26
  • Yes, I believe that ANTLR can handle self left-recursion but not mutual left-recursion. However, I don't think this is a case of mutual left-recursion at all since ```operation``` does not expand into ```symbolExpression``` on its left. On its leftmost, it expands into ```(``` or ```OPERATOR``` which are both terminals. – Corey Wu Jun 22 '15 at 22:44
  • Your are defining 'mutual left recursion' as requiring involvement of two left recursive rules. Antlr evidently defines it differently, per my prior comment. Note also that the Antlr error message only identified the one rule `symbolExpression` as being mutually left recursive. You could raise a Issue at the Github repo regarding the clarity of the error message. – GRosenberg Jun 22 '15 at 22:54
  • Could you provide a link to support that ANTLR uses a different definition of mutual left-recursion? I can't find anything about it and it seems strange that that would be the case. – Corey Wu Jun 23 '15 at 15:56
  • Looking around a bit, I think the error is related to this: http://stackoverflow.com/questions/21870266/mutual-left-recursion-antlr-4 It appears that ANTLR can't handle direct left-recursion with parentheses. – Corey Wu Jun 23 '15 at 16:12