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

Question

我一直在研究“ML中的现代编译器实现”，我将SML转换为OCaml。本书定义了一种名为Tiger的语言，该语言具有let ... in ... end语法，用于在给定表达式的范围内声明类型，变量和函数。此外，应将相同类型的相邻声明组合在一起以允许相互递归。

我试图通过以下语法片段来表示这是Menhir：

%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
      }
    }

有了这个，我得到了一个转移/减少冲突，但是Menhir以我喜欢的方式解决了它。我希望nonempty_list(typec)贪婪，因此相邻的TYPE声明被组合在一起。即，在Menhir解决冲突的情况下，我生成的AST看起来像：

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

我想摆脱这个警告，但我无法像Menhir一样解决冲突。我已经尝试过使用%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 ())))

我也试过明确设定优先权，但是Menhir警告我这是一个无用的宣言。

我敢肯定我在这里缺少一些基本的东西。给出产生列表列表的产品，如何让内部列表变得贪婪？

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_list中不需要dec：

decs: l = list(dec) { l }

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

在这种情况下，您的dec可能不需要返回列表。是的，你的AST将与%inline tydec相同，但它与语言一致。

顺便说一句，从menhir文档：

实际+是非实时的列表（实际）的语法糖

---

编辑：

如果你不想改变你的结构（由于某种原因），你总是可以重写你的规则，例如这两个语法是完全相同的：

1）有班次/减少

%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的哲学是不应容忍严重的冲突，所以你不应该关心如何解决它们。