OCaml + Menhir：如何像元组模式一样解析 OCaml？

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

这就是我重写它的方式：

%token LPAREN
%token RPAREN
%token EOF
%token COMMA
%token  LIDENT
%token UNDERBAR

%start  toplevel
%%

toplevel:
| p = pattern EOF { p }

pattern:
| p = simple_pattern; tail = pattern_tuple_tail
      { match tail with
        | [] -> p
        | _ -> Ppat_tuple (p :: tail)
      }

pattern_tuple_tail:
| COMMA; p = simple_pattern; seq = pattern_tuple_tail { p :: seq }
|                                                     { [] }

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

lident:
| l = LIDENT { Pident l }

一个主要的变化是元组元素不再是 pattern 而是 simple_pattern。 pattern 本身是一个或多个元素的逗号分隔序列。

$ menhir --interpret --interpret-show-cst parser.mly 
LIDENT COMMA LIDENT COMMA LIDENT
ACCEPT
[toplevel:
  [pattern:
    [simple_pattern: [lident: LIDENT]]
    [pattern_tuple_tail:
      COMMA
      [simple_pattern: [lident: LIDENT]]
      [pattern_tuple_tail:
        COMMA
        [simple_pattern: [lident: LIDENT]]
        [pattern_tuple_tail:]
      ]
    ]
  ]
  EOF
]

Answer 2

它包含一个典型的 shift-reduce 冲突，您在解决它时指定的优先级有误。请打开任何有关 Yacc 解析的书籍，并检查有关 shift-reduce 冲突及其解决方案的信息。

让我们用您的规则看看吧。假设我们有以下输入并且解析器正在向前看第二个 ,:

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

他们有两种可能性：

归约：将p1 , p2当成pattern。它使用 pattern
Shift：使用令牌 COMMA 并将前瞻光标向右移动，以尝试使逗号分隔列表更长。

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

$ 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 减少冲突警告（这就是精神！），您可以使用优先级明确说明在这种情况下应该选择哪个规则，就像 OCaml 的 parser.mly 所做的那样。（顺便说一句，OCaml 的 parser.mly 是 shift reduce 分辨率的宝箱。如果你不熟悉，你应该检查其中的一两个。）

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伪token是下方COMMA。这意味着 below_COMMA 比 COMMA 具有 更高的 优先级。因此，上面的例子选择了Reduce，违背了本意( (p1, p2), ...

正确的优先级声明是相反的。要让 Shift 发生，below_COMMA 必须在 COMMA 的之上，以获得 较低的 优先级：

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

参见 OCaml 的 parser.mly。它确实是这样的。放置 "below thing above" 听起来 完全疯狂 ，但这不是 Menhir 的错。这是 Yacc 不幸的传统。怪它。 OCaml 的 parser.mly 已有评论：

The precedences must be listed from low to high.

OCaml + Menhir：如何像元组模式一样解析 OCaml？

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

ocaml

menhir