改革语法以消除移位，减少"如果-然后-否则"的冲突

Question

如何消除给定语法中野牛的shift-reduce冲突？

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

提供修改语法的解决方案将不胜感激。

Answer 1

有一个更简单的解决方案。 如果您知道 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

使用野牛语法。

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

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

实际上，我最喜欢的答案甚至是给"then"和"else"相同的优先级。 当优先级相等时，为了打破想要转移的令牌和想要减少的规则之间的联系，Bison/Yacc 将研究关联性。 在这里，你想促进右结合性，可以这么说(更准确地说，你想促进"转移")，所以：

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

就足够了。

Answer 2

你需要认识到这样一个事实，即 if-else 情况下的中间statement不能(或以)悬空 if (if 没有其他)结尾。 最简单的方法是将stmt规则一分为二：

stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if ->
if ( expression ) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if |
...other statements not ending with dangling if...
stmt-ending-with-dangling-if ->
if ( expression ) stmt |
if ( expression ) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if |
...other statements ending with dangling if...

whatever不以stmt结尾的任何其他stmt -> whatever规则都包含在stmt-not-ending-with-if规则中，而任何以stmt结尾的stmt规则都会拆分为两个版本;not-ending-with-if规则中的not-ending-with-if版本和dangling-if规则中的dangling-if版本。

编辑

与其他作品的更完整的语法：

stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if :
IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if |
WHILE '(' expr ')' stmt-not-ending-with-dangling-if |
DO stmt WHILE '(' expr ')' ';' |
expr ';' |
'{' stmt-list '}'
stmt-ending-with-dangling-if:
IF '(' expr ')' stmt |
IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if |
WHILE '(' expr ')' stmt-ending-with-dangling-if

像WHILE (expr) stmt这样的规则被一分为二(因为它们以stmt结尾)，而像expr;这样的规则则不会。

Answer 3

如果其他语句比普通语句更高，例如：

statements:
statements lineEnd statement
| statements lineEnd IfStat
| statements lineEnd IfElseStat
| IfStat
| IfElseStat
;
IfStat:
if ( statement )
;
IfElse:
IfStat else statement
;