Warning: "rule useless in parser due to conflicts" in Bison

Question

I am trying to make a C lexical analyzer and I have some warnings:

rule useless in parser due to conflicts: sentenceList: sentenceList sentence
rule useless in parser due to conflicts: sentSelection: IF '(' expression ')' sentence
rule useless in parser due to conflicts: sentSelection: IF '(' expression ')' sentence ELSE sentence
rule useless in parser due to conflicts: sentSelection: SWITCH '(' expression ')' sentence
rule useless in parser due to conflicts: sentIteration: WHILE '(' expression ')' sentence
rule useless in parser due to conflicts: sentIteration: FOR '(' expression ';' expression ';' expression ')' sentence

This is the part of the code where the warnings come from:

input:    /* nothing */
        | input line
;

line:     '\n'
        | sentence '\n' 
;
sentence :       sentComposed
                |sentSelection
                |sentExpression
                |sentIteration
;

sentComposed:     statementsList
                 |sentenceList
;

statementsList:      statement
                   | statementsList statement
;

sentenceList:    sentence
                |sentenceList sentence
;

sentExpression: expression ';'
              |';'
;

sentSelection: IF '(' expression ')' sentence
              |IF '(' expression ')' sentence ELSE sentence
              |SWITCH '(' expression ')' sentence
;

sentIteration: WHILE '(' expression ')' sentence
              |DO sentence WHILE '(' expression ')' ';' 
              |FOR '(' expression ';' expression ';' expression ')' sentence
;

statement: DATATYPE varList                
;

varList:     aVar
            |varList ',' aVar
;

aVar:     variable inicial                           
;

variable: IDENTIFIER                                 
;

initial: '=' NUM                                         
;

I have just added some more information Every word in uppercase letters are tokens. If you need any aditional information please tell me

Answer 1

Here's a considerably simplified (but complete) excerpt of your grammar. I've declared expression to be a terminal so as to avoid having to define it:

%token expression IF
%%
sentence :       sentComposed
                |sentSelection
                |sentExpression
sentComposed:    sentenceList
sentenceList:    sentence
                |sentenceList sentence
sentExpression:  expression ';'
                |';'
sentSelection:   IF '(' expression ')' sentence

When I run that through bison, it reports:

ez.y: warning: 4 shift/reduce conflicts [-Wconflicts-sr]
ez.y: warning: 8 reduce/reduce conflicts [-Wconflicts-rr]

Those conflicts are the actual problem, as indicated by the following warnings ("due to conflicts"):

ez.y:8.18-38: warning: rule useless in parser due to conflicts [-Wother]
                 |sentenceList sentence
                  ^^^^^^^^^^^^^^^^^^^^^
ez.y:11.18-47: warning: rule useless in parser due to conflicts [-Wother]
 sentSelection:   IF '(' expression ')' sentence
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

When bison finds a conflict in a grammar, it resolves it according to a simple procedure:

• shift-reduce conflicts are resolved in favour of the shift
• reduce-reduce conflicts are resolved in favour of the production which occurs earlier in the grammar.

Once it does that, it might turn out that some production can no longer ever be used, because it was eliminated from every context in which it might have been reduced. That's a clear sign that the grammar is problematic. [Note 1]

The basic problem here is that sentComposed means that statements can just be strung together to make a longer statement. So what happens if you write:

IF (e) statement1 statement2

It could be that statement1 statement2 is intended to be reduced into a single sentComposed which is the target of the IF, so the two statements execute only if e is true. Or it could be that the sentComposed consists of the IF statement with target statement1, followed by statement2. In C terms, the difference is between:

if (e) { statement1; statement2; }

and

{ if (e) { statement1; } statement2; }

So that's a real ambiguity, and you probably need to rethink the absence of braces in order to fix it.

But that's not the only problem; you also have a bunch of reduce-reduce conflicts. Those come about in a much simpler way, because part of the above grammar is the following loop:

sentence:     sentComposed
sentComposed: sentenceList
sentenceList: sentence

That loop means that your grammar allows a single sentence to be wrapped in an arbitrary number of unit reductions. You certainly did not intend that; I'm certain that your intent was that sentComposed only be used if actually necessary. But bison doesn't know your intent; it only knows what you say.

Again, you will probably solve this problem when you figure out how you actually want to identify the boundaries of a sentComposed.

Notes:

1. In some cases, conflicts are not actually a problem. For example, there is a shift-reduce conflict between these two productions; the so-called "dangling-else" ambiguity:

   sentSelection: IF '(' expression ')' sentence
                 |IF '(' expression ')' sentence ELSE sentence
   

   In a nested IF statement:

   IF (e) IF (f) s1 ELSE s2
   

   it's not clear whether the ELSE should apply to the inner or outer IF. If it applies to the inner IF, it must be shifted to allow the second production for sentSelection. If it applies to the outer IF, a reduction must first be performed to complete the inner (else-less) IF before shifting ELSE into the outer IF. Bison's default action ("prefer shift") does exactly the right thing in this case, which is to shift the ELSE immediately. (Indeed, that's why the default was chosen to be "prefer shift").