在这个yacc文件中如何找到移位/归约冲突？

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 ;

- neuromancer

Answer 1

正如mientefuego所指出的，你的语法存在经典的“悬挂else”问题。 你可以通过为导致冲突的规则分配优先级来解决这个问题。

导致冲突的规则是：

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

首先，将ELSE和LOWER_THAN_ELSE（一个伪令牌）设置为非关联性：

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE

这是因为LOWER_THAN_ELSE被先声明，导致ELSE的优先级更高。在发生冲突的规则中，你需要为移进(shift)或规约(reduce)操作分配一个优先级：

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 ;

- ardsrk

---

为什么我一开始要将 ELSE 和 LOWER_THAN_ELSE (一个伪记号) 设置为非关联的？ - new_perl

哦，我忽略了它。由于ELSE和LOWER_THAN_ELSE没有相同的优先级，因此似乎不必要。 - ardsrk

%nonassoc是必要的。仅使用%token无法告诉bison有关优先级的任何信息。 - user764754

所有这些都会产生与原始yacc完全相同的结果。值得指出的是，原始冲突是可以预料的，并且通过yacc默认选择shift来正确解决。 - DigitalRoss

Answer 2

也许你应该尝试使用 yacc -v <filename>，它会生成详细的输出信息。

我在这里测试了一下，你的语法描述在经典的“悬挂else”问题上失败了。

请看一下这篇维基百科文章。

- user211430

Answer 3

啊，这个问题的正确答案通常是：什么都不做。

移位/规约冲突在含糊语法中是预期的。它们不是错误，而是冲突。

冲突将通过优先移位而非规约来解决，这恰好解决了经典的悬挂else问题。

而且bison甚至有一个%expect n语句，这样当恰好存在n个冲突时，就不会出现S/R冲突警告。

- DigitalRoss

---

%expect 是最可怕的发明。这就像告诉你的 QC 部门：“我们期望有 5 个 bug，所以如果 bug 的数量恰好是 5，就可以发货了。”没有区分拼写错误消息和格式化硬盘等 bug。 :-) - Ron Burk

但是...但是...s/r冲突不是错误。标记特定的冲突确实更好，但冲突并不完全在规则本身中，而是在生成的状态机中。因此，我们使用%expect来解决它。欢迎来到现实世界。 - DigitalRoss

关于“更喜欢移位而不是规约”的问题：是否有任何（真实的）“规约优先于移位”的案例？Yacc / Bison是否支持“规约优先于移位”？ - pmor

Answer 4

首先，从yacc中获取一个状态机输出state machine output from yacc。一个既可以移位又可以规约的状态表示移位/规约冲突。找到其中一个，然后通过重写语法来解决冲突。

- Yuval F

Answer 5

这篇文章提供了ardsrk发布的另一种解决方案的替代方案。

- Tomato

---

谢谢，我已经更正了链接到正确的地址！ - Tomato