Shift/уменьшить конфликт в 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 ; 

именно для обеспечения того, чтобы еще правильно подобран с ближайшим непревзойденной если. Оператор 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 
      | ... 
      ;