如何解决这个 reduce/reduce 冲突？

Question

我正在为 B 编程语言编写编译器。这种语言的语法在句法上区分左值和右值。在将语法转换为 yacc 语法时，我偶然发现了 reduce/reduce 冲突。这是一个最小的、完整的和可验证的例子：

%right '['
%left '+'

%%

rvalue  : '+' lvalue 
    | lvalue
    ;

lvalue  : 'x'
    | rvalue '[' rvalue ']'
    ;

Yacc 表示 1 reduce/reduce 冲突。此 reduce/reduce 冲突出现在状态 6:

6: reduce/reduce conflict (reduce 1, reduce 2) on '['
state 6
    rvalue : '+' lvalue .  (1)
    rvalue : lvalue .  (2)

    .  reduce 1

似乎很明显应该选择“reduce 1”作为此冲突的解决方案，因为“reduce 2”似乎永远无法导致成功解析。

我该如何解决这个冲突？

出于可移植性的原因，我不愿意在 POSIX.1 2008.

中指定的功能之外使用 bison 或 yacc 的任何功能

Answer 1

为了阅读此问答的任何人的利益，知道问题中的 + 标记旨在成为 pre-increment 运算符 ++。根据评论，进行更改是为了避免必须引入令牌声明。下面，我冒昧地将 '+' 更改为 Bison 语法 "++"，因为我认为使用预期运算符的正常拼写不会造成混淆。我也确实使用了 Bison 的 quoted-token 扩展，因为它更具可读性。（但删除起来很简单。）

冲突的发生是因为实际上存在一个使用 rvalue: lvalue 产生式的有效解析。具体来说，输入

++ x [ x ]

您的语法可以用两种不同的方式解析：

      rvalue                                      rvalue
  /           \                                      |
"++"        lvalue                                lvalue
        /--------------\                   /------------------\
     rvalue '[' rvalue ']'              rvalue   '['   rvalue   ']'
        |          |                   /      \           |
     lvalue     lvalue               "++"   lvalue     lvalue
        |          |                           |          |
       'x'        'x'                         'x'        'x'

注意第一个是你要的parse；下标运算符比前缀增量运算符绑定得更紧密，因此 ++x[x] 被正确解析为 ++ (x[x])。很好，所有语言都以这种方式处理后缀运算符，这与预期的行为相匹配。（绝大多数程序员会期望 -x[3] 首先提取数组 x 的元素 3，然后取反。首先绑定 -x 根本没有意义。对于++；如果 x 是一个数组，++x 和 -x 一样毫无意义。）

这与您关于应该选择 "reduce 1" 的主张相反；正确的解析需要 "reduce 2" 被采用。该错误也反映在您的优先声明中，逻辑上应该优先 right-associatively 后缀运算符：

%right "++" '['

（从技术上讲，前缀运算符的绑定不如后缀运算符紧密。但由于 right-associativity，它们共享优先级是可以的。）

但是做那个改变没有意义，因为优先级声明不能解决reduce/reduce冲突，因为优先级的解决总是涉及production的优先级之间的比较可以减少，并且可以移动前瞻 token 的优先级。（也就是说，被比较的东西的种类不同。）

In State 6 (reproduced in the question), parser has shifted the "++" and then the 'x', and then performed the forced reduction of 'x' to [=35] =].所以解析器堆栈是 ... "++" lvalue 并且先行标记是 [。如果文法不试图分离左值和右值（这样栈顶只是 value 而不是 lvalue），那么解析器可用的选择将是减少 "++" value 到 value，或移动 [ 为 right-hand 侧 value '[' value ']' 做准备。使用上面的优先级声明，由于 right-associativity，移位将获胜，因此将出现正确的解析。

但是语法试图区分左值和右值，这使得解析器无法转换 [；要使 [ 有效，必须先将 lvalue 减少为 rvalue。然而，优先决定总是立即发生的；解析器并没有真正将 rvalue: lvalue 的缩减视为移动 [ 的前奏。它看到的是两个相互竞争的 reduce 操作，优先级不适用于此类冲突。

由于优先级声明不会帮助解决这个特殊的冲突，因此最简单的方法是避免尝试将它们用于一元运算符，而将它们用于二元运算符。（也可以根本不使用它们，但它们对于表达二进制优先级很方便。） B reference manual [注 1] 清楚地表明叙述文本，而不是包含的语法，才是精确定义的内容运算符优先级和结合性，叙述文本包括两个句法类别，基本表达式和一元表达式，它们没有出现在语法中，但它们是, 事实上，语法上是必要的。

如果我们忽略 lvalue/rvalue 的区别，使用这些 non-terminals 编写语法很容易，所以这是一个很好的起点。（注意：我将 post-increment/decrement 运算符移动到 primary 以避免依赖优先级声明。）

%token NAME CONSTANT
%token INC "++" DEC "--"
%left '+' '-'
%left '*' '/' '%'
%start value
%%
primary : NAME
        | primary '[' value ']'
        | CONSTANT
        | '(' value ')'
        | primary "++"
        | primary "--"
unary   : primary
        | '*' unary 
        | '-' unary
        | '&' unary
        | "++" unary
        | "--" unary
value   : unary
        | value '+' value
        | value '-' value
        | value '*' value
        | value '/' value
        | value '%' value

现在我们可以看到有两个不同的 non-terminals 需要拆分成 l 和 r 变体，因为 primary 和 unary 都可以产生左值。（分别为 x[x] 和 *x。）但是，由于级联，它并不像将这两个 non-terminals 分为两类那么简单：

value   : unary
unary   : primary

结合所需的左值到右值的隐式缩减。

我们的第一个想法可能是拆分 non-terminals，让级联流经 rvalue: lvalue 个作品：

value   : runary
runary  : lunary
        | rprimary
lunary  : lprimary
rprimary: lprimary

不幸的是，这会产生两条不同的路径来到达 lprimary:

value -> runary -> lunary   -> lprimary
value -> runary -> rprimary -> lprimary

由于级联产生式没有关联的动作，并且左值到右值的转换（取消引用操作）对于两个实例都是相同的，实际上选择这些路径中的哪一条对我们没有影响。但是解析器会关心，所以我们必须消除其中一个。这是一种可能的解决方案：

%token NAME CONSTANT
%token INC "++" DEC "--"
%left '+' '-'
%left '*' '/' '%'
%start value
%%
lprimary: NAME
        | primary '[' value ']'
primary : lprimary
        | rprimary
rprimary: CONSTANT
        | '(' value ')'
        | lprimary "++"
        | lprimary "--"
lunary  : lprimary
        | '*' runary
runary  : lunary
        | rprimary 
        | '-' runary
        | '&' runary
        | "++" lunary
        | "--" lunary
value   : runary
        | value '+' value
        | value '-' value
        | value '*' value
        | value '/' value
        | value '%' value

如何解决这个 reduce/reduce 冲突？

How to resolve this reduce/reduce conflict?

parsing

yacc

reduce-reduce-conflict

b-lang