Вопрос по bison, shift-reduce-conflict – Конфликт между зубрами и сдвигом - невозможно решить

4

Грамматика выглядит следующим образом:

1. program -> declaration-list
2. declaration-list -> declaration-list declaration | declaration
3. declaration -> var-declaration | fun-declaration
4. var-declaration -> type-specifier ID ; | type-specifier ID [ NUM ] ;
5. type-specifier -> int | void
6. fun-declaration -> type-specifier ID ( params ) compound-stmt
7. params -> param-list | void
8. param-list -> param-list , param | param
9. param -> type-specifier ID | type-specifier ID [ ]
10. compound-stmt -> { local-declarations statement-list }
11. local-declarations -> local-declarations var-declarations | empty
12. statement-list -> statement-list statement | empty
13. statement -> expression-stmt | compound-stmt | selection-stmt |
iteration-stmt | return-stmt
14. expression-stmt -> expression ; | ;
15. selection-stmt -> if ( expression ) statement |
if ( expression ) statement else statement
16. iteration-stmt -> while ( expression ) statement
17. return-stmt -> return ; | return expression ;
18. expression -> var = expression | simple-expression
19. var -> ID | ID [ expression ]
20. simple-expression -> additive-expression relop additive-expression |
additive-expression
21. relop -> <= | < | > | >= | == | !=
22. additive-expression -> additive-expression addop term | term
23. addop -> + | -
24. term -> term mulop factor | factor
25. mulop -> * | /
26. factor -> ( expression ) | var | call | NUM
27. call -> ID ( args )
28. args -> arg-list | empty
29. arg-list -> arg-list , expression | expression

Конфликт уменьшения сдвига, который я получаю через бизона -d -v xyz.l, находится в состоянии 97

state 97

   29 selection-stmt: IF LFT_BRKT expression RGT_BRKT statement .
   30               | IF LFT_BRKT expression RGT_BRKT statement . ELSE statement

    ELSE  shift, and go to state 100

    ELSE      [reduce using rule 29 (selection-stmt)]
    $default  reduce using rule 29 (selection-stmt)

Но я не знаю, как решить этот конфликт. В ожидании ответа.

Ваш Ответ

4   ответа
1

fails.

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 правила: если это не такright recursive (не заканчиваетсяstatement) затем добавить толькоnoif_statement (лайкRETURN ';'). Else, for example

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

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

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

И добавьте первый вариант кif_statementс и второй кnoif_statements.

3

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

7

бизон сделал это для вас автоматически (но он все же дает вам знать об этом.)

Раздел5.2 руководства Bison именно об этом конфликте сдвига / уменьшения. Как там говорится, вы можете удалить предупреждающее сообщение, если хотите%expect декларация.

Этот конкретный конфликт сдвига / уменьшения был большой частью мотивации для стратегии разрешения оригиналаyacc parser-generator, как описано в исторической статье о yacc или в книге Dragon, потому что невероятно раздражает устранение конфликта из грамматики. Таким образом, решение этого вопроса - хороший умозаключение, но никогда не должно использоваться на практике. Использование встроенного в Bison устранения неоднозначности гораздо более читабельно и легко поддерживается, и в этом нет никакой неточности или позора.

Если я правильно помню, эта проблема - одно из упражнений в книге Дракона. Основная схема решения выглядит следующим образом:

There would not be an issue if the statement in if (expression) statement could not be an if statement. else cannot begin a statement, so if ( 0 ) break; cannot be reduced with else in the lookahead. The problem is if (0) if (0) break; else Now, it's not obvious whether else should be shifted (and thereby attached to the second if) or if the second if should be reduced, leaving the else to be shifted onto the first if. Normal practice (and yacc's ambiguity resolution algorithm) dictate the first.

So let's distinguish between complete if-statements and incomplete if-statements. Now we can say that an incomplete if-statement (one without an else clause) cannot be immediately followed by else. In other words, a complete if-statement cannot have an incomplete if-statement as its first enclosed statement.

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

conditional            : complete_conditional
                       | incomplete_conditional
                       ;

complete_conditional   : IF ( expression ) statement_other_than_conditional ELSE statement
                       | IF ( expression ) complete_conditional ELSE statement
                       ;

incomplete_conditional : IF ( expression ) statement
                       ;

И теперь нам нужно:

statement              : statement_other_than_conditional
                       | incomplete_conditional
                       | complete_conditional
                       ;
Я не могу получить вашу грамматику. Пожалуйста, объясни. Можете ли вы предоставить грамматику для кода selection-stmt - & gt; оператор if (выражение) | оператор if (выражение) Aakash Anuj
Спасибо за ваш ответ. Но я хочу знать, как изменить грамматику, чтобы устранить конфликт, а не просто игнорировать его. Aakash Anuj
Также скажите мне, как мы узнаем, какое действие выполняет бизон по умолчанию? Вы говорите, что это было принято в пользу смещения остального, но я вижу уменьшение в dafault. Пожалуйста помоги Aakash Anuj
@ user1506031: & quot; Эта ситуация, в которой допустим сдвиг или уменьшение, называется конфликтом сдвиг / уменьшение. Bison предназначен для разрешения этих конфликтов путем выбора смещения, если иное не указано декларациями приоритетов операторов. & Quot; (Со страницы, на которую я ссылался в своем ответе.) Исключенное сокращение заключено в скобки, что указывает на то, что оно было переопределено. (По крайней мере, я совершенно уверен, что именно эти скобки означают.)
0

которая работает (принятый ответ @rici НЕ РАБОТАЕТ, ответ @RaqaouPi относится к Крису Додду) состоит в том, чтобы обрабатывать код как серию if-else / for /, в то время как префиксы сопровождаются, возможно, одиночным зависанием, если или простое утверждение в конце. Этот пример адаптирован изэта грамматика Nearley для 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" _ ";"

Похожие вопросы