Реформирование грамматики для удаления сдвига уменьшает конфликт в if-then-else
Как удалить конфликт сдвига смены для бизона для данной грамматики?
selection-stmt -> if ( expression ) statement |
if ( expression ) statement else statement
Было бы высоко оценено решение, дающее модифицированную грамматику.
Ответы
Ответ 1
Существует гораздо более простое решение. Если вы знаете, как работают парсеры LR, то вы знаете, что конфликт происходит здесь:
if ( expression ) statement * else statement
где звезда отмечает текущую позицию курсора. Вопрос, на который должен ответить парсер, - "должен ли я сменить или уменьшить". Обычно вы хотите привязать else
к ближайшему if
, что означает, что вы хотите сдвинуть токен else
. Сокращение теперь означало бы, что вы хотите, чтобы else
ожидал привязки к "старшему" if
.
Теперь вы хотите "рассказать" вашему генератору синтаксиса, что "когда возникает конфликт сдвига/уменьшения между токеном "else"
и правилом" stm → if (exp) stm ", то токен должен побеждать". Для этого "дайте имя" приоритету вашего правила (например, "then"
) и укажите, что "then"
имеет меньшее приоритет, чем "else"
. Что-то вроде:
// Precedences go increasing, so "then" < "else".
%nonassoc "then"
%nonassoc "else"
%%
stm: "if" "(" exp ")" stm %prec "then"
| "if" "(" exp ")" stm "else" stm
с использованием синтаксиса Bison.
На самом деле, мой любимый ответ - даже дать "then"
и "else"
одинаковый приоритет. Когда приоритеты равны, чтобы разбить связь между токеном, который хочет быть сдвинутым, и правилом, которое хочет быть уменьшенным, Bison/Yacc будет рассматривать ассоциативность. Здесь вы хотите повысить право-ассоциативность, так сказать (точнее, вы хотите продвигать "сдвиг" ), поэтому:
%right "then" "else" // Same precedence, but "shift" wins.
будет достаточно.
Ответ 2
Вам нужно признать тот факт, что средний statement
в случае if-else не может быть (или заканчиваться) зависанием if (if, если нет.) Самый простой способ сделать это - разделить stmt
в два:
stmt -> stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if ->
if ( expression ) stmt-not-ending-with-dangling-if else stmt-not-ending-with-dangling-if |
...other statements not ending with dangling if...
stmt-ending-with-dangling-if ->
if ( expression ) stmt |
if ( expression ) stmt-not-ending-with-dangling-if else stmt-ending-with-dangling-if |
...other statements ending with dangling if...
Любое другое правило stmt -> whatever
, где whatever
не заканчивается символом stmt
, идет в правиле stmt-not-ending-with-if
, тогда как любое правило stmt
, которое заканчивается на stmt
, делится на две версии; версии not-ending-with-if
в правиле not-ending-with-if
и версии dangling-if
в правиле dangling-if
.
изменить
Более полная грамматика с другими постановками:
stmt : stmt-ending-with-dangling-if | stmt-not-ending-with-dangling-if
stmt-not-ending-with-dangling-if :
IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-not-ending-with-dangling-if |
WHILE '(' expr ')' stmt-not-ending-with-dangling-if |
DO stmt WHILE '(' expr ')' ';' |
expr ';' |
'{' stmt-list '}'
stmt-ending-with-dangling-if:
IF '(' expr ')' stmt |
IF '(' expr ')' stmt-not-ending-with-dangling-if ELSE stmt-ending-with-dangling-if |
WHILE '(' expr ')' stmt-ending-with-dangling-if
Такие правила, как WHILE (expr) stmt
, разделяются на две части (поскольку они заканчиваются на stmt
), тогда как правила, такие как expr;
, не работают.
Ответ 3
make, если еще более высокий уровень, чем обычные, например:
statements:
statements lineEnd statement
| statements lineEnd IfStat
| statements lineEnd IfElseStat
| IfStat
| IfElseStat
;
IfStat:
if ( statement )
;
IfElse:
IfStat else statement
;