Типы конфликтов в Bison

Question

%token<val>num 
%left '+' '-' 

Пример shift/reduce конфликта:

Expr:num {$$=$1}; 
    |Expr '+' Expr;{}; 
    |Expr '-' Expr;{}; 

Я хочу признать reduce/reduce конфликт. Это происходит, когда два или более правила применяются к одной последовательности входного (лексем)

Например:

Prod: proda|prodb 
    proda :'x' 
    prodb : 'x' 

Может кто-нибудь дать некоторые идеи, как распознают reduce/reduce конфликт легко?

Answer 1

Самый простой способ сделать это - создать файл y.output.

Использовать команду yacc -v parser_name.y. Это создаст вам выход, как работает yacc. Найдите состояние, в котором yacc говорит, что ваш конфликт есть, а затем очень важно понять, какой знак точки. в файлах.

Если выходной файл говорит что-то вроде этого:

4 | Expr. '+' Expr; {};

Точка знак после того, как выражение говорит вам:. «Я прочитал Expr и на входе у меня есть„+“

свертка-свертка конфликты появляются, когда у вас есть ситуации, как это:

NON_TERMINAL1: Expr. 
NON_TERMINAL2: Expr. 

В этой ситуации, когда у вас есть Expr. В конце правила Yacc не знает, что уменьшить, а что это уменьшить-уменьшить конфликт.

Answer 2

Ну, вы просто в значительной степени описали разницу между конфликтами. Что за вопрос?

shift/reduce конфликт означает, что зубр не знает, что он должен shift (читать дальше один терминал и поместите его на вершине своего стека) или reduce (конвертировать несколько терминалов/нетерминалы в стеке в новую Непро- Терминал). shift/reduce означает I don't know - should I apply a rule now or wait a bit, read some text and apply another rule there? Такие конфликты обычно разрешаются с помощью операции shift.

reduce/reduce конфликт означает, что существует два или более способов уменьшения терминалов/нетерминалов в верхней части стека. reduce/reduce означает I don't know - should I apply this rule or that rule now?. Этот конфликт гораздо серьезнее, чем shift/reduce - грамматика неоднозначна, и что-то действительно не так.

Обычно это лучше не признать свёртка/свёртка, но избежать его. У вас есть четкое представление о том, что вы хотите сделать с самого начала. Периодически пересматривайте свою грамматику. Есть ли шанс, что вы только что изобрели другое правило?

Когда дело доходит до отладки существующих конфликтов, параметр bison -v создает файл *.output с очень длинными описаниями всех ваших конфликтов. Это очень трудно прочитать в первый раз, и это требует некоторых знаний о том, как проводится LR1 parsing, но плюсы чтения его тоже замечательны.