如何在這個yacc文件中找到shift/reduce衝突？

Question

當我嘗試在以下文件上使用yacc時，出現錯誤衝突：1 shift/reduce 如何找到並解決衝突？

/* 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

正如mientefuego指出的那樣，語法有一個經典的「懸而未決」的問題。 您可以通過將優先級分配給導致衝突的規則來解決問題。

規則引起的衝突是：通過使ELSE和LOWER_THAN_ELSE（僞令牌）的非關聯

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

先啓動：

%nonassoc LOWER_THAN_ELSE 
%nonassoc ELSE 

這讓都更優於LOWER_THAN_ELSE只是因爲LOWER_THAN_ELSE首先被宣佈。

然後，在衝突的規則必須將一個優先級分配給任一移位或降低動作：

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

這裏，更高的優先級給予移動。我已摻入上述校正和下面列出的完整的語法：

/* 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

首先，獲得state machine output from yacc。可以移位或減少的狀態代表移位/減少衝突。找到一個，然後通過重寫語法來解決衝突。

Answer 3

也許你應該試試yacc -v <filename>，它會生成細節的輸出。

我在這裏測試過，你的語法描述在經典的「dangling else」問題中失敗。

看看this Wikipedia article。

Answer 4

This本文給出的替代解決方案的一個張貼由ardsrk。

Answer 5

Ahem，這個問題的正確答案通常是：什麼都不做。

移位/減少衝突是預期與歧義文法。他們不是錯誤，他們是衝突。

衝突將通過寧願轉移減少來解決，這恰好解決了典型的懸擺問題。

野牛甚至有一個％預計ň語句，這樣，當有確切ň衝突，你沒有得到一個S/R衝突警告。