grammar - 为什么这个简单的语法会有移位/归约冲突？

Question

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

这个有效:

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

这有 2 个转变/减少冲突:

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

为什么？

Answer 1

这是因为第二个实际上是不明确的。第一个语法也是如此，但您通过添加 %left 解决了歧义。

这个%left在第二个语法中不起作用，因为结合性和优先级不是从一个规则继承到另一个规则的。 IE。 binaryop 非终结符不会继承任何这样的东西，即使它产生 PLUS 和 MINUS 。关联性和优先级被本地化为规则，并围绕终结符号。

我们无法执行%left binaryop，但我们可以稍微重构一下语法:

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

现在没有冲突，因为它是隐式左关联的。 IE。越来越长的表达式的产生只能发生在binaryop的左侧，因为右侧是一个term，它只产生一个INT。