野牛转移减少冲突-无法解决

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手册第5.2节正是关于这种转变/减少冲突的。正如上面所说，如果您希望使用%expect声明，则可以消除警告消息。或者，您可以显式地声明"；优选将CCD_；通过使用bison/yacc的优先级声明来解决问题：赋予else令牌比不带else子句的if产品更高的优先级。(您可能希望在产品本身中使用类似%prec IF的东西，因为默认情况下，产品的优先级是其最后一个终端，在本例中，它将是一个右括号。)

这种特定的移位/减少冲突是原始yacc语法分析器生成器解决策略的主要动机，如关于yacc的历史性论文或Dragon的书中所述，因为从语法中消除冲突有点烦人。这个问题的解决方案是一个很好的脑筋急转弯，但在实践中，使用优先级声明或Bison内置的模糊消除通常更容易，也更容易维护。

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

1. 如果if (expression) statement中的statement不能是if语句，则不会出现问题。else不能开始一个语句，因此if ( 0 ) break;不能在前瞻中用else减少。问题是if (0) if (0) break; else现在，还不清楚是否应该移动else(从而连接到第二个if)，或者是否应该减少第二个if，从而使else移动到第一个if上。常规实践(以及yacc的模糊度解决算法)规定了第一个。

2. 因此，让我们区分完整if语句和不完整if语句。不完整的if语句是一个本可以用else子句完成的语句，因此它不能立即跟在else后面(因为它本来包括else0)。完整的语句不能用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

在这里看到我的答案：改革语法以删除if-then-else中的shift减少冲突。根据我的经验，你永远不应该离开"已知的冲突"，解决它们。将%expect N与N一起使用！=0不安全，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的回答是(至少看起来是)好的。有点适应：

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_startment(如RETURN ';')。否则，例如

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

复制：

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

并将第一个变体添加到if_statements，将第二个添加到noif_statents。

Answer 4

另一种有效的策略(@rici接受的答案不起作用，@RaqaouPi认为Chris Dodd的答案起作用)是将代码视为一系列if-else/for/while前缀，后面可能是一个悬空的if或结尾的一个简单语句。这个例子是根据Nearley语法改编的，用于C语言。

Statement         -> StatementPrefix:* (StatementEnd | DanglingIf)
StatementNoDangle -> StatementPrefix:* StatementEnd
StatementPrefix -> "if" _ "(" _ Expression _ ")" _ StatementNoDangle _ "else" _
| "while" _ "(" _ Expression _ ")" _
DanglingIf     -> "if" _ "(" _ Expression _ ")" _ Statement
StatementEnd   -> Simple _ ";"
| "return" (_ Expression):? _ ";"
| BlockStatement
| "break" _ ";"
| "continue" _ ";"