解析前面的列表时出现歧义

Question

在 Menhir 中编写解析器代码时，我不断遇到这种变得非常令人沮丧的设计模式。我正在尝试构建一个接受 "a*ba" 或 "bb" 的解析器。为此，我使用了以下语法（请注意 A* 与 list(A) 相同）：

exp:
 | A*; B; A; {1}
 | B; B; {2}

但是，此代码无法解析字符串 "ba"。 menhir编译器也提示解析器存在shift-reduce冲突，具体如下：

** In state 0, looking ahead at B, shifting is permitted
** because of the following sub-derivation:

. B B 

** In state 0, looking ahead at B, reducing production
** list(A) -> 
** is permitted because of the following sub-derivation:

list(A) B A // lookahead token appears

因此 | B A 需要移位，而 | A* B A 需要在第一个标记为 B 时减少。我可以手动解决这种歧义，并通过将表达式更改为如下所示来获得预期的行为（请注意 A+ 与 nonempty_list(A) 相同）：

exp2:
 | B; A; {1}
 | A+; B; A; {1}
 | B; B; {2}

在我看来，exp和exp2读起来一样，但明显区别对待。有没有一种方法可以编写 exp 来做我想做的事情而不需要代码重复（这会导致其他问题）？这是我应该完全避免的设计模式吗？

Answer 1

exp 和 exp2 解析同一种语言，但它们绝对不是同一种语法。 exp 需要 two-symbol 前瞻才能正确解析以 B 开头的句子，这正是您提到的原因：解析器无法决定是否插入空的 A* 在它看到符号之后 B 之前进入解析，但它需要在它可以处理 B 之前进行插入。相比之下，exp2 不需要空产生式来在 B A 之前创建一个空的 A 列表，因此不需要决定。

您不需要列表来产生此冲突。将 A* 替换为 A? 会产生完全相同的冲突。

您已经为 LALR(1) 解析器生成器找到了此 shift-reduce 冲突的常用解决方案：一点冗余。但是，正如您所注意到的，该解决方案并不理想。

另一个常见的解决方案（但可能不适用于 menhir）涉及使用终止列表的 right-recursive 定义：

prefix:
    | B;
    | A; prefix; 

exp:
    | prefix; A;  { 1 }
    | B; B;       { 2 }

据我所知，menhir 的标准库不包含终止列表宏，但它很容易编写。它可能看起来像这样：

%public terminated_list(X, Y):
| y = Y;
    { ( [], y ) }
| x = X; xsy = terminated_list(X, Y);
    { ( x :: (fst xsy), (snd xsy) ) }

可能有更惯用的写法；我不假装是 OCAML 编码器。

解析前面的列表时出现歧义

Ambiguity when Parsing Preceding List

parsing

menhir