В чем конфликт этого парсера yacc?

Question

Я использовал опцию -v в yacc для создания файла y.output. В верхней части файла написано

Состояние 98 конфликтов: 1 смещение / уменьшение

Далее в файле следующее:

state 98

   30 selection_stmt: IF '(' expression ')' statement .
   31               | IF '(' expression ')' statement . ELSE statement

    ELSE  shift, and go to state 101

    ELSE      [reduce using rule 30 (selection_stmt)]
    $default  reduce using rule 30 (selection_stmt)

Что такое конфликт и как его можно исправить?

Answer 1

Почти каждая ошибка сдвига / уменьшения с if/then/else оператором является печально известной висячей еще проблемой.

С этим сегментом кода:

if (f1):
    if (f2):
        c1
    else:
        c2

вы (и Python из-за его причудливых правил отступа) знают, к чему if принадлежит else, но парсер не настолько умен.

Невозможно определить, принадлежит ли else первому или второму if.

Эта ссылка показывает, как преобразовать LR (n) в эквивалент LR (1), который должен решить проблему.

Другая альтернатива - изменить определение базового языка (если это возможно), чтобы устранить неопределенность:

: IF '(' cond ')' THEN statement ENDIF
| IF '(' cond ')' THEN statement ELSE statement ENDIF

Answer 2

Гм, правильный ответ на эту проблему обычно: ничего не делать .

Ожидаются конфликты Shift / Reduce с неоднозначными грамматиками. Это не ошибки , это конфликты .

Конфликт будет разрешен путем предпочтения сдвига, а не уменьшения, что, как правило, решает проблему канонического повисшего остального.

И даже у бизона есть оператор% Ожидается n , поэтому вы не получите предупреждение о конфликте S / R, когда есть точно n конфликтов.

Answer 3

Попробуйте что-то вроде этого:

election_stmt: IF '(' expression ')' statement . selection_stmt_else_part;
selection_stmt_else_part: ELSE statement 
                        | 
                        ;