我如何解決降低減少衝突：

以下（簡化）野牛語法產生降低減少衝突：我如何解決降低減少衝突：

expr 
    : '(' expr ')' 
    | ID 
    | fn 
    ; 

arg_list 
    : ID 
    | arg_list ID 
    ; 

fn 
    : '(' ')' fnbody 
    | '(' arg_list ')' fnbody 
    ; 

fnbody 
    : '{' '}' 
    ;

我看到這個問題，只有一個令牌超前的，這是不可能告訴是否(an_id是'(' expr ')'或fn。但我該如何解決它？

來源

2012-05-27 Aaron Yodaiken

好，你怎麼*你*告訴他們分開？ –

fn有多個參數和{}。但我不知道如何在沒有「無限」前瞻的情況下將它們分開。 –

相關：http://stackoverflow.com/questions/10762153/adding-function-literals-while-abstaining-from-backtracking –

那麼，最簡單的答案就是在解析器中使用更多的lookahead - 或者使用類似btyacc的東西，或者使用bison的%glr-parser選項。

第二種選擇是添加先行在詞法分析器 - 返回')'令牌之前在這種情況下，看看是否對下一個標記是'{'，要麼返回一個特殊的標記，告訴你，這是你的arg_list即將結束而不是加括號的表達式，或者只是將兩者作爲單個標記返回並根據需要修改語法。

第三選擇是對語法進行分解。這並不容易，可能會炸燬語法的大小。基本的想法是確定衝突的規則並將它們組合成一個單獨的規則，可以由解析器進行重新規劃，並推遲對最終構造的選擇，直到你看到足夠多的規則。

在這個例子中添加新的規則衝突的情況下：

expr_or_fnhead: '(' ID ')' ;

這可能是表達式或fn的開始，然後修改其他規則來使用它。該fn規則變爲：

fn : '(' ')' fnbody    /* 0 arg function */ 
    | expr_or_fnhead fnbody  /* 1 arg function */ 
    | '(' ID arg_list ')' fnbody /* 2+ arg function */ 
    ;

的expr規則比較複雜：

expr  : ID 
      | non_ID_expr 
      ; 
non_ID_expr: '(' non_ID_expr ')' 
      | expr_or_fnhead 
      | fn 
      ;

來源

2012-05-27 06:23:44

不錯！我很困惑如何解決這個問題，而且你做得很好。我特別喜歡詞法解析器;從某種意義上講，這很冒險，但是很務實。 – Ashe

我如何解決降低減少衝突：

回答

相關問題