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

Question

如何删除给定语法的bison的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

使用Bison语法。

实际上，我最喜欢的答案甚至是让"then"和"else"具有相同的优先级。当优先级相等时，为了打破想要移位的标记和想要减少的规则之间的关系，Bison/Yacc将考虑结合性。在这里，您希望提升右关联性(更准确地说，您希望提升"shift")，因此：

%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版本在<代码>d12规则中。

编辑

一个更完整的语法和其他产品：

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

使if else比正常语句更高级别，例如：

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