为什么这个简单的语法会有移位/减少冲突? [英] Why does this simple grammar have a shift/reduce conflict?

问题描述

%token <token> PLUS MINUS INT
%left PLUS MINUS

此工作

exp : exp PLUS exp;
exp : exp MINUS exp;
exp : INT;

这有2个SHIFT/REDUCE冲突:

exp : exp binaryop exp;
exp : INT;
binaryop: PLUS | MINUS ;

为什么?

推荐答案

这是因为第二个实际上是模棱两可的.第一个语法也是，但是您通过添加%left解决了歧义.

This is because the second is in fact ambiguous. So is the first grammar, but you resolved the ambiguity by adding %left.

此%left在第二个语法中不起作用，因为关联性和优先级不是从规则继承的. IE.即使binaryop非终结符产生PLUS和MINUS，它也不会继承任何东西.关联性和优越性被局部化为规则，并以终端符号为中心.

This %left does not work in the second grammar, because associativity and precedence are not inherited from rule to rule. I.e. the binaryop nonterminal does not inherit any such thing even though it produces PLUS and MINUS. Associativity and predecence are localized to a rule, and revolve around terminal symbols.

我们不能执行%left binaryop，但是我们可以稍微重构语法:

We cannot do %left binaryop, but we can slightly refactor the grammar:

exp : exp binaryop term
exp : term;
term : INT;
binaryop: PLUS | MINUS ;

现在不存在冲突，因为它是隐式左关联的. IE.越来越长的表达式只能在binaryop的左侧发生，因为右侧是term，仅产生INT.

That has no conflicts now because it is implicitly left-associative. I.e. the production of a longer and longer expression can only happen on the left side of the binaryop, because the right side is a term which produces only an INT.

这篇关于为什么这个简单的语法会有移位/减少冲突?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！