0

我一直在研究“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 一样解决冲突的方法。我试过 using %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 警告我这是一个无用的声明。

我敢肯定我在这里遗漏了一些基本的东西。给出产生列表列表的产品，我怎样才能使内部列表变得贪婪？

4

1 回答 1

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 将与 for 相同%inline tydec，但它与语言一致。

顺便说一句，来自 menhir 文档：

actual+是nonempty_list(actual)的语法糖

编辑：

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

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

于 2017-08-11T23:26:24.553 回答