Yacc : Boolean and Arithmetic expression grammars conflict

Question

I'm implementing a compiler as part of a class, for a language which is supposed to support both arithmetic and boolean expression. Unfortunately, I'm having some trouble implementing rules for both that do not conflict.

Specifically, both types of expression are supposed to be able to reduce to accessing a variable. But that leads to conflicts, which I don't know how to solve.

Here is a minimal working example, which shows the issue :

(compile with yacc -v -d -Wcounterexamples y.tab.y and lex -o lex.yy.c lex.yy.l, although the lex file is not necessary to see the problem. Also I think -Wcounterexamples is specific to the latest version of GNU Bison, which I highly recommend over POSIX Yacc just for this.)

y.tab.y

%{
    extern int yylex(void);
    extern int yyerror(char *msg);
%}
%token MINUS PLUS DIVIDED_BY TIMES OPEN_PARENTHESIS CLOSED_PARENTHESIS INTEGER_CONSTANT
%token OR AND FALSE TRUE NOT DIFFERENT EQUAL INFERIOR STRICT_INFERIOR SUPERIOR STRICT_SUPERIOR
%token IDENTIFIER
%%
expression:
    arithmetic_expression
    | boolean_expression
    ;
arithmetic_expression:
    arithmetic_term 
    | arithmetic_expression MINUS arithmetic_term
    | arithmetic_expression PLUS arithmetic_term 
    ;
arithmetic_term:
    arithmetic_factor 
    | arithmetic_term DIVIDED_BY arithmetic_factor 
    | arithmetic_term TIMES arithmetic_factor
    ;
arithmetic_factor:
    OPEN_PARENTHESIS arithmetic_expression CLOSED_PARENTHESIS
    | INTEGER_CONSTANT
    | variable 
    ;
boolean_expression:
    boolean_term
    | boolean_expression OR boolean_term
    ;
boolean_term:
    boolean_factor
    | boolean_term AND boolean_factor
    ;
boolean_factor:
    FALSE
    | TRUE
    | NOT boolean_factor
    | arithmetic_expression comparison arithmetic_expression
    | OPEN_PARENTHESIS boolean_expression CLOSED_PARENTHESIS 
    | variable
    ;
comparison:
    DIFFERENT
    | EQUAL
    | INFERIOR 
    | STRICT_INFERIOR
    | SUPERIOR
    | STRICT_SUPERIOR
    ;
variable:
    IDENTIFIER
    ;

lex.yy.l

%{
    #include "y.tab.h"
%}
%%
- {return MINUS;}
\+ {return PLUS;}
\* {return TIMES;}
\( {return OPEN_PARENTHESIS;}
\) {return CLOSED_PARENTHESIS;}
\|\| {return OR;}
&& {return AND;}
false {return FALSE;}
true {return TRUE;}
! {return NOT;}
!= {return DIFFERENT;}
== {return EQUAL;}
\<= {return INFERIOR;}
\< {return STRICT_INFERIOR;}
\>= {return SUPERIOR;}
\> {return STRICT_SUPERIOR;}
[a-z][a-zA-Z0-9_]* {return IDENTIFIER;}
%%

Answer 1

With a recently updated Windows WSL, I am getting:

y.tab.y: warning: 2 reduce/reduce conflicts [-Wconflicts-rr]
y.tab.y: warning: reduce/reduce conflict on tokens $end, CLOSED_PARENTHESIS [-Wcounterexamples]
  Example: variable •
  First reduce derivation
    expression
    ↳ 1: arithmetic_expression
         ↳ 3: arithmetic_term
              ↳ 6: arithmetic_factor
                   ↳ 11: variable •
  Second reduce derivation
    expression
    ↳ 2: boolean_expression
         ↳ 12: boolean_term
               ↳ 14: boolean_factor
                     ↳ 21: variable •

In your grammar, variables can be an arithmetic_expression as well as a boolean_expression.

You can probably ignore this error, but the implementation of arithmetic operations has to deal with potential boolean operands. Typically, false is treated as 0 and true is treated as 1. The other way round: For boolean operations, arithmetic operands have to be coerced to true or false.

As commented by @user207421, you could get rid of the warning by treating everything as expression. Remove the boolean parts and take care for the type conversion in the implementation of the operations.