4

我是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
]
4

2 回答 2

5

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

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

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

他们有两种可能性：

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

Yacc 在轮班减少冲突时选择优先级更高的规则。对于 shift，它的优先级是前瞻光标处的标记之一，COMMA在这种情况下就是这样。reduce 的优先级可以通过%prec TOKEN相应规则的后缀来声明。如果你不指定它，我猜规则的优先级是未定义的，这就是为什么如果你删除了 shift reduce 冲突会被警告的原因%prec below_COMMA。

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

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

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

正确的优先级声明是相反的。要让 Shift 发生，below_COMMA必须高于of COMMA，以具有较低的优先级：

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

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

The precedences must be listed from low to high.
于 2015-10-29T03:02:40.533 回答
3

这就是我将如何重写它：

%token LPAREN
%token RPAREN
%token EOF
%token 逗号
%token LIDENT
%token 底栏

%开始顶层
%%

顶层：
| p = 模式 EOF { p }

图案：
| p = 简单模式；尾 = 模式元组尾
      { 匹配尾部
        | []->p
        | _ -> Ppat_tuple (p :: 尾)
      }

模式元组尾：
| 逗号; p = 简单模式；seq = pattern_tuple_tail { p :: seq }
| { [] }

简单模式：
| UNDERBAR { Ppat_any }
| LPAREN RPAREN { Ppat_unit }
| v =lident { Ppat_var v }
| LPAREN p = 模式 RPAREN { p }

lident：
| l = LIDENT { Pident l }

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

$ menhir --interpret --interpret-show-cst parser.mly
LIDENT 逗号 LIDENT 逗号 LIDENT
接受
[顶层：
  [图案：
    [simple_pattern：[lident：LIDENT]]
    [pattern_tuple_tail：
      逗号
      [simple_pattern：[lident：LIDENT]]
      [pattern_tuple_tail：
        逗号
        [simple_pattern：[lident：LIDENT]]
        [pattern_tuple_tail:]
      ]
    ]
  ]
  EOF
]
于 2015-10-28T20:20:25.580 回答