1

我正在使用 Menhir 创建解析器，并且有一种行为总是让我感到困惑，我不明白。我创建了以下最小示例来演示它；这显示了在 Go 语言（ http://golang.org/ref/spec#Method_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) 解析器生成器，因此可能需要了解其他类似工具的工作原理。）

4

2 回答 2

4

我想 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

（或其他一些可能性，但这足以说明问题。）

在第二种情况下（只是一个类型），我们需要先减少 anoptional_identifier和 anoptional_star才能将IDENTIFIER. 在第一种情况下（一个变量和一个类型），我们需要IDENTIFIER立即移位。我们可以用来区分的唯一信息是前瞻标记IDENTIFIER，这显然是不够的。

如果我们使用四路扩展生产，那么就没有问题了：

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

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

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

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

于 2014-10-04T04:17:43.627 回答
1

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

于 2014-10-03T18:19:45.117 回答