这段 YACC 代码如何造成 shift/reduce 冲突？（非常简单）

Question

我真的试图理解为什么这会造成冲突，但我想我遗漏了什么。

%token D
%start a

%%

a
    : b
    | a '+' b
    ;

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

c
    : D
    ;

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

非常感谢

Answer 1

让我们按如下方式标记您的备选方案：

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

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

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

所以这就是您遇到冲突的原因。正如已经指出的那样，解决方案是使 ++ 成为单个标记。这还有一个好处，即 ++ 内不再允许有空格，这更符合现有语言的语法。

这段 YACC 代码如何造成 shift/reduce 冲突？（非常简单）

How this YACC code makes a shift/reduce conflict?(very simple)

yacc