移位/減少與嵌套列表的衝突

Question

我一直在努力通過「現代編譯器在ML中的實現」，我將SML轉換爲OCaml。本書定義了一種名爲Tiger的語言，該語言有一個let ... in ... end語法用於爲給定表達式聲明範圍內的類型，變量和函數。此外，相同類型的相鄰聲明應該組合在一起以允許相互遞歸。

我試圖代表這是巨石與下面的文法片段：

%right FUNCTION TYPE 

. 
. 
. 

decs: l = list(dec) { l } 

dec: 
    | l = nonempty_list(tydec) { A.TypeDec l } 
    | v = vardec { v } 
    | l = nonempty_list(fundec) { A.FunctionDec l } 

tydec: 
    | TYPE; name = ID; EQUAL; ty = ty { 
     A.{ 
     type_name = Symbol.symbol name; 
     type_ty = ty; 
     type_pos = Position.make $startpos $endpos 
     } 
    } 

有了這個，我得到一個轉變/減少衝突，但巨石解決它，我想的方式。我想nonempty_list(typec)是貪婪的，所以相鄰的TYPE聲明被分組在一起。即，與巨石解決衝突產生我AST看起來像：

(LetExp 
    (decs 
    ((TypeDec 
     (((type_name (my_type)) (type_ty (NameTy (int)))) 
     ((type_name (my_type2)) (type_ty (NameTy (string)))) 
    )))) 
    (body (SeqExp()))) 

我想擺脫的警告，但我想不出來解決衝突的方式巨石一樣。我試過使用%inline tydec，這確實會使警告消失，但TYPE的移位並未如我所料。相反，優選名單中decs，產生一個看起來像這樣的AST：

(LetExp 
    (decs 
    ((TypeDec 
     (((type_name (my_type)) (type_ty (NameTy (int)))))) 
    (TypeDec 
     (((type_name (my_type2)) (type_ty (NameTy (string))) 
))))) 
    (body (SeqExp()))) 

我也試着明確設置優先級，但巨石警告我說，這是一個無用的聲明。

我確定我在這裏錯過了一些基本的東西。提供產生列表的產品，我如何使內部列表變得貪婪？

Answer 1

據我記得，你不能準確地優先於另一個規則（因爲你可以用與%prec相同的規則生產），也許我錯了，但如果不是，我可以理解爲什麼它是不可能的。這個想法是，如果你在這種情況下，你可能犯了一些邏輯錯誤。我會盡力解釋。

讓我們說我們有一些語言的語法如下：在這種情況下

vardef i = 42 
     j = 24 
typedef all_new_int = int 
     all_new_bool = bool 

這是相當邏輯定義是這樣的：

decs: l = list(dec) { l } 

dec: 
    | l = TYPEDEF nonempty_list(tydec) { A.TypeDec l } 
    | ... 

在這種情況下，因爲typedef我們不要的沒有任何衝突。現在，如果沒有這樣的「分隔符」但簡單地說：

var i = 42 
    var j = 24 
    type all_new_int = int 
    type all_new_bool = bool 

爲什麼試圖重新集結這兩類型的聲明？它不是一個塊（如前面的例子），而是兩個單獨的聲明。所以AST必須與語言保持一致。我知道這是不是你要找的答案，但我想說的是，你不需要在nonempty_listdec：

decs: l = list(dec) { l } 

dec: 
    | l = tydec { [A.TypeDec l] } 
    | v = vardec { v } 
    | l = fundec { [A.FunctionDec l] } 

在這種情況下，也許你dec不需要返回一個列表。是的，您的AST將與%inline tydec相同，但它與語言一致。

順便說一句，從巨石文檔：

實際+是語法糖nonempty_list（實際）

---

編輯：

如果您不想改變你的結構（出於某種原因）你總是可以重寫你的規則，比如這兩語法是完全一樣的：

1）用SHIFT /減少

%token <int> INT 
%token NONE 
%token EOF 

%start <int option list list> main 

%% 

main: l = op_list* EOF { l } 

op_list: 
     l = num+ { l } 
    | NONE { [None] } 

num: i = INT { Some i } 

2）在不換擋/減少

%token <int> INT 
%token NONE 
%token EOF 

%start <int option list list> main 

%% 

main: ll=main2 EOF { ll } 

main2: 
    { [] } 
    | n=num ll=main2 { match ll with 
         | ((Some i)::l)::ll -> ((Some i)::(Some n)::l)::ll 
         | _ -> [Some n]::ll 
        } 
    | NONE ll=main2 { [None]::ll } 

num: i=INT { Some i } 

再次，在這裏，當我看到0 NONE 1 2 NONE 3我想[0; None; 1; 2; None; 3]而不是[[0]; [None]; [1; 2; 3]; [None]; 3]，但如果第二個解決方案更簡單，以供將來使用，那麼確定。我相信你可以用%prec和公司（%left,%right，...）來做到這一點，但無論如何你需要重寫你的規則。當你有衝突時你需要解決它，沒有魔法。

6.3嚴重衝突最終如何解決？未指定如何解決嚴重的衝突。 Menhir嘗試使用 來模擬ocamlyacc的規範，也就是說，爲了解決 轉換/減少衝突而偏向於轉換，並且要解決 減少/減少衝突，有利於文本性地在文法​​規範中出現的文本性的 。但是，這種規格在三方衝突的情況下不一致，即 衝突同時涉及移動操作和幾個減少操作。此外，當語法規範被分割到多個模塊時，文本優先級可以是未定義的 。 Menhir的理念是，嚴重的衝突不應該是 容忍，所以你不應該在乎他們如何解決。