Shift/reduzieren Konflikte in Bison

Question

Ich bin neu in Bison und ich habe Probleme mit Schiebe-/reduzieren Konflikte ... Ich versuche, aus der Datei zu array data[] zu laden:

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

Hier ist ein Teil mein 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); } 
     ; 

%%    

ich diesen Fehler:

conflicts: 5 shift/reduce 

Jede Idee, wo ich schief gelaufen?

Answer 1

Sie können die Option -v verwenden, um bison zu erhalten, um eine .output Datei zu erstellen, die viel mehr Informationen enthält, die Ihnen bei der Diagnose von Shift/Reduce-Konflikten helfen können. Insbesondere zeigt es Ihnen jeden Parserstatus, einschließlich der Liste der Elemente, und zeigt auch an, in welchen Zuständen Konflikte auftreten.

Aber in diesem Fall ist das Problem ziemlich einfach. Stripped auf das Wesentliche Sie haben:

List: Record 
    | List Record 
    ; 

Record: Something 
     | /* Nothing */ 
     ; 

ignorieren, was die Definition von Something ist, ist das Problem, dass ein List einer beliebigen Anzahl von Records, einer nach dem anderen bestehen kann, und ein Record kann leer sein. Das bedeutet, dass nichts geparst werden kann, wie eine beliebige Anzahl von leeren Records, die völlig mehrdeutig ist. Beliebige zwei aufeinanderfolgende Somethings im Eingang könnten durch 0, 1, 2, 42 oder 273 leer Records getrennt werden. Da der Parser nicht wissen kann, ob er eine neue Something (shift) analysieren oder eine leere Record (reduce) ausgeben soll, beschwert er sich, dass es einen Shift/Reduce-Konflikt gibt.

In diesem Fall ist die Lösung ziemlich einfach. Wir können sehen, dass ein nicht leerer Something mit einem NL enden muss; vermutlich war die Absicht, dass die File aus einer beliebigen Anzahl von Records besteht, jede auf einer eigenen Linie. So können wir umschreiben:

File: List EOF 
    ; 

List: Record 
    | List NL Record 
    ; 

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

nun eine Record, leer oder nicht, muss entweder durch eine EOF oder NL folgen. Es kann nicht direkt von einem anderen Record gefolgt werden.