转移/减少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.

现在,我知道悬挂的其他问题,我尝试使语法明确:

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 ;

正是为了确保a else与最接近的不匹配正确匹配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
            | ...
            ;