无法解决以下 reduce-reduce 错误（LALR 解析）

Question

我目前正在实现 Decaf（编程语言）语法的一部分。这是 bison 代码的相关片段：

type:
  INT
  | ID
  | type LS RS
  ;

local_var_decl:
  type ID SEMICOLON
  ;

name:
  THIS
  | ID
  | name DOT ID
  | name LS expression RS
  ;

然而，一旦我开始研究 name 生产规则，我的解析器就会给出 reduce-reduce 警告。

这是 .output 文件（由 bison 生成）中的内容：

State 84

   23 type: ID .
   61 name: ID .

    ID        reduce using rule 23 (type)
    LS        reduce using rule 23 (type)
    LS        [reduce using rule 61 (name)]
    $default  reduce using rule 61 (name)

因此，如果我们给出以下输入 { abc[1] = abc; }，它表示 syntax error, unexpected NUMBER, expected RS。 NUMBER 来自 expression 规则（基本上，它必须如何解析它），尽管它试图通过 [ 解析它=47=]规则。

您认为应该改变什么来解决这个问题？花了大约 2 个小时，尝试了不同的东西，但没有用。

谢谢！！

PS。这是 link 到完整的 .y 源代码

Answer 1

这是一个常见问题的具体实例，解析器在获得足够信息之前被迫做出决定。在某些情况下，例如这个，所需的信息并不遥远，如果可能的话，增加前瞻性就足够了。（不幸的是，很少有解析器生成器生成 k > 1 的 LR(k) 解析器，bison 也不例外。）通常的解决方案是简单地让解析继续进行，而不必做出决定。 bison 的另一种解决方案（但仅在 C 模式下）是要求 %glr-parser，这对于何时需要以额外的处理时间为代价解决缩减问题更加灵活。

在这种情况下，上下文允许 type 或 name，两者都可以以 ID 开头，后跟 [（LS).在 name 的情况下，[ 后面必须跟一个数字；在 type 的情况下，[ 必须后跟 ]。所以如果我们能看到 ID 之后的第二个标记，我们就可以立即决定。

但是我们只能看到前面的一个标记，就是]。并且语法坚持我们能够立即做出决定，因为在一种情况下我们必须将 ID 减少到 name，而在另一种情况下，我们必须减少到 type。所以我们有一个归约-归约冲突，野牛总是使用语法文件中最先出现的归约来解决这个冲突。

一个解决方案是避免以重复制作为代价来强迫这个选择。例如：

type_other:
  INT
  | ID LS RS
  | type_other LS RS
  ;
type: ID
  | type_other
  ;

name_other:
  THIS
  | ID LS expression RS
  | name_other DOT ID
  | name_other LS expression RS
  ;
name: ID
  | name_other
  ;

无法解决以下 reduce-reduce 错误（LALR 解析）

Cannot resolve the following reduce-reduce error (LALR parses)

parsing

yacc

lalr

bison

bisonc++