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?

Accepted Answer

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

Solution

Problem