改革语法以删除移位，减少 if-then-else 中的冲突

如何消除给定语法的 bison 的移位归约冲突？

 selection-stmt -> if ( expression ) statement |
                      if ( expression ) statement else statement

提供修改后的语法的解决方案将受到高度赞赏。

有一个更简单的解决方案。如果你知道 LR 解析器是如何工作的，那么你就知道冲突发生在这里：

if ( expression ) statement * else statement

其中星号标记光标的当前位置。解析器必须回答的问题是“我应该移动，还是应该减少”。通常，您想要绑定else到最近的if，这意味着您想要移动else现在令牌。现在减少意味着您想要else等待与“长辈”绑定if.

现在你想“告诉”你的解析器生成器“当令牌之间存在移位/归约冲突时"else"以及规则“stm -> if ( exp ) stm”，则令牌必须获胜”。为此，请为规则的优先级“命名”（例如，"then"），并指定"then"优先级低于"else"。就像是：

// Precedences go increasing, so "then" < "else".
%nonassoc "then"
%nonassoc "else"
%%
stm: "if" "(" exp ")" stm            %prec "then"
   | "if" "(" exp ")" stm "else" stm

使用 Bison 语法。

我对此感到不安%nonassoc在这里，因为它确实这么说"then" and "else"是非结合性的，这在大多数语法中都是如此，但我只是想给它们优先级，而不是结合性。野牛提供%precedence为此：

// Precedences go increasing, so "then" < "else".
%precedence "then"
%precedence "else"
%%
stm: "if" "(" exp ")" stm            %prec "then"
   | "if" "(" exp ")" stm "else" stm

事实上，我最喜欢的答案甚至是给出"then" and "else"相同的优先级。当优先级相等时，为了打破想要移动的标记和想要减少的规则之间的联系，Bison/Yacc 将考虑关联性。在这里，您想要促进右结合性（更准确地说，您想要促进“移位”），所以：

%right "then" "else" // Same precedence, but "shift" wins.

就足够了。

根据野牛手册 (3.8.1)，“但这两种解决方案都不是完美的。”