移位/减少与嵌套列表的冲突

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的理念是，严重的冲突不应该是 容忍，所以你不应该在乎他们如何解决。