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

问题描述

语法如下:

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

我通过野牛-d -v xyz.l得到的减少位移的冲突处于状态97

The shift reduce conflict that I get through bison -d -v xyz.l is in state 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)

但我不知道如何解决此冲突.等待答案.

But I do not know how to resolve this conflict. Waiting for an answer.

推荐答案

您可能希望解决冲突，而转移"else".幸运的是，野牛会自动为您完成此操作(但仍然可以让您知道这一点.)

You would want to resolve the conflict in favour of shifting the 'else'. Fortunately, bison has done that for you automatically (but it still lets you know about it.)

Bison手册的 5.2 正是关于这种移位/减少冲突.如此处所说，如果要使用%expect声明，则可以消除警告消息.

Section 5.2 of the Bison manual is about precisely this shift/reduce conflict. As it says there, you can eliminate the warning message if you want to with a %expect declaration.

如yacc的历史性论文或《 Dragon》一书中所述，这种特定的移位/减少冲突是原始yacc解析器生成器解决策略动机的很大一部分，因为它令人难以置信地令人讨厌从语法上消除冲突.因此，解决这个问题的方法很不错，但是绝不应该在实践中使用.使用Bison内置的歧义消除功能更具可读性和可维护性，并且这样做没有不精确性或耻辱感.

This specific shift/reduce conflict was a large part of the motivation for the resolution strategy of the original yacc parser-generator, as described in the historic paper on yacc, or in the Dragon book, because it is incredibly annoying to eliminate the conflict from a grammar. So the solution to this question is a nice brain-teaser, but should never be deployed in practice. Using Bison's built-in ambiguity elimination is much more readable and maintainable, and there is no imprecision or shame in doing so.

如果我没记错的话，这个问题是《龙》书中的练习之一.解决方案的基本概述如下:

If I recall correctly, this problem is one of the exercises in the Dragon book. The basic outline of the solution goes like this:

1. 如果if (expression) statement中的statement不能为if语句，则不会有问题. else无法开始声明，因此在前瞻中不能使用else来简化if ( 0 ) break;.问题是if (0) if (0) break; else现在，不清楚是否应该移动其他字符(并附加到第二个if上)还是应该减小第二个if，而将else移到第一个if .通常的做法(以及yacc的歧义解决算法)决定了第一个.

1. There would not be an issue if the statement in if (expression) statement could not be an if statement. else cannot begin a statement, so if ( 0 ) break; cannot be reduced with else in the lookahead. The problem is if (0) if (0) break; else Now, it's not obvious whether else should be shifted (and thereby attached to the second if) or if the second if should be reduced, leaving the else to be shifted onto the first if. Normal practice (and yacc's ambiguity resolution algorithm) dictate the first.

因此，让我们区分完整的if语句和不完整的if语句.现在我们可以说，不完整的if语句(一个没有else子句的语句)不能紧跟在else之后.换句话说，一个完整的if语句不能将不完整的if语句作为其第一个包含的语句.

So let's distinguish between complete if-statements and incomplete if-statements. Now we can say that an incomplete if-statement (one without an else clause) cannot be immediately followed by else. In other words, a complete if-statement cannot have an incomplete if-statement as its first enclosed statement.

所以我们可以尝试类似的东西:

So we can try something like:

conditional            : complete_conditional
                       | incomplete_conditional
                       ;

complete_conditional   : IF ( expression ) statement_other_than_conditional ELSE statement
                       | IF ( expression ) complete_conditional ELSE statement
                       ;

incomplete_conditional : IF ( expression ) statement
                       ;

现在我们需要:

statement              : statement_other_than_conditional
                       | incomplete_conditional
                       | complete_conditional
                       ;

这篇关于野牛移位减少冲突-无法解决的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！