22

How do I remove shift-reduce conflict for bison for the given grammar?

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

A solution giving the modified grammar would be highly appreciated.

4

3 回答 3

44

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

就足够了。

于 2012-10-04T19:29:58.210 回答
7

您需要认识到statementif-else 案例中的中间不能是（或以）悬空 if（没有 else 的 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...

任何其他不以 a 结尾的stmt -> whatever规则都在规则中，而任何以结尾的规则都分为两个版本；规则中的版本和规则中的版本。whateverstmtstmt-not-ending-with-ifstmtstmtnot-ending-with-ifnot-ending-with-ifdangling-ifdangling-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;这样的规则则不会。

于 2012-10-04T17:17:57.903 回答
-1

使 if else 比普通语句更高级别，例如：

statements:
  statements lineEnd statement
| statements lineEnd IfStat
| statements lineEnd IfElseStat
| IfStat
| IfElseStat
;
IfStat:
  if ( statement )
;
IfElse:
  IfStat else statement
;
于 2016-03-25T09:19:44.543 回答