改革语法以消除移位可减少if-then-else中的冲突 [英] Reforming the grammar to remove shift reduce conflict in if-then-else

问题描述

如何针对给定的语法消除针对野牛的移位减少冲突?

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.

推荐答案

有一个简单得多的解决方案.如果您知道LR解析器的工作原理，那么您就会知道冲突发生在这里:

There is a much simpler solution. If you know how LR parsers work, then you know that the conflict happens here:

if ( expression ) statement * else statement

，其中星号标记光标的当前位置.解析器必须回答的问题是我应该转移还是应该减少".通常，您要将else绑定到最接近的if，这意味着您现在想移动else令牌.现在减少意味着您希望else等待绑定到较旧的" if.

where the star marks the current position of the cursor. The question the parser must answer is "should I shift, or should I reduce". Usually, you want to bind the else to the closest if, which means you want to shift the else token now. Reducing now would mean that you want the else to wait to be bound to an "older" if.

现在，您想告诉"解析器生成器当令牌"else"与规则"stm-> if(exp)stm"之间存在移位/减少冲突时，则令牌必须获胜".为此，请赋予名称"规则的优先级(例如"then")，并指定"then"的优先级小于"else".像这样:

Now you want to "tell" your parser generator that "when there is a shift/reduce conflict between the token "else" and the rule "stm -> if ( exp ) stm", then the token must win". To do so, "give a name" to the precedence of your rule (e.g., "then"), and specify that "then" has less precedence than "else". Something like:

// 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将着眼于关联性.在这里，您可以说可以促进右联想(更确切地说，您可以促进转移")，所以:

Actually, my favorite answer is even to give "then" and "else" the same precedence. When the precedences are equal, to break the tie between the token that wants to be shifted, and the rule that wants to be reduced, Bison/Yacc will look at associativity. Here, you want to promote right-associativity so to speak (more exactly, you want to promote "shift"), so:

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

就足够了.

这篇关于改革语法以消除移位可减少if-then-else中的冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！