改变语法以消除移位减少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将查看关联性.在这里,你想要促进权利相关性(更确切地说,你想促进"转变"),所以:

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

就足够了.

Answer 2

你需要认识到statementif-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...

任何其他stmt -> whatever规则,其中whatever不以结束stmt去的stmt-not-ending-with-if规则,而任何stmt这并最终在规则stmt有两个版本GET分; 一个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;没有.