Shift/reduce conflicts in bison

Question

I'm new to Bison and I'm having trouble with shift/reduce conflicts... I'm trying to load from file to array data[]:

struct  _data
{
  char name[50]; 
  char surname[50]; 
  int year;
} data[1000];

Here is part of my bison code:

%token ID NUM NL EOF 

%%

File   : List EOF
       ;
List   : Record
       | List Record
       ;
Record : Name Surname Year NL  { count++; }
       | NL                    { count++; }
       | /*empty*/
       ;
Name   : ID                    { strcpy(data[count].name, yytext); }
       ;
Surname: ID                    { strcpy(data[count].surname, yytext); }
       ;
Year   : NUM                   { data[count].year= atoi(yytext); }
       ;

%%

I get this error:

conflicts: 5 shift/reduce

Any idea where I went wrong?

rici rici · Accepted Answer · 2013-07-11T15:49:13

You can use the -v option to get bison to produce an .output file containing a lot more information which can help you diagnose shift/reduce conflicts. In particular, it will show you every parser state, including the list of items, and also indicate which states have conflicts.

But in this case, the problem is pretty simple. Stripped to its essentials you have:

List  : Record

Record: Something
      | /* Nothing */

Ignoring what the definition of Something is, the problem is that a List can consist of any number of Records, one after another, and a Record can be empty. That means that nothing can be parsed as any number of empty Records, which is totally ambiguous. Any two consecutive Somethings in the input could be separated by 0, 1, 2, 42, or 273 empty Records. Since the parser can't know whether to start parsing a new Something (shift) or to emit an empty Record (reduce), it complains that there is a shift/reduce conflict.

The solution is also pretty simple. We can see that a non-empty Something must end with a NL; presumably the intent was that the File consists of any number of Records, each on its own line. So we can rewrite:

List  : Record
      | List NL Record

Record: Name Surname Year
      | %empty

Now a Record, empty or not, must be followed by either a NL or whatever can follow List (in this case the end-of-input indicator, although you normally don't need to add such a rule explicitly). It cannot be directly followed by another Record.

Shift/reduce conflicts in bison

1 Answers