1

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

%right '['
%left '+'

%%

rvalue  : '+' lvalue 
    | lvalue
    ;

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

Yacc 表示 1 个减少/减少冲突。这种减少/减少冲突出现在状态 6 中：

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

    .  reduce 1

显然应该选择“reduce 1”作为这种冲突的解决方案，因为“reduce 2”似乎永远不会导致成功的解析。

我该如何解决这个冲突？

出于可移植性的原因，我不愿意使用 bison 或 POSIX.1 2008 中指定之外的任何 yacc 功能。

4

1 回答 1

3

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

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

++ x [ x ]

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

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

请注意，第一个是您想要的解析；下标运算符比前缀增量运算符绑定得更紧密，因此++x[x]可以正确解析为++ (x[x]). 几乎所有语言都以这种方式处理后缀运算符，这符合预期的行为。（绝大多数程序员都希望-x[3]先提取数组的第 3 个元素x，然后将其取反。绑定第一个元素-x根本没有意义。对于++; 如果x是一个数组，++x则与 . 一样没有意义-x。）

这与您应该选择“减少 1”的断言相反；正确的解析要求采用“减少 2”。该错误也反映在您的优先级声明中，从逻辑上讲，它应该以右关联方式将优先级赋予后缀运算符：

%right "++" '['

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

但是进行这种更改是没有意义的，因为优先级声明不能解决减少/减少冲突，因为优先级的解决总是涉及可以减少的生产的优先级与可以转移的前瞻标记的优先级之间的比较。（换句话说，被比较的事物的类型是不同的。）

在状态 6（在问题中重现）中，解析器已经移动了"++"，然后是'x'，然后执行了强制归约'x'to lvalue。所以解析器堆栈是... "++" lvalue，前瞻标记是[. 如果语法没有尝试分离左值和右值（因此堆栈的顶部只是value而不是lvalue），那么解析器可用的选择将是减少"++" value到value，或者转移[到为右侧做准备value '[' value ']'。使用上述优先级声明，由于右关联性，移位会获胜，因此会出现正确的解析。

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

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

如果我们忽略左值/右值的区别，使用这些非终结符编写语法很容易，所以这是一个很好的起点。（注意：我将后递增/递减运算符移入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

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

value   : unary
unary   : primary

结合所需的将左值隐式减少为右值。

我们的第一个想法可能是只拆分非终端，让级联流过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
于 2019-06-12T07:23:13.337 回答