Java杯子中的Shift/Reduce冲突-悬空其他问题 [英] Shift/reduce conflict in java cup - dangling else issue

问题描述

我收到以下错误:

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.

现在，我知道悬而未决的问题，并且我尝试使语法清晰:

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
              ;

没有优先级运算符，是否有任何方法可以解决此问题，或者语法是否还有其他问题?

解决方案

问题中显示的语法没有任何问题，因此我的猜测是，移位/减少冲突是与另一生产交互的结果. /p>

将语句分为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

但是，这违反了不能跟随 else 的要求. Matched后可以跟 else ，但是在这种情况下，Matched以Unmatched_If结尾.因此，我们有一个转移/减少冲突:

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
            | ...
            ;

I am getting the following error:

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.

Now, i am aware of the dangling else problem, and i have tried making the grammar unambiguous:

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
              ;

Is there any way to resolve this problem without the precedence operator, or is there something else wrong with the grammar?

解决方案

There is nothing wrong with the grammar presented in the question, so my guess is that the shift/reduce conflict is the result of an interaction with another production.

The idea of splitting statements into Matched and Unmatched:

Statement ::= Matched | Unmatched ;

is precisely to ensure that an else is correctly matched with the nearest unmatched if. A Matched statement cannot be extended with an else clause; an Unmatched statement could have been. So we require that else tokens in the grammar cannot follow Unmatched statements, thus avoiding prematurely reducing a statement which might have been extended with an else clause.

So inside the If statement, the else can only follow a Matched statement. The statement itself is Unmatched if it doesn't have an else clause, or if the else clause itself is Unmatched. Thus, we have three productions:

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

But this isn't the whole story, because there are other possible compound statements. Consider, for example, a while statement. If the language has such a construct, the grammar probably includes something like this:

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

That won't work, because a while statement can also be Unmatched, in precisely the same way that an if...else statement can be: if the interior Statement is Unmatched.

For example, consider

while (x) if (y) do_x_and_y;

With the incorrect While production above, that would be reduced as follows:

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

But that violates the requirement that Unmatched cannot be followed by else. Matched can be followed by else, but in this case the Matched ends with Unmatched_If. And consequently, we have a shift/reduce conflict:

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

This could be parsed as

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

But that is not actually the intended parse. (The indentation might lead us to think that it was the programmer's intent, but it is not the intent of the language designer.) The else should match the second if, not the first one, leading to:

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

So we need to distinguish between matched and unmatched While statements, not just matched and unmatched If statements:

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

With that, while (x) if (y) do_x_and_y; will be parsed as an Unmatched_While, and so it can no longer be part of the productions which start IF LPAREN Condition RPAREN Matched ELSE...

Of course, the same will need to be done for other compound statements, such as for statements.

So the final result will be something like:

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

这篇关于Java杯子中的Shift/Reduce冲突-悬空其他问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！