Lemon正确处理非关联优先级吗?

Question

我感觉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

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

Answer 1

花了一些时间仔细研究了Lemon和Bison为关联语法生成的报告后，我只能得出结论，Lemon确实错误地处理了非关联优先级。确凿的证据包含在上面引用的状态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 EQ项，预计后面会有另一个expr。因此，它包含expr的First集合，即状态中以*开头的3个条目。如果我们在这种状态下读取expr，我们将在状态4中着陆，在缩减的中途或最后有一个项目。

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

如果我们在这种状态下读取EQ会发生什么?我把答案告诉了柠檬。这是一个错误，因为EQ是非结合律。相反，它会报告shift/reduce冲突。在实践中，它会移动，这将使它接受非法解析，如x=y=z。

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

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，则使用它来消除假定的歧义。