似乎等价的Menhir规则改变语法中的移位/减少冲突

Question

我用Menhir创建了一个解析器，有一种行为总是让我感到震惊，但我不明白。我创建了下面的最小示例来演示它；这在Go语言(declarations)中的方法声明中显示了接收方参数的声明：

%{

%}

%token <string> T_identifier
%token T_star

%start <unit> demo


%%


(* This rule has a shift/reduce conflict
demo:
| option(T_identifier) option(T_star) T_identifier { () } 
*)

(* This rule is okay. *)
demo:
| T_identifier T_star T_identifier { () }
| T_identifier T_identifier        { () }
| T_star T_identifier              { () }
| T_identifier                     { () }

据我所见，这两条规则在语义上是等价的:我们正在寻找一个可选的标识符(接收者的名称)、一个可选的星号(指针与否)和一个强制类型名称(接收者的类型)。然而，第一个规则(注释掉的规则)提供了一个移位/减少冲突，而第二个规则工作良好。

每当出现这种情况时，我都可以通过用多个规则替换option来改进我的解析器，但一直困扰我的是，我不明白为什么会发生这种情况。

(如果您不知道menhir，它是一个LR(1)解析器生成器，所以可能会应用其他类似工具的工作方式。)

Answer 1

我认为Menhir通过一些标准转换将EBNF缩减为BNF。这很常见。不幸的是，这些转换会破坏LR(1)的可解析性。

考虑一下您的规则，在另一个类似EBNF的语法中：

demo → IDENTIFIER? STAR? IDENTIFIER

将其转化为BNF的一种方法是，正如您在第二组规则中所做的那样:定义四条不同的规则，每种可能性一条。这种转换永远不会改变LR(1)的可解析性，使用“可选”运算符的规则总是有可能的，但它有两个缺点：

1. 如果一个规则中有几个可选元素，那么最终的结果就是产生大量的结果。
2. 它不适用于重复操作符。

另一种似乎更为普遍的方法是为每个扩展的BNF运算符创建一个新的非终端。所以我们可以这样做：

optional_identifier → IDENTIFIER | ε
optional_star       → STAR | ε
demo                → optional_identifier optional_star IDENTIFIER

类似的转换也适用于x*

repeated_x → ε | repeated_x x

这当然会产生一种等价的语言，但现在语法可能不是LR(1)。

特别是，demo不再是LR(1)。一开始就失败了。假设第一个输入令牌是IDENTIFIER。这可能是

IDENTIFIER IDENTIFIER

或

IDENTIFIER

(或者其他一些可能性，但这足以说明问题所在。)

在第二种情况下(只是一种类型)，我们需要减少optional_identifier和optional_star，然后才能转移IDENTIFIER。在第一种情况下(变量和类型)，我们需要立即转移IDENTIFIER。我们唯一可以区分的信息是IDENTIFIER，这显然是不够的。

如果我们采用四位一体的扩大生产，那么就没有问题：

demo → IDENTIFIER
     | STAR IDENTIFIER
     | IDENTIFIER IDENTIFIER
     | IDENTIFIER STAR IDENTIFIER

在这里，当我们看到一个IDENTIFIER时，我们不知道它是第一个生产、第三个生产还是第四个生产的一部分。但这并不重要，因为在所有情况下，我们只是转移IDENTIFIER，等待更多的信息。

类似的现象发生在yacc/bison和其他允许中间规则操作(MRAs)的解析器生成器中。一个MRA被转化为一个新的非终端，其唯一的生产是ε生产；新的非终端的目的是在其减少时运行MRA。这真的很酷，只是有时新的非终端会在我们不知道是否适合减少它的时候引入。因此，MRA可以将一个非常好的LR(1)语法转换为一个非LR(1)语法，即使语言没有改变。

虽然与Menhir的情况无关，但有趣的是，上面的EBNF转换，如果小心的话，不会引入不存在的歧义。因此，即使结果语法不再是LR(1)，它仍然是明确的，可以用GLR解析器进行解析。然而，据我所知，Menhir并没有生成GLR解析器，所以这个事实可能不是很有用。

Answer 2

在第二条规则中，您已经明确地指定了歧义应该按照什么顺序来解决。实际上，您可以通过重新排序子句，以几种不同的方式重写第二条规则。这就是为什么曼希尔抱怨说，他不知道你喜欢什么顺序。