1

下面是一个 Bison 语法，它说明了我的问题。我使用的实际语法更复杂。

%glr-parser
%%
s : e | p '=' s;
p : fp | p ',' fp;
fp : 'x';
e : te | e ';' te;
te : fe | te ',' fe;
fe : 'x';

输入的一些示例是：

x
x = x
x,x = x,x
x,x = x;x
x,x,x = x,x;x,x
x = x,x = x;x

我所追求的是，​​'=' 左侧的 x 的解析方式与右侧的不同。但是，可能出现在“=”符号右侧的合法“表达式”集合比左侧的要大（因为“;”）。

Bison 打印消息（输入文件为 test.y）：

test.y: conflicts: 1 reduce/reduce.

一定有办法解决这个问题。在 C 中，您也有类似的情况。下面的程序通过 gcc 没有错误。

int main(void) {
  int x;
  int *px;
  x;
  *px;
  *px = x = 1;
}

在这种情况下，“px”和“x”会根据它们出现在“=”符号的左侧或右侧而得到不同的处理。

4

2 回答 2

2

您正在使用%glr-parser，因此无需“修复”减少/减少冲突。Bison 只是告诉你有一个，这样你就知道你的语法可能是模棱两可的，所以你可能需要使用%dprecor%merge指令添加歧义解决方案。但在你的情况下，语法是没有歧义的，所以你不需要做任何事情。

冲突不是错误，它只是表明您的语法不是 LALR(1)。

于 2013-09-22T08:41:12.470 回答
2

语法中的减少-减少冲突来自上下文：

... = ... x ,

此时，解析器必须决定x是 anfe还是 an fp，并且它无法通过一个符号前瞻来知道。实际上，它无法通过任何有限的前瞻知道，您可以在x ,不遇到 a或输入结尾的情况下重复该点的任意次数，其中任何一个都会揭示答案=。;

这与 C 问题不太一样，可以通过单符号前瞻来解决。但是，C 示例是为什么 SLR(1) 语法不如 LALR(1) 语法强大的经典说明——它在龙书中用于此目的——并且类似的有问题的语法是两者之间差异的一个例子LALR(1) 和 LR(1)；它可以在野牛手册（这里）中找到：

 def: param_spec return_spec ',';

 param_spec: type | name_list ':' type;

 return_spec: type | name ':' type;

 type: "id";
 name: "id";
 name_list: name | name ',' name_list;

（野牛手册解释了如何解决 LALR(1) 语法的这个问题，尽管使用 GLR 语法始终是可能的。）

在不使用 GLR 语法的情况下解决此类冲突的关键是避免强制解析器做出过早的决定。

例如，在语法上区分左值和右值是传统的做法，一些语言继续这样做。但是，C 和 C++ 没有；这在 C++ 中被证明是一个非常强大的特性，因为它允许定义可以充当左值的函数。

在 C 中，我认为这只是为了简化语法：C 语法允许任何一元运算符的结果出现在赋值运算符的左侧，但一元运算符实际上是左值 ( *v, v[expr]) 和右值的混合( sizeof v, f(expr))。语法可以区分这两种一元运算符，但它无法解决实际的限制，即只有可修改的左值可能出现在赋值运算符的左侧。

C++ 允许任意表达式出现在赋值运算符的左侧（尽管有些需要用括号括起来）；因此，以下内容是完全合法的：

(predicate(x) ? *some_pointer : some_variable) = 42;

在您的情况下，您可以通过替换来在语法上解决冲突tewith p，因为两个非终结符都会产生相同的派生集。这可能不是一般的解决方案，除非在您的完整语法中确实存在左侧表达式是右侧表达式的严格子集的情况。在一个完整的语法中，你可能会得到三种类型的表达式（left-only、right-only、common），这可能会使语法变得相当复杂，而将分辨率留给语义分析可能会更容易（甚至，如在 C++ 的情况下，非常有用）。

于 2013-09-22T15:38:39.840 回答