縮小/減少語法

衝突讓我們想象一下我希望能夠解析這樣的值（每行是一個單獨的例子）：縮小/減少語法

x 
(x) 
((((x)))) 
x = x 
(((x))) = x 
(x) = ((x))

我寫這個YACC語法：

%% 
Line: Binding | Expr 
Binding: Pattern '=' Expr 
Expr: Id | '(' Expr ')' 
Pattern: Id | '(' Pattern ')' 
Id: 'x'

但我得到一個減少/減少衝突：

$ bison example.y 
example.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]

任何提示，如何解決呢？我正在使用GNU野牛3.0.2

來源

2014-09-05 tokland

你的語法不是LR(k)任何k。所以你要麼修復語法，要麼使用GLR parser。

假設輸入開頭：

(((((((((((((x

到這裏，是沒有問題的，因爲每一個字符已轉移到分析器棧。

但現在呢？在下一步中，必須減少x，並且向前看)。如果將來某處有=，則x是Pattern。否則，它是一個Expr。

您可以修復由語法：

擺脫Pattern，改變Binding到Expr | Expr '=' Expr;
擺脫Expr所有的定義，並與Expr: Pattern

替換它們

第二種選擇可能更好在l因爲很可能在您想象（或正在開發）的完整語法中，Pattern是Expr的子集，而不是與Expr相同。將Expr分解爲Pattern的單位生產，非模式替代將允許您使用LALR(1)解析器解析語法（如果語法的其餘部分符合）。

或者您可以使用GLR語法，如上所述。

來源

2014-09-05 15:14:51 rici

謝謝，現在很清楚。在真正的語法模式和表達式中相似但不相同（它們在AST中產生不同的節點）。在野牛中啓用GLR解析器的確解決了這個問題（我想性能不會很好，但我不在乎這是否簡化了語法）。 – tokland 2014-09-08 10:16:33

減少/減少衝突常常意味着語法中存在一個基本問題。

解決的第一步是獲取輸出文件（bison -v example.y產生example.output）。野牛2.3說（部分）：

state 7 

    4 Expr: Id . 
    6 Pattern: Id . 

    '='  reduce using rule 6 (Pattern) 
    ')'  reduce using rule 4 (Expr) 
    ')'  [reduce using rule 6 (Pattern)] 
    $default reduce using rule 4 (Expr)

衝突是明確的;在語法讀取x（並將其減少到Id）和)之後，它不知道是將表達式減少爲Expr還是將其作爲Pattern。這提出了一個問題。

我想你應該重寫語法而不Expr之一，Pattern：

%% 
Line: Binding | Expr 
Binding: Expr '=' Expr 
Expr: Id | '(' Expr ')' 
Id: 'x'

來源

2014-09-05 15:10:56

謝謝！這確實解決了衝突，但我應該在問題中注意到，真實語法中的模式和表達是相似的，但不完全相同。 – tokland 2014-09-08 10:12:39

縮小/減少語法

回答

相關問題