Warnung: 2 verringern/verringern Konflikte [-Wconflicts-rr] in yacc Grammatik

Question

ich habe folgende yacc Grammatik:

%{ 
#include <stdio.h> 
extern FILE* yyin; 
extern char* yytext; 

%} 

%token VAR ID_NAME TYPE_STRING TYPE_BOOL TYPE_NUMBER 
%token CONST VALUE_STRING VALUE_BOOL VALUE_NUMBER 

%% 

program 
    : declarations 
    ; 

declarations 
    : declaration 
    | declarations declaration 
    ; 

declaration 
    : var_declaration 
    | const_declaration 
    ; 

value 
    : VALUE_BOOL 
    | VALUE_STRING 
    | VALUE_NUMBER 
    ; 

assignment 
    : ID_NAME '=' value 
    ; 

assignments 
    : assignment 
    | assignments ',' assignment 
    ; 

id_list 
    : ID_NAME 
    | id_list ',' ID_NAME 
    ; 

declaration_expression 
    : assignments 
    | id_list 
    | assignments ',' declaration_expression 
    | id_list ',' declaration_expression 
    ; 

var_declaration 
    : VAR ':' type declaration_expression ';' { printf("%s var\n", $1); } 
    ; 

const_declaration: CONST ':' type assignments ';' {printf("const\n");} 
    ; 

type: TYPE_NUMBER 
    | TYPE_STRING 
    | TYPE_BOOL 
    ; 

%% 
void yyerror (char const *s) { 
    fprintf (stderr, "%s\n", s); 
} 

int main(int argc, char** argv[]) 
{ 

    yyparse(); 
    return 0; 
} 

Es soll eine kleine Sprache beschreiben, die Variablen und Konstanten Deklarationen der Form ermöglicht: var:<type> <variables_names or variables_initializations> und const:<type> <constants_initialization>.

Ich möchte für die folgende Syntax-Unterstützung hinzufügen:

var:<type> var1, var2=<value>, var3; 

Etwas wie folgt aus: var:<type> (<variables_names>|<variable_initializations>)+.

Um das zu erreichen, dass ich die folgenden Änderungen an meine Grammatik hinzugefügt haben:

assignments 
    : assignment 
    | assignments ',' assignment 
    ; 

id_list 
    : ID_NAME 
    | id_list ',' ID_NAME 
    ; 

declaration_expression 
    : assignments 
    | id_list 
    | assignments ',' declaration_expression 
    | id_list ',' declaration_expression 
    ; 

Was ich dachte, das (<variables_names>|<variable_initializations>)+ Teil ermöglichen. Aber ich bekomme einen reduce/reduce Konflikt aufgrund dieser Zeilen:

| assignments ',' declaration_expression 
    | id_list ',' declaration_expression 

Was mache ich falsch?

Answer 1

Wenn ich Sie richtig verstehe, möchten Sie eine Mischung aus bloßen Variablennamen und Variableninitialisierungen in einer var Deklaration und nur Initialisierungen in einer Deklaration zulassen. Das ist ziemlich geradlinig:

initialization : ID '=' value 
init_list  : initialization | init_list ',' initialization 
init_or_id  : initialization | ID 
init_or_id_list: init_or_id 
       | init_or_id_list ',' init_or_id 

const_declaration: CONST ':' type init_list 
var_declaration : VAR ':' type init_or_id_list 

Was du falsch gemacht hast war eine gemischte Liste zu machen, indem eine gemischte Liste mit Listen erstreckt, eher mit Artikeln. Das ist mehrdeutig, so dass es zu einem Konflikt kommt.

Das obige funktioniert (wie auch Ihr Original), weil init_list und init_or_id_list niemals (als Nicht-Terminals) am selben Punkt in einer Ableitung erscheinen können. Einer von ihnen folgt eindeutig dem Schlüsselwort const, und der andere folgt eindeutig dem Schlüsselwort var. Das ist gut so, denn eine Liste von reinen Zuweisungen würde beide Produktionen zufriedenstellen, was einen Konflikt reduzieren/reduzieren würde, wenn sie einen Kontext teilen würden. Dieses Problem ist auch lösbar, und da es gelegentlich auftritt, werde ich die Lösung hinzufügen, obwohl ich betonen, dass es nicht relevant auf diese spezielle Frage ist. (Es könnte jedoch für einige spätere Leser mit einem ähnlichen Problem relevant sein.) Um die beiden möglichen Listensyntaxen eindeutig zu machen, ist es notwendig, sicherzustellen, dass die potentiell reine Zuordnungsliste immer die Ableitung einer anderen Produktion von ist die gemischte Liste. So konnten wir schreiben:

init_list: initialization | init_list initialization 
init_or_id_list: ID 
       | init_list ',' ID 
       | init_or_id_list ',' init_or_id 

Nun wird ein init_or_id_list notwendigerweise mindestens ein ID Element, so kann es nicht mit init_list verwechselt werden. Aber jetzt verwenden wir das Endergebnis, wir müssen uns daran erinnern, dass ein Kontext, der eine gemischte Liste akzeptiert, beide Listenmöglichkeiten zulassen muss:

pure_list: init_list 
mixed_list: init_list | init_or_id_list