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