Lemon是否正确处理非Lemon优先级？

Question

我觉得Lemon解析器生成器在非Lemon优先级上做错了。我有一个简化的语法，它展示了我所看到的问题。

%nonassoc EQ.
%left PLUS.

stmt ::= expr.

expr ::= expr EQ expr.
expr ::= expr PLUS expr.
expr ::= IDENTIFIER.

生成具有如下冲突的报告：

State 4:
      expr ::= expr * EQ expr
  (1) expr ::= expr EQ expr *
      expr ::= expr * PLUS expr

                        EQ shift  2
                        EQ reduce 1   ** Parsing conflict **
                      PLUS shift  1
                 {default} reduce 1

如果我告诉它equals是左关联的，那么问题就消失了。这就好像nonassoc没有将规则放入优先集。与Bison版本的语法相比，没有冲突。赋值应该是非关联的。为了解决这个问题，我不想对它撒谎。

Answer 1

在花了一些时间研究Lemon和Bison为相关语法生成的报告后，我只能得出结论，Lemon确实错误地处理了nonassoc优先级。确凿证据包含在上面引用的状态4中，但为了清楚起见，我可能应该列出一些更多的细节。

构建expr EQ的状态很简单。您到达状态2，然后：

State 2:
      expr ::= * expr EQ expr
      expr ::= expr EQ * expr
      expr ::= * expr PLUS expr
      expr ::= * IDENTIFIER

                IDENTIFIER shift  5
                      expr shift  4

此状态包含当前的expr项，预计后面将跟随另一个expr EQ项。因此，它包含expr的第一个集合，即状态中以*开头的3个条目。如果我们在这种状态下读取expr，我们将进入状态4，其中一个项要么在缩减过程中进行，要么在结束时结束。

expr ::= expr * EQ expr
expr ::= expr EQ expr *

如果我们在这种状态下读取EQ，会发生什么？我把答案告诉了莱蒙。这是一个错误，因为EQ是非结合性的。相反，它会报告一个shift/reduce冲突。实际上，它会发生变化，这会让它接受非法的解析，比如x=y=z。

野牛包含这些相同的状态，编号不同，但具有明显的区别。

state 8

    2 expr: expr . EQ expr  [$end, PLUS]
    2     | expr EQ expr .  [$end, PLUS]
    3     | expr . PLUS expr

    EQ  error (nonassociative)

    $default  reduce using rule 2 (expr)

    Conflict between rule 2 and token PLUS resolved as reduce (PLUS < EQ).
    Conflict between rule 2 and token EQ resolved as an error (%nonassoc EQ).

Bison知道非关联是什么意思，如果它在表达式中看到第二个EQ，它就会用它来消除假定的歧义。