为什么 bison 与无歧义语法有 shift/reduce 冲突？

Question

我正在使用 bison，我运行陷入了 shift/reduce 冲突。 Bison 发现了一个 shift/reduce 冲突。我找不到这种语言的歧义：

start
    : IDENT trailer EQUAL atom trailer SEMICOLON
    | atom trailer SEMICOLON
    ;

atom
    : LPAR atom trailer RPAR
    | IDENT
    ;

trailer
    : %empty
    | LPAR RPAR
    ;

这个问题在底部附近的python grammar documentation中也有描述。我可以使用本文档描述的解决方案消除歧义（将第 2 行更改为 atom trialer EQUAL atom trailer SEMICOLON.

现在它已修复，我可以继续前进，但我仍然对这个问题感到好奇。请向我描述上面语法的问题，并用具有两个独特解析树的语言给出例句。

编辑 1
进一步排查，下面有shift/reduce冲突：

start
    : IDENT LPAR RPAR EQUAL atom LPAR RPAR SEMICOLON
    | atom LPAR RPAR SEMICOLON
    ;

atom
    : IDENT
    ;

但这没有 shift/reduce 冲突：

start
    : IDENT LPAR RPAR EQUAL IDENT LPAR RPAR SEMICOLON
    | IDENT LPAR RPAR SEMICOLON
    ;

这对我来说似乎很可疑，因为在第一个语法原子中被迫产生 IDENT，所以这两个本质上是相同的语法。我还需要一些解释。

Answer 1

Shift/reduce 冲突并不一定意味着你的语法有歧义。所有有歧义的语法都会产生 shift/reduce 或 reduce/reduce 冲突，但反之则不一定正确。

在您的情况下，假设解析器已经启动并且刚刚读取了一个 IDENT 令牌，然后是 LPAR。它有两种选择。首先，您可能正在生成起始非终结符的第一个（较长）分支。在这种情况下，您应该根据稍后减少整个长表达式的计划来转移 LPAR。其次，可能是您正在生成起始非终结符的第二个（较短的）分支，这意味着您应该将 IDENT 缩减回原子。仅仅知道下一个终端是 LPAR 并不能帮助您区分这些情况，因此 shift/reduce 冲突。

另一方面，在有更多上下文可用之前，您的语法的第二个版本不需要决定如何处理前面的 IDENT，因此没有冲突。

为什么 bison 与无歧义语法有 shift/reduce 冲突？

Why does bison have shift/reduce conflict with unambiguous grammar?

parsing

bison

context-free-grammar