Конфликт сдвига-уменьшения Bison - невозможно разрешить

Вы хотели бы разрешить конфликт в пользу смещения «другого». К счастью, bison сделал это за вас автоматически (но все равно дает вам знать об этом).

Раздел 5.2 руководства Bison посвящен именно этому сдвиг/уменьшение конфликта. Как там сказано, вы можете удалить предупреждающее сообщение, если хотите, с помощью объявления %expect. В качестве альтернативы вы можете явно объявить предпочтение сдвигу разрешения else, используя объявления приоритета bison/yacc: присвойте токену else более высокий приоритет, чем продукции if без предложения else. (Возможно, вы захотите использовать что-то вроде %prec IF в самих постановках, потому что по умолчанию постановка имеет приоритет своего последнего терминала, который в данном случае будет правой скобкой.)

Этот специфический конфликт сдвига/уменьшения был значительной частью мотивации стратегии разрешения исходного генератора синтаксического анализатора yacc, как описано в исторической статье о yacc или в книге Dragon, потому что устранение конфликта из грамматика. Решение этого вопроса — хорошая головоломка, но на практике обычно проще и удобнее использовать объявление приоритета или встроенное устранение двусмысленности Bison.

Эта задача — одно из упражнений в книге «Дракон». Основная схема решения выглядит следующим образом:

1. Не было бы проблемы, если бы statement в if (expression) statement не могло быть выражением if. else не может начинать оператор, поэтому if ( 0 ) break; нельзя сократить с помощью else в упреждающем просмотре. Проблема в том, что if (0) if (0) break; else Теперь не очевидно, следует ли сместить else (и, таким образом, присоединить ко второму if) или следует уменьшить второе if, оставив else для сдвига на первое if. Обычная практика (и алгоритм разрешения неоднозначности yacc) диктует первое.

2. Итак, давайте различать полные операторы if и неполные операторы if. Неполный оператор if — это оператор, который мог бы быть дополнен предложением else, поэтому за ним не может сразу следовать предложение else (поскольку оно включало бы else). Полный оператор не может быть расширен оператором else, поэтому он также не должен заканчиваться неполным оператором.

Итак, мы можем попробовать что-то вроде:

statement              : complete_statement
                       | incomplete_conditional

complete_statement     : complete_conditional
                       | statement_other_than_conditional

complete_conditional   : "if" '(' expression ')' complete_statement "else" complete_statement

incomplete_conditional : "if" '(' expression ')' statement
                       | "if" '(' expression ')' complete_statement "else" incomplete_conditional

Такие языки, как C, имеют другие типы операторов, которые могут заканчиваться вложенными операторами (например, циклические операторы). Все они также должны быть разделены на полные и неполные, в зависимости от полноты завершающего оператора. Вот что делает это решение раздражающим.

Примечание. Приведенная выше грамматика была исправлена ​​из неправильной версии, опубликованной девять лет назад. Несколько ответов относятся к неправильному ответу; к сожалению, никто из них не подумал сигнализировать об ошибке комментарием, который я мог бы увидеть. Прошу прощения, если кто-то использовал неправильный код.

См. мой ответ здесь: Реформирование грамматики для удаления сокращения сдвига конфликт в if-then-else. По моему опыту, вы никогда не должны оставлять «известные конфликты», решайте их. Использование %expect N с N != 0 небезопасно, ИМХО (кроме GLR, конечно).

Я попробовал ответ @rici (принятый ответ), и он не работает.

statement: conditional | statement_other_than_conditional;
conditional: complete_conditional | incomplete_conditional;
complete_conditional: L_IF '(' expression ')' statement_other_than_conditional L_ELSE statement
| L_IF '(' expression ')' complete_conditional L_ELSE statement;
incomplete_conditional: L_IF '(' expression ')' statement;
statement_other_than_conditional: ';';
expression: IDENTIFIER;

$ bison --report=all rrr.y
rrr.y: warning: 2 shift/reduce conflicts [-Wconflicts-sr]

State 14 conflicts: 1 shift/reduce
State 15 conflicts: 1 shift/reduce

State 14

3 conditional: complete_conditional .  [$end, L_ELSE]
6 complete_conditional: L_IF '(' expression ')' complete_conditional . L_ELSE statement

L_ELSE  shift, and go to state 16

L_ELSE    [reduce using rule 3 (conditional)]
$default  reduce using rule 3 (conditional)


State 15

2 statement: statement_other_than_conditional .  [$end, L_ELSE]
5 complete_conditional: L_IF '(' expression ')' statement_other_than_conditional . L_ELSE statement

L_ELSE  shift, and go to state 17

L_ELSE    [reduce using rule 2 (statement)]
$default  reduce using rule 2 (statement)

Ответ Криса Додда (по крайней мере, кажется) хорош. Немного адаптировано:

statement: if_statement | noif_statement;

if_statement:
  IF '(' expression ')' statement
| IF '(' expression ')' noif_statement ELSE if_statement
;

noif_statement:
  IF '(' expression ')' noif_statement ELSE noif_statement
| RETURN ';'
;

expression: IDENTIFIER;

Если у вас есть дополнительные правила оператора: если он не является право-рекурсивным (не заканчивается на statement), добавьте только к noif_statement (например, RETURN ';') . Еще, например

statement: blah '(' blah ')' statement ;

Дублируйте это:

| blah '(' blah ')' if_statement
| blah '(' blah ')' noif_statement

И добавьте первый вариант в if_statement, а второй — в noif_statement.

Другая стратегия, которая работает (принятый ответ @rici НЕ работает, ответ @RaqaouPi кредитует Криса Додда), состоит в том, чтобы рассматривать код как серию префиксов if-else/for/while, за которыми, возможно, следует один оборванный if или простое утверждение в конце. Этот пример адаптирован из этой грамматики Неарли для C- как язык.

Statement         -> StatementPrefix:* (StatementEnd | DanglingIf)
StatementNoDangle -> StatementPrefix:* StatementEnd

StatementPrefix -> "if" _ "(" _ Expression _ ")" _ StatementNoDangle _ "else" _
                 | "while" _ "(" _ Expression _ ")" _

DanglingIf     -> "if" _ "(" _ Expression _ ")" _ Statement
StatementEnd   -> Simple _ ";"
                | "return" (_ Expression):? _ ";"
                | BlockStatement
                | "break" _ ";"
                | "continue" _ ";"