YACC程序中的移位減少衝突

我已經寫了這個YACC程序來驗證字符串w.r.t語法{c^kaⁿb^m: n ≠ m ∧ k,m,n > 0}。 NL代表換行符。令牌通過已經在那裏的lex傳遞。但是，這個錯誤是給出的。我認爲，產生式規則都OK，但我收到此消息：YACC程序中的移位減少衝突

[[email protected] wali1]$ yacc -d assign1.y 
yacc: 2 shift/reduce conflicts, 1 reduce/reduce conflict.

這裏是我的語法文件：

%{ 
#include<stdio.h> 
%} 
%token NL A B C 
%% 
stmt : C stmt 
| X NL 
| Y NL 
; 
X : A X B 
| X B 
| B 
; 
Y : A Y B 
| A Y 
| A 
; 
%% 
int yyerror(char *msg) 
{ 
printf("Invalid String!\n"); 
exit(0); 
}

來源

2017-10-05 Hailey

你的語法正確無誤的，據我所看到的。但它不是有限的前瞻，更不是LR（1）。

LR（k）解析器必須能夠根據對下一個令牌的檢查，預測非終端完成時輸入點處的縮減。

現在考慮輸入包含A令牌的大數字（相對於k），後面跟着B。如果輸入最終匹配Y，那麼解析器現在必須減少Y → A，然後可能會減少Y → A Y的一個或多個實例，LR解析的從左到右的性質意味着這些減少必須立即發生。

但是沒有看到整個輸入的其餘部分並計算B s的數量，無法知道要減少多少個實例。此外，輸入完全可能與X匹配，在這種情況下，B必須移位，因爲減少到Y不正確。再次，沒有足夠的信息來做出這個決定，直到輸入結束。

通過將-v選項傳遞給yacc/bison生成的狀態表中顯示了這些難題。例如，我們可以看到：

State 1 

    4 X: A . X B 
    7 Y: A . Y B 
    8 | A . Y 
    9 | A . 

    A shift, and go to state 1 
    B shift, and go to state 2 

    B   [reduce using rule 9 (Y)] 
    $default reduce using rule 9 (Y) 

    X go to state 7 
    Y go to state 8

表達的是否最後A降低到Y假設的問題，有更多的A總比B S，或到第一B準備轉變爲將其減少到X，假設有更多B s比A s。

（衝突由前瞻B的兩種不同動作表示，減號動作包含在括號內（[reduce using rule 9 (Y)]），表明野牛通過選擇總是移動來解決衝突。當然，這不是總是正確的分辨率，所以你的解析器將不能正確識別需要縮減操作的輸入。）

該語言確實有LR（1）語法。訣竅是首先識別A s和B的內部平衡序列，而不強制解析器確定它遇到的句子類型。如果遇到B與A不匹配，或者在某些A尚未匹配時發現句子結尾，則可以作出該決定。

這裏，AB是As和Bs的平衡序列。AAB一個或多個A，然後是AB;而ABB是AB後跟一個或多個B s。

stmt: tail NL 
    | C tail NL 
tail: AAB 
    | ABB 
AAB : A AB 
    | A AAB 
ABB : AB B 
    | ABB B 
AB : /* empty */ 
    | A AB B

人們很容易寫

AAB : AA AB 
AA : A 
    | A AA

，但它不會工作，因爲它需要解析器來決定的A是否爲AA的一部分，它曾經看到一個B前。如上所述，A總是移入堆棧，並且在解析器堆棧展開時作出決定。

在另一方面，它會因爲解析器到達第一無與倫比B所有相關決定已經作出的時間是不可能有書面的生產ABB以這種方式（ABB: AB BB; BB: B | BB B）。我選擇像上面那樣做對稱。

來源

2017-10-05 15:23:04 rici

對不起，我沒有得到它，請你提供解決方案。 – Hailey

@海利：好的，增加了解決方案。如果敘述不能使這個過程足夠明顯，我建議你使用[野牛的追蹤功能]（https://www.gnu.org/software/bison/manual/bison.html#Tracing），這可能會有所幫助你可以看到解析器在做什麼。 LR解析的一個很好的參考也可能是有用的。 – rici

YACC程序中的移位減少衝突

回答

相關問題