Java杯子中的Shift / Reduce冲突-悬空其他问题

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.

现在，我知道了悬而未决的问题，并且我尝试使语法明确：

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

问题中显示的语法没有错，所以我的猜测是，移位/减少冲突是与另一种产品相互作用的结果。

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

Statement ::= Matched | Unmatched ;

正是为了确保else正确匹配最接近的unmatched if。一个Matched语句不能与其他条款进行扩展;
一种Unmatched说法本来是。因此，我们要求else语法中的标记不能跟随Unmatched语句，从而避免过早地减少可能已被else子句扩展的语句。

因此，在If语句内部，else只能遵循一条Matched语句。语句本身就是Unmatched如果它没有else子句，或者该else子句本身是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。因此，我们有一个转移/减少冲突：

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