Реформирование грамматики для удаления сдвига уменьшает конфликт в if-then-else

Ответ 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
;