OCaml + Menhir : How to parse OCaml like tuple-pattern?

Question

我是menhir的初学者。
我想知道如何在我自己的语言中像元组模式一样解析 OCaml，这与 OCaml 非常相似。

例如，在表达式 let a,b,c = ... 中，a, b, c 应该像 Tuple (Var "a", Var "b", Var "c") 一样被解析。

但是，在解析器的以下定义中，上面的示例被解析为 Tuple (Tuple (Var "a", Var "b"), Var "c") 。
我想知道如何修复以下定义来解析像 ocaml 这样的模式。

我已经检查了 OCaml 的 parser.mly，但我不确定如何实现。
我认为我的定义类似于 OCaml 的定义...
他们用的是什么魔法？

%token LPAREN
%token RPAREN
%token EOF
%token COMMA
%left COMMA
%token <string> LIDENT
%token UNDERBAR
%nonassoc below_COMMA

%start <Token.token> toplevel
%%

toplevel:
| p = pattern EOF { p }

pattern:
| p = simple_pattern        { p }
| psec = pattern_tuple %prec below_COMMA
  { Ppat_tuple (List.rev psec) }

simple_pattern:
| UNDERBAR                  { Ppat_any }
| LPAREN RPAREN             { Ppat_unit }
| v = lident                { Ppat_var v }
| LPAREN p = pattern RPAREN { p }

pattern_tuple:
| seq = pattern_tuple; COMMA; p = pattern { p :: seq }
| p1 = pattern; COMMA; p2 = pattern { [p2; p1] }

lident:
| l = LIDENT { Pident l }

结果如下:

[~/ocaml/error] menhir --interpret --interpret-show-cst ./parser.mly
File "./parser.mly", line 27, characters 2-42:
Warning: production pattern_tuple -> pattern_tuple COMMA pattern is never reduced.
Warning: in total, 1 productions are never reduced.
LIDENT COMMA LIDENT COMMA LIDENT
ACCEPT
[toplevel:
  [pattern:
    [pattern_tuple:
      [pattern:
        [pattern_tuple:
          [pattern: [simple_pattern: [lident: LIDENT]]]
          COMMA
          [pattern: [simple_pattern: [lident: LIDENT]]]
        ]
      ]
      COMMA
      [pattern: [simple_pattern: [lident: LIDENT]]]
    ]
  ]
  EOF
]

Answer 1

它包含一个典型的 shift-reduce 冲突，您通过指定优先级在解决它时犯了一个错误。请打开任何一本关于 Yacc 解析的书，并检查 shift-reduce 冲突及其解决方案。

让我们看看它使用你的规则。假设我们有以下输入并且解析器正在查看第二个 , :

( p1 , p2 , ...
          ↑
         Yacc is looking at this second COMMA token

他们有两种可能:

Reduce:将 p1 , p2 作为 pattern 。它使用 pattern

的第二条规则

Shift:使用标记 COMMA 并将前瞻光标向右移动以尝试使逗号分隔列表更长。

从 %prec below_COMMA 规则中删除 pattern 可以很容易地看到冲突:

$ menhir z.mly   # the %prec thing is removed
...
File "z.mly", line 4, characters 0-9:
Warning: the precedence level assigned to below_COMMA is never useful.
Warning: one state has shift/reduce conflicts.
Warning: one shift/reduce conflict was arbitrarily resolved.

许多 Yacc 文档说在这种情况下 Yacc 更喜欢 shift，并且这种默认设置通常与人类意图相匹配，包括您的情况。因此，解决方案之一就是简单地删除 %prec below_COMMA 并忘记警告。

如果您不喜欢 shift reduce 冲突警告(这就是精神!)，您可以使用优先级明确说明在这种情况下应该选择哪个规则，就像 OCaml 的 parser.mly 一样。 (顺便说一句，OCaml 的 parser.mly 是一个减少移位分辨率的 gem 盒。如果你不熟悉，你应该检查其中的一两个。)

Yacc 在 shift 减少冲突时选择具有更高优先级的规则。对于移位，其优先级是前瞻光标处的标记之一，在本例中为 COMMA。 reduce的优先级可以通过相应规则处的 %prec TOKEN后缀来声明。如果你不指定它，我猜规则的优先级是未定义的，这就是为什么如果你删除 %prec below_COMMA 会警告 shift reduce 冲突。

所以现在的问题是: COMMA 或 below_COMMA 哪个具有更高的优先级？这应该在 mly 文件的序言中声明。 (这就是为什么我要求提问者展示那部分。)

...
%left COMMA
...
%nonassoc below_COMMA

我跳过 %left 和 %nonassoc 的意思，因为所有 Yacc 书籍都应该解释它们。这里 below_COMMA 伪标记是 低于 COMMA 。这意味着 below_COMMA 的 优先级高于 COMMA 。因此，上面的例子选择Reduce，违背意图获取( (p1, p2), ...。

正确的优先级声明正好相反。为了让 Shift 发生， below_COMMA 必须高于 COMMA 的 ，使 低于 优先级:

...
%nonassoc below_COMMA
%left COMMA
...

参见 OCaml 的 parser.mly 。它确实像这样。将“下面的东西放在上面”听起来 完全疯狂 ，但这不是 Menhir 的错。这是 Yacc 不幸的传统。怪它。 OCaml 的 parser.mly 已经有评论:

The precedences must be listed from low to high.