warning: 2 reduce/reduce conflicts [-Wconflicts-rr] in yacc grammar

Question

I have the following yacc grammar:

%{
#include  <stdio.h>
extern FILE* yyin;
extern char* yytext;

%}

%token VAR ID_NAME TYPE_STRING TYPE_BOOL TYPE_NUMBER
%token CONST VALUE_STRING VALUE_BOOL VALUE_NUMBER

%%

program
    : declarations
    ;

declarations
    : declaration
    | declarations declaration
    ;

declaration
    : var_declaration
    | const_declaration
    ;

value
    : VALUE_BOOL
    | VALUE_STRING
    | VALUE_NUMBER
    ;

assignment
    : ID_NAME '=' value
    ;

assignments
    : assignment
    | assignments ',' assignment
    ;

id_list
    : ID_NAME
    | id_list ',' ID_NAME
    ;

declaration_expression
    : assignments
    | id_list
    | assignments ',' declaration_expression
    | id_list ',' declaration_expression
    ;

var_declaration
    : VAR ':' type declaration_expression ';' { printf("%s var\n", $1);  } 
    ;

const_declaration: CONST ':' type assignments ';' {printf("const\n");}
    ;

type: TYPE_NUMBER 
    | TYPE_STRING
    | TYPE_BOOL
    ;

%%
void yyerror (char const *s) {
    fprintf (stderr, "%s\n", s);
}

int main(int argc, char** argv[])
{

    yyparse();
    return 0;
}

It should describe a little language that allows variables and constants declarations of the form: var:<type> <variables_names or variables_initializations> and const:<type> <constants_initialization>.

I want to add support for the following syntax:

var:<type> var1, var2=<value>, var3;

Something like this: var:<type> (<variables_names>|<variable_initializations>)+.

To accomplish that I've added the following modifications to my grammar:

assignments
    : assignment
    | assignments ',' assignment
    ;

id_list
    : ID_NAME
    | id_list ',' ID_NAME
    ;

declaration_expression
    : assignments
    | id_list
    | assignments ',' declaration_expression
    | id_list ',' declaration_expression
    ;

Which I thought will enable the (<variables_names>|<variable_initializations>)+ part. But I get a reduce/reduce conflict, due to these lines:

    | assignments ',' declaration_expression
    | id_list ',' declaration_expression

What am I doing wrong?

Answer 1

If I understand you correctly, you want to allow a mixture of bare variable names and variable initializations in a var declaration, and only initializations in a const declaration. That's quite straight-forward:

initialization : ID '=' value
init_list      : initialization | init_list ',' initialization
init_or_id     : initialization | ID
init_or_id_list: init_or_id
               | init_or_id_list ',' init_or_id

const_declaration: CONST ':' type init_list
var_declaration  : VAR   ':' type init_or_id_list

What you did wrong was to make a mixed list by extending a mixed list with lists, rather with items. That's ambiguous, so it results in a reduce/reduce conflict.

The above works (as did your original) because init_list and init_or_id_list can never appear (as non-terminals) at the same point in a derivation. One of them unambiguously follows the const keyword and the other unambiguously follows the var keyword. That's fortunate, because a list of pure assignments would satisfy both productions, which would create a reduce/reduce conflict if they shared a context. That problem is also solvable, and since it occasionally arises, I'll add the solution although I emphasize that it is not relevant to this particular question. (It might be relevant to some later reader with a similar issue, though.)

To make the two possible list syntaxes unambiguous, it is necessary to ensure that the potentially pure assignment list is always the derivation of a different production from the mixed list. So we could write:

init_list: initialization | init_list initialization
init_or_id_list: ID
               | init_list ',' ID
               | init_or_id_list ',' init_or_id

Now, an init_or_id_list necessarily contains at least one ID item, so it cannot be confused with init_list. But now we use the final result, we need to remember that a context which accepts a mixed list needs to allow both list possibilities:

pure_list: init_list
mixed_list: init_list | init_or_id_list