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

它包含一个典型的移位-归约冲突，并且您通过指定优先级来解决该冲突。请打开任何有关 Yacc 解析的书籍并检查移位归约冲突及其解决方案。

\n\n

让我们使用您的规则来看看它。假设我们有以下输入，并且解析器正在向前查看第二个输入,：

\n\n

( p1 , p2 , ...\n          \xe2\x86\x91\n         Yacc is looking at this second COMMA token\n

\n\n

他们有两种可能性：

\n\n

\n
• 减少：p1 , p2作为pattern. 它使用了第二条规则pattern
\n
• Shift：消耗标记COMMA并将前瞻光标向右移动以尝试使逗号分隔的列表更长。
\n

\n\n

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

\n\n

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

\n\n

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

\n\n

如果您不喜欢减少班次冲突警告（这就是精神！），您可以使用优先级明确说明在这种情况下应选择哪个规则，就像 OCaml 所做的那样parser.mly。（顺便说一句，OCaml 是parser.mly移位减少分辨率的宝石盒。如果您不熟悉，您应该检查其中的一两个。）

\n\n

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

\n\n

所以现在的问题是：哪个优先级更高，COMMA还是below_COMMA？这应该在文件的序言中声明mly。（这就是为什么我要求提问者展示该部分。）

\n\n

...\n%left COMMA\n...\n%nonassoc below_COMMA\n

\n\n

我跳过了“what”%left和%nonassoc“mean”，因为所有 Yacc 书籍都应该解释它们。这里的below_COMMA伪令牌如下 COMMA。这意味着below_COMMA具有比更高的COMMA优先级。因此，上面的例子选择了Reduce，违背了( (p1, p2), ...初衷。

\n\n

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

\n\n

...\n%nonassoc below_COMMA\n%left COMMA\n...\n

\n\n

请参阅 OCaml 的parser.mly。确实是这样的。把“上面的东西放在下面”听起来很疯狂，但这不是门希尔的错。这是Yacc 不幸的传统。怪它。OCaml 已经parser.mly有评论：

\n\n

The precedences must be listed from low to high.\n

\n