0

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

type:
  INT
  | ID
  | type LS RS
  ;

local_var_decl:
  type ID SEMICOLON
  ;

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

然而，一旦我开始研究名称生成规则，我的解析器就会发出reduce-reduce警告。

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

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来自表达式规则（基本上，它必须如何解析它），尽管它尝试通过local_var_decl规则解析它。

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

谢谢！！

PS。这是完整.y源代码的链接

4

1 回答 1

1

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

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

但是我们只能看到前面的一个标记，那就是]. 语法坚持我们能够立即做出决定，因为在一种情况下，我们必须将 a 简化ID为 a name，在另一种情况下，简化为 a type。所以我们有一个reduce-reduce冲突，bison通过总是使用语法文件中首先出现的那个reduce来解决这个问题。

一种解决方案是避免强迫这种选择，代价是复制产品。例如：

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
  ;
于 2017-11-04T04:17:09.100 回答