Bison Shift/Reduce 编程语言语法冲突

Question

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

这是通过运行 bison 和 -v

获得的 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: /* 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
    ;

问题：为什么语法有 shift/reduce 冲突，如何解决？我见过没有冲突的类似风格的解析器，这真的很奇怪。

如果你需要查看完整的复制语法，这里有一个 hastebin https://hasteb.in/zozifopi.shell

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

Answer 1

问题在于，当解析器移动 TIDENT 标记并向前看 TLPAREN 标记时，语法允许两种选择：

将 TIDENT 减少为 ident，或
转移 TLPAREN.

Bison 通常会通过选择换档来解决换档/减少冲突，如果这就是您在这种情况下想要的，那么您可以简单地忽略警告。

然而，在这种特殊情况下，您应该能够通过更改 call 产品的规则来解决冲突：

call:
       ident TLPAREN args TRPAREN
       ;

根据该规则，如果不先将 TIDENT 减少为 ident，就不再可以移动 TLPAREN。

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

Answer 2

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

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

If I find an IDENTIFIER should I reduce it through rule 24 to an ident non terminal or should I shift it as in call rule?

这是因为一旦缩小就不能移动，反之亦然，这确实造成了冲突。

要解决冲突，您需要将该选择移动到与解析器相同的状态，以便它能够根据上下文做出决定。

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

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

或对 call 和 expr 本身使用相同的 ident 非终结符，因此它总是会减少它。

Answer 3

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

如果您对解析器始终将其解释为函数调用感到高兴（这是它的默认行为，因为它更喜欢移位），那么您可以添加几个优先级声明，以便调用的优先级高于缩减：

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

这只是掩盖了歧义，可能会导致令人惊讶的解析。但唯一的其他解决方案是使语言明确。

Bison Shift/Reduce 编程语言语法冲突

Bison Shift/Reduce Conflict for a programming language grammar

c

parsing

yacc

bison

compiler-compiler