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

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

这种转变减少了我通过野牛-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'.幸运的是,野牛自动为你做了这件事(但它仍然让你知道它.)

"野牛手册" 第5.2节正是这种转变/减少冲突.正如它所说,如果你想要%expect声明,你可以消除警告信息.

这个特定的转移/减少冲突是原始yacc解析器生成器的解决策略的动机的很大一部分,如yacc或Dragon书中的历史文章所述,因为消除冲突是非常烦人的语法.因此,这个问题的解决方案是一个很好的脑筋急转弯,但不应该在实践中部署.使用Bison的内置模糊消除更具可读性和可维护性,并且这样做没有任何不精确或羞耻感.

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

1. 如果statementin if (expression) statement不能成为if声明,那就不会有问题.else无法开始陈述,因此if ( 0 ) break;无法else在前瞻中减少.问题是if (0) if (0) break; else现在,不清楚是否应该移位(并因此附加到第二个if)或者如果第二个if应该减少,则将else其移到第一个上if.正常练习(和yacc的模糊度解析算法)决定了第一个.

2. 因此,让我们区分完整的if语句和不完整的if语句.现在我们可以说一个不完整的if语句(一个没有else子句)不能立即跟着else.换句话说,完整的if语句不能将不完整的if语句作为其第一个封闭语句.

所以我们可以尝试这样的事情:

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
                       ;