1

在使用 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没有代码重复的情况下编写我想要的东西（这可能会导致其他问题）？这是我应该完全避免的设计模式吗？

4

1 回答 1

2

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

你不需要一个列表来产生这个冲突。替换A*为A?会产生完全相同的冲突。

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

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

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 编码员。

于 2019-07-24T05:50:34.573 回答