Shift Reduce Conflict in Bison Grammar?

Question

I have the following Bison Grammar File, when I do "bison -d filename.y" I get a message

conflicts: 5 Shift/Reduce.

Actually they were 8, I managed to get rid of 3 but no idea where the rest is, I am guessing it is something that has to do with COMMA, but hmm.. anyidea whats wrong in my grammar definition. The parser is to supposed to parse part of the Prolog Syntax

%{#include <math.h>
#include <stdio.h>
void yyerror(char *message);
%}
%start program
%token ATOM VAR NUM

%token DOT COMMA
%token PARENTLEFT PARENTRIGHT RSQRBRACKETS LSQRBRACKETS
%token IF CUT IS PIPE
%token SMALLEREQ GREQ SMALLER GREATER EQ
%token PLUS MULTIP DIVIDE MINUS MOD
%token Aus

%left PLUS MINUS
%left DIVIDE MULTIP
%left COMMA

%%
program :           program rule                { printf("programm fertig gelesen \n");} 
        |       program fact                { printf("programm fertig gelesen \n");} 
        |       rule                        { printf("programm fertig gelesen \n");} 
        |       fact                        { printf("programm fertig gelesen \n");}
;

fact :              struct DOT                  { printf("Fakt gelesen\n\n\n"); }
;

rule :              struct IF subProbList DOT   { printf("Regel mit %d Teilprobleme    gelesen\n\n\n", $3); }
;

struct :            ATOM PARENTLEFT parameterList PARENTRIGHT  {printf("%s mit %d    Variablen\n",$1,$3); $$=$3;}
;

subProbList :       subProb                     {$$ = 1; }
        |       subProbList COMMA subProb   {$$ = $1 + 1;}
;

subProb :           struct | assignmentTerm | comparison | CUT { printf("CUT Op\n"); }
;

assignmentTerm :    exp IS exp                  { printf("is mit %d Variabeln\n", ($1 + $3)); $$ = $1 + $3; }
;

exp :               num                         { $$ = 0; }
    |           var                         { printf("Variable %s \n", $1); $$ = 1; } 
    |           exp operation exp           { printf("left exp is %d right exp is %d\n",$1,$3); $$ = $1 + $3;} 
    |           PARENTLEFT exp PARENTRIGHT         { $$ = $2;}
;

parameter :         var                         { printf("Variable %s\n",$1 ); $$ = 1; }
        |       struct                      { $$ = $1; }
        |       list                        { $$ = $1; }
;

parameterList :     parameter                   { $$ = $1;}
            |   parameterList COMMA parameter {$$= $1 + $3;}
;

operation :         PLUS | MINUS | MULTIP | DIVIDE | MOD
;

comparison :        var comparisonOp num        { printf("Variable %s \n", $1);

                                                printf("Vergleich mit 1 Vars\n" );
                                                $$=1;   
                                            }
        |       num comparisonOp var        {  
                                                printf("Variable %s \n", $3);
                                                printf("Vergleich mit 1 Vars\n" );
                                                $$=1;   
                                            }

        |       var comparisonOp var        {   printf("Variable %s \n", $1);
                                                printf("Variable %s \n", $3);
                                                printf("Vergleich mit 2 Vars\n" );
                                                $$=2;   
                                            }
        |       num comparisonOp num        {  
                                                $$=0; 
                                                printf("Vergleich mit 0 Variablen \n");

                                            }
;

comparisonOp :      EQ | GREATER | SMALLER | GREQ | SMALLEREQ
;

list :              LSQRBRACKETS varList RSQRBRACKETS       {$$ = $2;}
    |           LSQRBRACKETS elementList RSQRBRACKETS   {$$ = $2;}
    |           LSQRBRACKETS RSQRBRACKETS               {$$ = 0;}
;
varList :           var PIPE var                {   printf("Variable %s \n", $1);
                                                printf("Variable %s \n", $3);
                                                $$ = 2;
                                            }
;
elementList :       ATOM                        { $$ = 0;}
            |   var                         { printf("Variable %s \n", $1); $$ = 1; } 
            |   elementList COMMA var       { $$ = $1 + 1; } 
            |   elementList COMMA ATOM      { $$ = $1; }
;

num : NUM | MINUS NUM
;
var : VAR | MINUS VAR
;
%%

int main(int argc, char **argv){
    yyparse();
    return 0;
}

void yyerror(char *message) {
    printf("How about no?Well,no,that word doesnt belong to this classy language! \n");
}

btw, the parser parses the file I give it as input flawlessly, so it works as I want it to, but would be great if the conflicts can be removed. — StaticBug

Bryan Olivier Bryan Olivier · Accepted Answer · 2013-04-13T18:34:43

If you change the definition of exp to

exp :           num    
    |           var
    |           exp PLUS exp
    |           exp MINUS exp
    |           exp MULTIP exp
    |           exp DIVIDE exp
    |           exp MOD exp
    |           PARENTLEFT exp PARENTRIGHT
;

that is expand operation (and remove it) inside exp and add

%left MOD

amongst the other operators, that is define its precedence in relation to the other operators, then you should be fine.

Shift Reduce Conflict in Bison Grammar?

1 Answers