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?

Answer 1

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
    | 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.

In this case the solution is 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:

File:    List EOF
    ;

List:    Record
    |    List NL Record
    ;

Record:  Name Surname Year
      |  /* Empty */
      ;

Now a Record, empty or not, must be followed by either an EOF or a NL. It cannot be directly followed by another Record.