Bison 转移减少冲突 - 无法解决

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 得到的转变减少冲突处于状态 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 已经自动为您完成了(但它仍然让您知道。)
Bison 手册的 Section 5.2 正是关于这种转变/减少冲突。正如那里所说，如果您想使用 %expect 声明，您可以消除警告消息。或者，您可以通过使用 bison/yacc 的优先级声明显式声明“首选移动 else”解决方案:为 else 标记提供比没有 if 子句的 else 产生式更高的优先级。 (您可能希望在产生式本身中使用类似 %prec IF 的东西，因为默认情况下，产生式具有其最后一个终端的优先级，在这种情况下将是一个右括号。)
这种特定的 shift/reduce 冲突是原始 yacc 解析器生成器解析策略的很大一部分动机，如关于 yacc 的历史论文或 Dragon 书中所述，因为从一个语法。这个问题的解决方案是一个很好的脑筋急转弯，但在实践中，使用优先声明或 Bison 的内置歧义消除通常更容易和更易于维护。
此题为龙书习题之一。解决方案的基本轮廓是这样的:

如果 statement 中的 if (expression) statement 不能是 if 语句，就不会有问题。 else 不能开始一个语句，所以 if ( 0 ) break; 不能在前瞻中用 else 减少。问题是 if (0) if (0) break; else 现在，else 是否应该被移动(从而附加到第二个 if)或者是否应该减少第二个 if ，让 else 被移动到第一个 if 上并不明显。通常的做法(和 yacc 的歧义解决算法)规定了第一个。

所以让我们区分完整的 if 语句和不完整的 if 语句。不完整的 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 这样的语言还有其他语句类型，它们可以以封闭语句(例如循环语句)结尾。所有这些也必须分为“完整”和“不完整”，这取决于终止语句的完整性。这就是让这个解决方案烦人的原因。
注意:以上语法已从九年前发布的错误版本中更正。几个答案指的是错误的答案；不幸的是，他们都没有想到用我可能会看到的评论来表示错误。如果有人使用了错误的代码，我深表歉意。