野牛移減少衝突 - 無法解析

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'。幸運的是，野牛自動爲你做了這件事（但它仍然讓你知道它）。

Bison手冊的5.2部分正是關於這種轉換/減少衝突。正如它在那裏所說的那樣，如果您希望申報%expect，則可以消除警告消息。

這個特定的轉換/減少衝突是原始yacc解析器生成器的解決策略的動機的很大一部分，正如yacc的歷史性論文或龍書中所描述的，因爲它令人難以置信地煩人從語法中消除衝突。所以這個問題的解決方案是一個很好的腦筋急轉彎，但不應該在實踐中部署。使用Bison的內置歧義消除功能更具可讀性和可維護性，而且這樣做沒有不準確或恥辱。

如果我沒有記錯，這個問題是龍書中的練習之一。該解決方案的基本輪廓是這樣的：

1. 有不會是一個問題，如果在if (expression) statement的statement不可能是if聲明。 else無法開始聲明，所以if (0) break;不能用else縮小。問題是if (0) if (0) break; else現在，不清楚是否應該移位（因而附加到第二個），或者如果應該減少第二個，則將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 
         ; 

Answer 2

見我的答案在這裏：Reforming the grammar to remove shift reduce conflict in if-then-else。根據我的經驗，你永遠不應該離開「已知的衝突」，解決它們。在N！= 0時使用％expect N是不安全的，恕我直言（當然，GLR不在這裏）。