Если тогда еще двусмысленность в CUP

Question

Я создаю грамматику в CUP, и я столкнулся с препятствиями при определении операторов IF-THEN-ELSE.

Мой код выглядел так:

start with statements;

/* Top level statements */
statements ::= statement | statement SEPARATOR statements ;
statement  ::= if_statement | block | while_statement | declaration | assignment ;
block        ::= START_BLOCK statements END_BLOCK ;

/* Control statements */
if_statement    ::= IF    expression THEN statement
                  | IF    expression THEN statement ELSE statement ;
while_statement ::= WHILE expression THEN statement ;

Но инструмент CUP жаловался на неоднозначность в определении if_statement,

Я нашел эту статью, описывающую, как устранить двусмысленность, не представляя endif жетоны.

Поэтому я попытался адаптировать их решение:

start with statements;

statements ::= statement | statement SEPARATOR statements ;

statement  ::= IF expression THEN statement
             | IF expression THEN then_statement ELSE statement 
             | non_if_statement ;

then_statement ::= IF expression THEN then_statement ELSE then_statement
                 | non_if_statement ; 

// The statement vs then_statement is for disambiguation purposes
// Solution taken from http://goldparser.org/doc/grammars/example-if-then-else.htm

non_if_statement ::= START_BLOCK statements END_BLOCK  // code block
                   | WHILE expression statement        // while statement
                   | declaration | assignment ;

К сожалению, CUP жалуется на следующее:

Warning : *** Reduce/Reduce conflict found in state #57
  between statement ::= non_if_statement (*) 
  and     then_statement ::= non_if_statement (*) 
  under symbols: {ELSE}
  Resolved in favor of the first production. 

Почему это не работает? Как мне это исправить?

Answer 1

Проблема здесь заключается во взаимодействии if заявления и while заявления, которые вы можете увидеть, если вы удалите while выписка из non-if-statement,

Проблема в том, что цель while заявление может быть if заявление, и что while Заявление может быть в then пункт о другом if заявление:

IF expression THEN WHILE expression IF expression THEN statement ELSE ...

Теперь у нас есть немного другое проявление исходной проблемы: else в конце может быть частью вложенного if или внешний if,

Решение состоит в том, чтобы расширить различие между утверждениями с ограничениями ("тогда-заявления" в терминах вашей ссылки), чтобы также включить два различных вида while заявления:

statement  ::= IF expression THEN statement
             | IF expression THEN then_statement ELSE statement 
             | WHILE expression statement
             | non_if_statement ;

then_statement ::= IF expression THEN then_statement ELSE then_statement
                 | WHILE expression then_statement
                 | non_if_statement ; 

non_if_statement ::= START_BLOCK statements END_BLOCK
                   | declaration | assignment ;

Конечно, если вы расширяете свою грамматику, чтобы включить другие типы составных операторов (таких как for петли), вам придется сделать то же самое для каждого из них.