Why am I getting conflicts: 1 shift/reduce

Question

I'm new to bison and I'm getting a "conflicts: 1 shift/reduce" error. Can anyone shed some light on this?

Here's the y file.

test.y:

%{
#include <stdio.h>
#include <string.h>

#define YYERROR_VERBOSE
#define YYDEBUG 1
void yyerror(const char *str);
int yywrap();
%}

%union
{
    int integer;
    char *string;
}

%token <string>     VAR_LOCAL
%token <integer>    LIT_NUMBER
%token <string>     LIT_STRING
%token WS_LINEBRK

//%token SYMB_EQL
%token SYMB_PLUS
%token SYMB_MINUS
%token SYMB_MUL
%token SYMB_DIV

%%

/*
    // Sample input
    num = 10
    str = "this is a string"
*/

inputs: /* empty token */
        | literal
        | variable
        | inputs stmt WS_LINEBRK
        ;

stmt:   variable "=" exps  
        ;

exps:   variable op literal
        | variable op variable
        | literal op literal
        | literal op variable
        ;


op:     SYMB_PLUS | SYMB_MINUS | SYMB_MUL | SYMB_DIV ;


variable: VAR_LOCAL
        {
            printf("variable: %s\n", $1);
        }
        ;

literal:
        number | string
        ;

string: LIT_STRING
        {
            printf("word: %s\n", $1);
        }
        ;

number: LIT_NUMBER
        {
        printf("number: %d\n", $1);
        }
        ;

%%

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

int yywrap()
{
        return 1;
} 

main()
{
    yyparse();
}

Here's the lex file test.l:

%{
#include <stdio.h>
#include <stdlib.h>


#include "y.tab.h"
int line_no = 0;

%}

%%
[a-z][a-zA-Z0-9]*       {
                            // local variable
                            yylval.string=strdup(yytext);
                            return VAR_LOCAL;
                        }

[0-9]+                  {
                            //number literal
                            yylval.integer=atoi(yytext);
                            return LIT_NUMBER;
                        }

=                       return SYMB_EQL;
\+                      return SYMB_PLUS;
\-                      return SYMB_MINUS;
\*                      return SYMB_MUL;
\/                      return SYMB_DIV;


\"[-+\!\.a-zA-Z0-9' ]+\"    {
                            // word literal
                            yylval.string=strdup(yytext);
                            return LIT_STRING;
                        }

\n                      {
                            // line break
                            printf("\n");
                            return WS_LINEBRK;
                        }

[ \t]+                  /* ignore whitespace */;

%%

Answer 1

bison -r test.y will write a file test.output with a detailed description of the generated state machine that allows you to see what's going on - such as the state where the shift/reduce conflict occurs.

In your case, the problem is in the start state (corresponding to your start nonterminal, inputs). Say the first token is VAR_LOCAL. There's two things your parser could do:

• It could match the variable case.
• It could also match the inputs stmt WS_LINEBRK case: inputs matches the empty string (first line), and stmt matches variable "=" exps.

With the one token of lookahead that bison parsers use, there's no way to tell. You need to change your grammar to get rid of this case.