4

语法如下：

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)

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

4

4 回答 4

8

您可能希望解决冲突以转移“其他”。幸运的是，bison 自动为您完成了这项工作（但它仍然让您知道它。）

Bison 手册的第 5.2 节正是关于这种移位/减少冲突。正如它在那里所说，如果您想使用%expect声明，您可以消除警告消息。或者，您可以通过使用 bison/yacc 的优先级声明明确声明“更喜欢转移else”解决方案：赋予else令牌比if不带else子句的产品更高的优先级。（您可能希望%prec IF在产品本身中使用类似的东西，因为默认情况下，产品具有其最后一个终端的优先级，在这种情况下将是一个右括号。）

这种特定的 shift/reduce 冲突是原始解析器生成器解析策略的很大一部分动机yacc，如关于 yacc 的历史论文或 Dragon book 中所述，因为从语法。这个问题的解决方案是一个很好的脑筋急转弯，但在实践中，使用优先声明或 Bison 的内置歧义消除通常更容易且更易于维护。

这道题是龙书的习题之一。解决方案的基本轮廓如下所示：

  1. 如果statementinif (expression) statement不能是一个if语句，就不会有问题。else不能开始一个语句，所以if ( 0 ) break;不能else在前瞻中减少。问题是if (0) if (0) break; else现在，是否应该转移 else （并因此附加到第二个 if ）或者是否if应该减少第二个，将elseto 转移到第一个上并不明显if。常规做法（和 yacc 的歧义解决算法）规定了第一个。

  2. 因此，让我们区分完整的 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 这样的语言还有其他可以以封闭语句结尾的语句类型（例如循环语句）。根据终止语句的完整性，所有这些也必须在“完整”和“不完整”之间进行划分。这就是使该解决方案令人讨厌的原因。

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

于 2012-10-04T04:57:28.363 回答
4

在这里查看我的答案：Reforming the grammar to remove shift减少 if-then-else 中的冲突。根据我的经验，你永远不应该离开“已知冲突”，解决它们。使用 %expect N 和 N != 0 是不安全的，恕我直言（当然 GLR 除外）。

于 2012-10-04T19:33:37.987 回答
2

我试过@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_statement（如RETURN ';'）。否则，例如

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

复制它：

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

并将第一个变体添加到if_statement s 和第二个变体到noif_statement s。

于 2018-03-14T22:23:33.597 回答
0

另一种有效的策略（@rici 接受的答案不起作用，@RaqaouPi 归功于 Chris Dodd 的答案）是将代码视为一系列 if-else/for/while 前缀，可能是一个悬空的 if或最后的简单陈述。此示例改编自类似 C 语言的 Nearley 语法。

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" _ ";"
于 2018-09-10T21:17:05.910 回答