1

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

%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 版本相比，没有冲突。分配确实应该是非关联的。为了解决这个问题，我宁愿不撒谎。

4

1 回答 1

2

在花了一些时间仔细研究 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 是非关联的。相反，它报告了一个移位/减少冲突。在实践中，它会发生变化，这将让它接受非法解析，例如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，就会使用它来消除假定的歧义。

于 2014-06-07T04:12:34.890 回答