yacc - 这个 YACC 代码是如何产生 shift/reduce 冲突的？（很简单）

Question

我真的试图理解为什么这会产生冲突，但我认为我遗漏了一些东西。

%token D
%start a

%%

a
    : b
    | a '+' b
    ;

b
    : c
    | c '+' '+'
    ;

c
    : D
    ;

我发现相同的“+”字符造成了问题，但我在这段代码中找不到任何歧义......

我真的很感激

标签： yacc

Answer 1

让我们按如下方式标记您的替代方案：

a
    : b          // a1
    | a '+' b    // a2
    ;

b
    : c          // b1
    | c '+' '+'  // b2
    ;

现在，如果解析器刚刚解析了 ac并且下一个标记是 a '+'，则有两种可能性：+可以是 的一部分c '+' '+'，在这种情况下b2应该选择，或者+可以是 的一部分a '+' b，在这种情况下b1应该选择并且a2将被选择下一个。但是，如果没有看到第二个，解析器无法知道是哪一个，+而 YACC 作为LALR(1)解析器生成器，只能向前看一个令牌，而不是两个。

所以这就是为什么你会发生冲突。正如已经指出的，解决这个问题的方法是制作++一个令牌。这还有一个好处，即在 中不再允许使用空格++，这更接近于现有语言的语法。