如何在清晰的語法中解決shift-reduce衝突

我正在嘗試使用LALR（1）解析器生成器（Bison，但該問題不是特定於該工具）解析簡單語法，而且正在打擊轉變 - 減少衝突。我發現有關解決這些文檔和其他來源往往說一個或多個以下：如何在清晰的語法中解決shift-reduce衝突

如果語法是不明確的（如IF-THEN-ELSE歧義），改變語言來解決歧義。
如果是運算符優先級問題，請明確指定優先級。
接受默認分辨率，並告訴生成器不要抱怨它。

然而，所有的這些似乎適用於我的情況：語法是明確的，只要我可以告訴（當然這是不明確的，只有一個字先行的），它只有一個運營商，以及默認分辨率導致在正確形成的輸入上解析錯誤。是否有任何技術可以重新定義語法以消除不屬於上述桶的轉換 - 減少衝突？

爲了具體，這裏所討論的語法：

%token LETTER 

%% 
%start input; 
input:   /* empty */ | input input_elt; 
input_elt:  rule | statement; 
statement:  successor ';'; 
rule:   LETTER "->" successor ';'; 
successor:  /* empty */ | successor LETTER; 
%%

意圖是解析形式的分號分隔的線「[A-ZA-Z] +」或「[A-ZA-Z ] - > [A-Za-z] +「。

來源

2009-06-06 Geoff Romer

Bah，我用編輯理論有些生疏...... 你知道你的語法裏衝突在哪裏嗎？ – 2009-06-06 03:23:08

Bison表示「POSIX表示％開始規則必須出現在%%行之前」。 – 2009-06-06 04:41:56

使用的yacc的Solaris版本，我得到：

1: shift/reduce conflict (shift 5, red'n 7) on LETTER 
state 1 
    $accept : input_$end 
    input : input_input_elt 
    successor : _ (7) 

    $end accept 
    LETTER shift 5 
    . reduce 7 

    input_elt goto 2 
    rule goto 3 
    statement goto 4 
    successor goto 6

所以，麻煩的是，因爲它往往是，空的規則 - 特別是空的繼任者。目前尚不完全清楚您是否希望允許分號作爲有效輸入 - 目前情況如此。如果您將後續規則修改爲：

successor: LETTER | successor LETTER;

消除了轉換/減少衝突。

來源

2009-06-06 04:48:40

感謝您削減語法併發布它。將後續規則更改爲 -

successor:  /* empty */ | LETTER successor;

...爲我工作。 ITYM 語言看起來毫不含糊。

來源

2009-06-06 04:03:40

如何在清晰的語法中解決shift-reduce衝突

回答

相關問題