Come trovare lo spostamento/riduzione dei conflitti in questo file yacc?

Question

Quando provo a utilizzare yacc nel seguente file ottengo i conflitti di errore: 1 spostamento/riduzione Come posso trovare e risolvere il conflitto?

/* C-Minus BNF Grammar */ 

%token ELSE 
%token IF 
%token INT 
%token RETURN 
%token VOID 
%token WHILE 

%token ID 
%token NUM 

%token LTE 
%token GTE 
%token EQUAL 
%token NOTEQUAL 
%% 

program : declaration_list ; 

declaration_list : declaration_list declaration | declaration ; 

declaration : var_declaration | fun_declaration ; 

var_declaration : type_specifier ID ';' 
       | type_specifier ID '[' NUM ']' ';' ; 

type_specifier : INT | VOID ; 

fun_declaration : type_specifier ID '(' params ')' compound_stmt ; 

params : param_list | VOID ; 

param_list : param_list ',' param 
      | param ; 

param : type_specifier ID | type_specifier ID '[' ']' ; 

compound_stmt : '{' local_declarations statement_list '}' ; 

local_declarations : local_declarations var_declaration 
        | /* empty */ ; 

statement_list : statement_list statement 
       | /* empty */ ; 

statement : expression_stmt 
      | compound_stmt 
      | selection_stmt 
      | iteration_stmt 
      | return_stmt ; 

expression_stmt : expression ';' 
       | ';' ; 

selection_stmt : IF '(' expression ')' statement 
       | IF '(' expression ')' statement ELSE statement ; 

iteration_stmt : WHILE '(' expression ')' statement ; 

return_stmt : RETURN ';' | RETURN expression ';' ; 

expression : var '=' expression | simple_expression ; 

var : ID | ID '[' expression ']' ; 

simple_expression : additive_expression relop additive_expression 
        | additive_expression ; 

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ; 

additive_expression : additive_expression addop term | term ; 

addop : '+' | '-' ; 

term : term mulop factor | factor ; 

mulop : '*' | '/' ; 

factor : '(' expression ')' | var | call | NUM ; 

call : ID '(' args ')' ; 

args : arg_list | /* empty */ ; 

arg_list : arg_list ',' expression | expression ; 

Answer 1

Come mientefuego ha sottolineato che la grammatica ha il classico problema "dangling else". È possibile superare il problema assegnando la precedenza alle regole che causano conflitti.

La regola che causa conflitto è:

selection_stmt : IF '(' expression ')' statement 
       | IF '(' expression ')' statement ELSE statement ; 

Primo avvio facendo altro e LOWER_THAN_ELSE (uno pseudo-token) non associativa:

%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE 

Questo dà ELSE più la precedenza su LOWER_THAN_ELSE semplicemente perché LOWER_THAN_ELSE è dichiarato per primo.

Poi nella norma contraria occorre assegnare una precedenza a uno spostamento o ridurre l'azione:

selection_stmt : IF '(' expression ')' statement %prec LOWER_THAN_ELSE ; 
       | IF '(' expression ')' statement ELSE statement ; 

Qui, più alta la precedenza è data a spostare. Ho inserito le correzioni sopra citati ed elencati la grammatica completa qui sotto:

/* C-Minus BNF Grammar */ 

%token ELSE 
%token IF 
%token INT 
%token RETURN 
%token VOID 
%token WHILE 

%token ID 
%token NUM 

%token LTE 
%token GTE 
%token EQUAL 
%token NOTEQUAL 

%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE 
%% 

program : declaration_list ; 

declaration_list : declaration_list declaration | declaration ; 

declaration : var_declaration | fun_declaration ; 

var_declaration : type_specifier ID ';' 
       | type_specifier ID '[' NUM ']' ';' ; 

type_specifier : INT | VOID ; 

fun_declaration : type_specifier ID '(' params ')' compound_stmt ; 

params : param_list | VOID ; 

param_list : param_list ',' param 
      | param ; 

param : type_specifier ID | type_specifier ID '[' ']' ; 

compound_stmt : '{' local_declarations statement_list '}' ; 

local_declarations : local_declarations var_declaration 
        | /* empty */ ; 

statement_list : statement_list statement 
       | /* empty */ ; 

statement : expression_stmt 
      | compound_stmt 
      | selection_stmt 
      | iteration_stmt 
      | return_stmt ; 

expression_stmt : expression ';' 
       | ';' ; 

selection_stmt : IF '(' expression ')' statement %prec LOWER_THAN_ELSE ; 
       | IF '(' expression ')' statement ELSE statement ; 

iteration_stmt : WHILE '(' expression ')' statement ; 

return_stmt : RETURN ';' | RETURN expression ';' ; 

expression : var '=' expression | simple_expression ; 

var : ID | ID '[' expression ']' ; 

simple_expression : additive_expression relop additive_expression 
        | additive_expression ; 

relop : LTE | '<' | '>' | GTE | EQUAL | NOTEQUAL ; 

additive_expression : additive_expression addop term | term ; 

addop : '+' | '-' ; 

term : term mulop factor | factor ; 

mulop : '*' | '/' ; 

factor : '(' expression ')' | var | call | NUM ; 

call : ID '(' args ')' ; 

args : arg_list | /* empty */ ; 

arg_list : arg_list ',' expression | expression ; 

Answer 2

In primo luogo, ottenere un state machine output from yacc. Uno stato che può essere spostato o ridotto rappresenta uno spostamento/riduzione del conflitto. Trova uno e poi risolvi il conflitto riscrivendo la grammatica.

Answer 3

forse dovresti provare a yacc -v <filename>, genera un'uscita dei dettagli.

Ho eseguito il test qui e la descrizione della grammatica non funziona nel classico problema "penzolante".

Dai uno sguardo allo this Wikipedia article.

Answer 4

This un articolo fornisce una soluzione alternativa a quella pubblicato da ardsrk.

Answer 5

Ahem, la risposta corretta a questo problema è di solito: non fanno nulla.

I conflitti di shift/riduzione sono attesi con grammatiche ambigue. Non sono errori, sono conflitti.

Il conflitto si risolverà preferendo lo shift over reduce, il che equivale a risolvere il problema canonico dell'altro dangling.

e Bison ha anche un% si aspetta n dichiarazione in modo che non si ottiene un messaggio di avviso di conflitto S/R, quando ci sono esattamente n conflitti.