Bison转换/减少编程语言语法的冲突

Question

我正在编写一个编程语言解析器，我陷入了这种Shift / Reduce Conflict。

这是通过使用-v运行bison获得的parser.output文件中的冲突状态

State 1

   24 ident: TIDENT .
   26 call: TIDENT . TLPAREN args TRPAREN

    TLPAREN  shift, and go to state 24

    TLPAREN   [reduce using rule 24 (ident)]
    $default  reduce using rule 24 (ident)

当我试图实现呼叫规则时，冲突正在发生，它似乎与正常的身份规则冲突。

这里是语法的一些部分，（为简单起见删除了操作，但不应该使用它们。我也不确定规则的定义是否重要，如果我错了，请纠正我）

（大写字母是代币）

身份规则很简单

ident: TIDENT
          ;

通过电话使用的Args。

args: /* empty */
        |
        expr
        |
        args TCOMMA expr
        ;

呼叫呼叫功能

call:
       TIDENT TLPAREN args TRPAREN
       ;

Expr用于表达式

expr:
    number
    |
    ternary
    |
    bool
    |
    string
    |
    ident
    |
    call
    |
    TLPAREN expr TRPAREN
    |
    expr TPLUS expr
    |
    expr TMINUS expr
    |
    expr TSLASH expr
    |
    expr TSTAR expr
    |
    expr TGT expr
    |
    expr TGE expr
    | 
    expr TLT expr
    |
    expr TLE expr
    ;

问题：为什么语法有转换/减少冲突，你如何解决它？我见过类似的风格解析器没有真正奇怪的冲突。

如果你需要看到完整的语法再现这里是一个hastebin https://hasteb.in/zozifopi.shell

如果您需要有关其他任何内容的更多详细信息，请在评论中告诉我，我会相应地编辑问题。

Answer 1

这里的根本问题是你的语法是模糊的，因为语句不需要被终止（stmts: stmts stmt），语句可以是一个表达式。因此，两个表达式可以一个接一个地出现而没有任何标点符号。这意味着f(3)可以是一个表达式（函数调用）或两个表达式（f和(3)）。

如果你很高兴解析器总是把它解释为函数调用（这是它的默认行为，因为它更喜欢移位），那么你可以添加几个优先级声明，这样调用的优先级高于减少：

%precedence TIDENT
//...
%precedence TLPAREN
// ...
%%
expr : ident %prec TIDENT

这只是关于歧义的论文，可能会引起令人惊讶的解析。但唯一的其他解决方案是使语言明确无误。

Answer 2

问题是，当解析器移动了TRIDENT令牌并向前看qazxsw poi令牌时，语法允许两种选择：

1. 将TLPAREN减少到TIDENT，或
2. 转移ident。

Bison通常会通过选择转换来解决转移/减少冲突，如果这就是你想要的，那么你可以简单地忽略警告。

但是，在这种特殊情况下，您应该能够通过更改TLPAREN生产的规则来解决冲突：

call

有了这个规则，在没有首先将

call:
       ident TLPAREN args TRPAREN
       ;

减少到TLPAREN的情况下，不再可以选择移动TIDENT。

或者，您可以考虑完全删除ident非终端，而是直接使用ident，无论您现在使用TIDENT。也可能有其他替代方案。最适合您的方法可能取决于您尝试对语义操作执行的操作。我不能对此进行更具体的评论，因为您选择不考虑语义行为。

Answer 3

Bison默认生成一个LR解析器，它是一个自下而上的解析器，可以决定移动令牌还是减少令牌。

冲突非常简单，输出本身很好地解释了（我想知道什么不清楚），它告诉你：

如果我发现ident我应该通过规则24减少到IDENTIFIER非终端或者我应该像ident规则那样移动它吗？

这是因为一旦减少你就不能转移和反之，这确实造成了冲突。

要解决冲突，您需要在解析器的相同状态下移动该选项，以便它能够根据上下文来决定。

由于call只有一个终端ident规则，同样适用于呼叫，你可以轻松地将所有内容移动到同一级别，使其始终移位：

IDENT

或者对

expr: 
  IDENT | 
  IDENT LPAREN args RPAREN |
  ...

和ident本身使用相同的call非终端，因此它将始终减少它。