21

当我尝试在以下文件上使用 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 ;
4

5 回答 5

21

正如 mientefuego 指出的那样，您的语法存在经典的“悬空其他”问题。您可以通过为导致冲突的规则分配优先级来解决问题。

引起冲突的规则是：

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

首先让 ELSE 和 LOWER_THAN_ELSE （一个伪标记）非关联：

%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE

这使得 ELSE 比 LOWER_THAN_ELSE 更优先，因为首先声明了 LOWER_THAN_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 ;
于 2009-11-15T14:11:25.443 回答
7

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

我在这里测试过，你的语法描述在经典的“悬空其他”问题中失败了。

看看这篇维基百科文章。

于 2009-11-15T13:21:34.077 回答
4

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

模棱两可的语法预计会发生移位/减少冲突。它们不是错误，它们是冲突。

冲突将通过优先使用 shift 而不是 reduce 来解决，这恰好解决了规范的悬空 else 问题。

bison 甚至还有一个 %expect n语句，这样当恰好有n 个冲突时，您就不会收到 S/R 冲突警告。

于 2013-01-11T23:11:21.027 回答
0

首先，从 yacc 获取状态机输出。可以移位或减少的状态表示移位/减少冲突。找到一个，然后通过重写语法解决冲突。

于 2009-11-15T12:58:28.620 回答
0

本文提供了 ardsrk 发布的解决方案的替代解决方案。

于 2012-04-02T04:30:32.413 回答