Bison shift-reduce冲突-无法解决

Question

语法如下：

1. program -> declaration-list
2. declaration-list -> declaration-list declaration | declaration
3. declaration -> var-declaration | fun-declaration
4. var-declaration -> type-specifier ID ; | type-specifier ID [ NUM ] ;
5. type-specifier -> int | void
6. fun-declaration -> type-specifier ID ( params ) compound-stmt
7. params -> param-list | void
8. param-list -> param-list , param | param
9. param -> type-specifier ID | type-specifier ID [ ]
10. compound-stmt -> { local-declarations statement-list }
11. local-declarations -> local-declarations var-declarations | empty
12. statement-list -> statement-list statement | empty
13. statement -> expression-stmt | compound-stmt | selection-stmt |
iteration-stmt | return-stmt
14. expression-stmt -> expression ; | ;
15. selection-stmt -> if ( expression ) statement |
if ( expression ) statement else statement
16. iteration-stmt -> while ( expression ) statement
17. return-stmt -> return ; | return expression ;
18. expression -> var = expression | simple-expression
19. var -> ID | ID [ expression ]
20. simple-expression -> additive-expression relop additive-expression |
additive-expression
21. relop -> <= | < | > | >= | == | !=
22. additive-expression -> additive-expression addop term | term
23. addop -> + | -
24. term -> term mulop factor | factor
25. mulop -> * | /
26. factor -> ( expression ) | var | call | NUM
27. call -> ID ( args )
28. args -> arg-list | empty
29. arg-list -> arg-list , expression | expression

我通过bison -d -v xyz.l得到shift reduce处于状态97

state 97

   29 selection-stmt: IF LFT_BRKT expression RGT_BRKT statement .
   30               | IF LFT_BRKT expression RGT_BRKT statement . ELSE statement

    ELSE  shift, and go to state 100

    ELSE      [reduce using rule 29 (selection-stmt)]
    $default  reduce using rule 29 (selection-stmt)

但是我不知道如何解决这个冲突。等待答案。

Answer 1

您可能想要解决冲突，以支持转移“else”。幸运的是，bison已经自动为您完成了这项工作(但它仍然会让您了解它)。

野牛手册的Section 5.2就是关于这种转移/减少冲突的。正如它所说的，如果您想要使用%expect声明，您可以消除警告消息。或者，您可以通过使用bison/yacc的优先级声明来显式声明“首选移位else”解决方案:赋予else标记比不带if子句的else生成更高的优先级。(您可能希望在产品本身中使用类似%prec IF的内容，因为默认情况下，产品具有其最后一个终端的优先级，在本例中，最后一个终端将是一个右括号。)

这个问题的解决方案是一个很好的脑筋急转弯，但在实践中，使用优先声明或Bison内置的歧义消除通常更容易和更易于维护。

这个问题是“龙”书中的练习之一。解决方案的基本轮廓是这样的：

1. 如果if (expression) statement中的statement不能是if语句，则不会出现问题。else不能开始语句，因此不能在前视中使用else来减少if ( 0 ) break;。现在的问题是if (0) if (0) break; else，不清楚是否应该移位(并因此附加到第二个if)，或者是否应该减少第二个if，让else移动到第一个if上。通常的做法(以及yacc的歧义解决算法)决定了第一个。

所以让我们来区分完整的if语句和不完整的if语句。，，

1. ，
2. 。不完整的if语句是一个本可以用else子句完成的语句，因此后面不能紧跟else (因为它会包含else)。完整的语句不能用else扩展，因此也不能以不完整的语句结尾。

因此，我们可以尝试如下所示：

statement              : complete_statement
                       | incomplete_conditional

complete_statement     : complete_conditional
                       | statement_other_than_conditional

complete_conditional   : "if" '(' expression ')' complete_statement "else" complete_statement

incomplete_conditional : "if" '(' expression ')' statement
                       | "if" '(' expression ')' complete_statement "else" incomplete_conditional

像C这样的语言还有其他语句类型，它们可以以封闭语句(例如循环语句)结束。所有这些也必须根据终止语句的完整性分为“完整”和“不完整”。这就是这个解决方案让人讨厌的地方。

注:上述语法已从九年前发布的不正确版本中更正。有几个答案指的是不正确的答案；不幸的是，他们都没有想到用我可能会看到的注释来表示错误。如果有人使用了错误的代码，我深表歉意。

Answer 2

请看我的答案：Reforming the grammar to remove shift reduce conflict in if-then-else。在我的经验中，你永远不应该离开“已知的冲突”，解决它们。在N != 0的情况下使用%expect N是不安全的，IMHO (当然，除了GLR)。

Answer 3

我试过@rici的答案(公认的答案)，但它失败。

statement: conditional | statement_other_than_conditional;
conditional: complete_conditional | incomplete_conditional;
complete_conditional: L_IF '(' expression ')' statement_other_than_conditional L_ELSE statement
| L_IF '(' expression ')' complete_conditional L_ELSE statement;
incomplete_conditional: L_IF '(' expression ')' statement;
statement_other_than_conditional: ';';
expression: IDENTIFIER;

$ bison --report=all rrr.y
rrr.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]

State 14 conflicts: 1 shift/reduce
State 15 conflicts: 1 shift/reduce

State 14

3 conditional: complete_conditional .  [$end, L_ELSE]
6 complete_conditional: L_IF '(' expression ')' complete_conditional . L_ELSE statement

L_ELSE  shift, and go to state 16

L_ELSE    [reduce using rule 3 (conditional)]
$default  reduce using rule 3 (conditional)


State 15

2 statement: statement_other_than_conditional .  [$end, L_ELSE]
5 complete_conditional: L_IF '(' expression ')' statement_other_than_conditional . L_ELSE statement

L_ELSE  shift, and go to state 17

L_ELSE    [reduce using rule 2 (statement)]
$default  reduce using rule 2 (statement)

Chris Dodd's answer是(至少看起来是)好的。稍微适应一下：

statement: if_statement | noif_statement;

if_statement:
  IF '(' expression ')' statement
| IF '(' expression ')' noif_statement ELSE if_statement
;

noif_statement:
  IF '(' expression ')' noif_statement ELSE noif_statement
| RETURN ';'
;

expression: IDENTIFIER;

如果你有更多的语句规则:如果它不是右递归(不以statement结尾)，那么只添加到noif_statement (如RETURN ';')。否则，例如

statement: blah '(' blah ')' statement ;

复制它：

| blah '(' blah ')' if_statement
| blah '(' blah ')' noif_statement

并将第一个变体添加到_if_statement_s，将第二个变体添加到_noif_statement_s。