Shift/reduce java 杯中的冲突 - 其他悬挂问题

Question

我收到以下错误：

Warning : *** Shift/Reduce conflict found in state #116
between Statement ::= Matched (*) 
and     Unmatched ::= IF LPAREN Condition RPAREN Matched (*) ELSE Unmatched 
and     Matched ::= IF LPAREN Condition RPAREN Matched (*) ELSE Matched 
under symbol ELSE
Resolved in favor of shifting.

现在，我知道悬垂的 else 问题，并且我已经尝试使语法明确：

Statement ::= Matched | Unmatched ;


Matched ::= IF LPAREN Condition RPAREN Matched ELSE Matched
            |
            Others
             ;

Unmatched ::= IF  LPAREN Condition RPAREN Statement 
              | 
              IF  LPAREN Condition RPAREN Matched ELSE Unmatched
              ;

没有优先运算符有什么办法可以解决这个问题，还是语法有其他问题？

Answer 1

题目中的语法没有问题，所以我猜测 shift/reduce 冲突是与另一个产品交互的结果。

将语句拆分为 Matched 和 Unmatched 的想法：

Statement ::= Matched | Unmatched ;

正是为了保证一个else与最近的未匹配if正确匹配。 Matched 语句不能用 else 子句扩展； Unmatched 声明本来可以。所以我们要求语法中的 else 标记不能跟在 Unmatched 语句之后，从而避免过早地减少可能已经用 else 子句扩展的语句。

所以在If语句里面，else只能跟在Matched语句后面。如果语句本身没有 else 子句，或者如果 else 子句本身是 Unmatched，则该语句本身就是 Unmatched。因此，我们有三个作品：

Unmatched_If ::= IF LPAREN Condition RPAREN Statement
               | IF LPAREN Condition RPAREN Matched ELSE Unmatched ;
Matched_If   ::= IF LPAREN Condition RPAREN Matched ELSE Matched ;

但这还不是全部，因为还有其他可能的复合语句。例如，考虑 while 语句。如果语言有这样的结构，语法可能包括这样的东西：

While        ::= WHILE LPAREN Condition RPAREN Statement ; /* Wrong! */

那行不通，因为 while 语句也可以是 Unmatched，与 if...else 语句可以是完全相同的方式：如果内部 Statement 是 Unmatched。

例如，考虑

while (x) if (y) do_x_and_y;

由于上面的 While 生产不正确，将减少如下：

   WHILE LPAREN Condition RPAREN Unmatched_If
-> WHILE LPAREN Condition RPAREN Statement
-> Matched

但这违反了Unmatched后面不能跟else的要求。 Matched 后面可以跟 else，但在这种情况下 Matched 以 Unmatched_If 结尾。因此，我们有 shift/reduce 冲突：

if (w)
  while (x) if (y) do_this;
else do_that;

这可以解析为

IF ( Condition:[w] ) Matched:[while(x)if(y)do_this;] ELSE Statement:[do_that;]

但这实际上并不是预期的解析。（缩进可能会让我们认为这是程序员的意图，但这不是语言设计者的意图。）else 应该匹配第二个 if，不是第一个，导致：

if (w)
  while (x)
    if (y) do_this; else do_that;

所以我们需要区分匹配和不匹配的While语句，而不仅仅是匹配和不匹配的If语句：

Unmatched_While ::= WHILE LPAREN Condition RPAREN Unmatched ;
Matched_While   ::= WHILE LPAREN Condition RPAREN Matched ;

这样，while (x) if (y) do_x_and_y; 将被解析为 Unmatched_While，因此它不再是开始于 IF LPAREN Condition RPAREN Matched ELSE...

的作品的一部分

当然，其他复合语句也需要做同样的事情，比如for语句。

所以最终结果将是这样的：

Matched   ::= Matched_If
            | Matched_While
            | Matched_For
            | ...
            | Simple_Statement
            ;
Unmatched ::= Unmatched_If
            | Unmatched_While
            | Unmatched_For
            | ...
            ;

Shift/reduce java 杯中的冲突 - 其他悬挂问题

Shift/reduce conflict in java cup - dangling else issue

java

compiler-construction

parsing

cup