ANTLR4 doesn't manage with left recursion properly

Question

I'm trying to describe the grammar for logical expressions using ANTLR4. Surely, this grammar has direct left recursion, and as I've read ANTLR4 supports it.

grammar Logic;
@header {
package parser;
import expression.*;
}

expression returns [Expression value] : disjunction {$value = $disjunction.value;}
                                      | disjunction IMPLIES expression {$value = new Implication($disjunction.value, $expression.value);};

disjunction returns [Expression value] : conjunction {$value = $conjunction.value;}
                                       | disjunction OR conjunction {$value = new Disjunction($disjunction.value, $conjunction.value);};

conjunction returns [Expression value] : negation {$value = $negation.value;}
                                       | conjunction AND negation {$value = new Conjunction($conjunction.value, $negation.value);};

negation returns [Expression value] : variable {$value = $variable.value;}
                                    | NOT negation {$value = new Negation($negation.value);}
                                    | OB expression CB {$value = $expression.value;};

variable returns [Expression value] : VAR {$value = new Variable($VAR.text);};

IMPLIES : '->';
OR : '|';
AND : '&';
NOT : '!';
OB : '(';
CB : ')';
VAR : [A-Z]([0-9])*;

But when I'm running antlr to generate parser for my grammar, it gives some strange errors:

error(65): Logic.g4:5:125: unknown attribute value for rule disjunction in $disjunction.value
error(65): Logic.g4:5:125: unknown attribute value for rule conjunction in $conjunction.value

When I swap disjunction and conjunction in disjunction rule, making disjunction right-associative, it works, but this can cause some mistakes in my work.

As it might be important, I generate parsers using ANTLR4-plugin for Intellij Idea.

What am I doing wrong? Thank you in advance.

Bart Kiers Bart Kiers · Accepted Answer · 2016-08-23T14:15:19

When referring to a disjunction in your code:

disjunction returns [Expression value]
 : conjunction {$value = $conjunction.value;}
 | disjunction OR conjunction {$value = new Disjunction($disjunction.value, $conjunction.value);}
 ;

ANTLR tries to get the value of the entire enclosing rule if you do $disjunction instead of the disjunction in disjunction OR ....

If you want to refer to disjunction in disjunction OR ..., you need to label it before referencing it:

disjunction returns [Expression value]
 : c1=conjunction                  {$value = $c1.value;}
 | d=disjunction OR c2=conjunction {$value = new Disjunction($d.value, $c2.value);}
 ;

Here's a full working (tested) example:

grammar Logic;

@header {
  import expression.*;
}

expression returns [Expression value]
 : d1=disjunction                      {$value = $d1.value;}
 | d2=disjunction IMPLIES e=expression {$value = new Implication($d2.value, $e.value);}
 ;

disjunction returns [Expression value]
 : c1=conjunction                  {$value = $c1.value;}
 | d=disjunction OR c2=conjunction {$value = new Disjunction($d.value, $c2.value);}
 ;

conjunction returns [Expression value]
 : n1=negation                   {$value = $n1.value;}
 | c=conjunction AND n2=negation {$value = new Conjunction($c.value, $n2.value);}
 ;

negation returns [Expression value]
 : variable         {$value = $variable.value;}
 | NOT n=negation   {$value = new Negation($n.value);}
 | OB expression CB {$value = $expression.value;}
 ;

variable returns [Expression value]
 : VAR {$value = new Variable($VAR.text);}
 ;

IMPLIES : '->';
OR      : '|';
AND     : '&';
NOT     : '!';
OB      : '(';
CB      : ')';
VAR     : [A-Z]([0-9])*;
SPACE   : [ \t\r\n] -> skip;

ANTLR4 doesn't manage with left recursion properly

1 Answers