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

В грамматике, представленной в вопросе, нет ничего плохого, поэтому я предполагаю, что конфликт сдвига/уменьшения является результатом взаимодействия с другим продуктом.

Идея разделения операторов на Matched и Unmatched:

Statement ::= Matched | Unmatched ;

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