Если тогда еще двусмысленность в CUP - PullRequest
Новая
       71

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

0 голосов
/ 30 апреля 2018

Я строю грамматику в 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.

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

1 Ответ

0 голосов
/ 30 апреля 2018

Проблема здесь заключается во взаимодействии операторов 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), вам придется сделать то же самое для каждого из них.

...