Сдвиг / уменьшение конфликта в java cup - еще одна проблема

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 с ближайшим непревзойденным if. Matched оператор не может быть расширен с помощью оператора else; Unmatched Заявление могло бы быть. Поэтому мы требуем, чтобы другие грамматики не могли следовать Unmatched заявления, таким образом избегая преждевременного сокращения утверждения, которое могло быть расширено else пункт.

Так что внутри If заявление, остальное может только следовать 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 не может сопровождаться другим. Matched может сопровождаться еще, но в этом случае 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;]

Но на самом деле это не предполагаемый анализ. (Отступ может заставить нас думать, что это было намерение программиста, но это не намерение разработчика языка.) Остальное должно соответствовать второму, если не первому, что приводит к:

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