Как исправить конфликты сдвига / уменьшения YACC от оператора постинкремента?

Я пишу грамматику в YACC (на самом деле Bison), и у меня проблема со сдвигом / уменьшением. Это результат включения постфиксных операторов инкремента и декремента. Вот урезанная версия грамматики:

%token NUMBER ID INC DEC

%left      '+' '-'
%left      '*' '/'
%right     PREINC
%left      POSTINC

%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     INC expr %prec PREINC
|     DEC expr %prec PREINC
|     expr INC %prec POSTINC
|     expr DEC %prec POSTINC
|     '(' expr ')'
;

%%

Bison сообщает мне, что существует 12 конфликтов сдвига / уменьшения, но если я закомментирую строки для увеличения и уменьшения постфикса, он работает нормально. Кто-нибудь знает, как исправить этот конфликт? На этом этапе я подумываю о переходе на генератор синтаксического анализатора LL (k), который значительно упрощает его, но грамматики LALR всегда казались более естественными для написания. Я тоже рассматриваю GLR, но не знаю хороших генераторов синтаксического анализатора C / C ++ GLR.


parsing yacc bison shift-reduce-conflict lalr
person Zifre    schedule 20.05.2009    source источник
comment
Я был бы признателен, если бы подавляющие голоса хотя бы объяснили причину ...   -  person Zifre    schedule 26.05.2009

Ответы (5)


arrow_upward
3
arrow_downward

Bison / Yacc может сгенерировать синтаксический анализатор GLR, если вы укажете %glr-parser в разделе опций.

person tomjen    schedule 06.06.2009
comment
Вау! Я не знал этого ... Я только что попробовал, но у меня все еще возникают конфликты shift-reduce с моей исходной грамматикой. Я предполагаю, что алгоритм GLR Bison плохо взаимодействует с приоритетом, но это может работать в сочетании с ответом Дэвида Долсона. - person Zifre; 06.06.2009
comment
Хорошо, я только что попробовал это с помощью метода Дэвида Долсона, и он работает! - person Zifre; 06.06.2009
comment
-1: Использование режима GLR не является хорошим решением для этого, так как вам все еще нужно как-то разрешить двусмысленность, и, что еще хуже, если вы НЕ исправляете двусмысленность, bison молча примет грамматику без жалоб и выдаст вам ошибки времени выполнения, поэтому легко подумать, что вы устранили проблему, когда вы этого не сделали. - person Chris Dodd; 08.09.2013

arrow_upward
2
arrow_downward

Попробуй это:

%token NUMBER ID INC DEC

%left       '+' '-'
%left       '*' '/'
%nonassoc   '++' '--'
%left       '('
%%

expr: NUMBER
|     ID
|     expr '+' expr
|     expr '-' expr
|     expr '*' expr
|     expr '/' expr
|     '++' expr 
|     '--' expr 
|     expr '++'
|     expr '--'
|     '(' expr ')'
;

%%

Главное - объявить постфиксные операторы неассоциативными. В противном случае вы могли бы

++var++--

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

person goresplatter    schedule 21.01.2010
comment
Фактически, поскольку для нормального поведения C вы хотите, чтобы ++var++ анализировался как ++(var++) и не отклонялся как ошибка (постфикс имеет более высокий приоритет, чем префикс), вам нужно %right, а не %nonassoc - person Chris Dodd; 08.09.2013
comment
Кроме того, приоритет для '(' не имеет смысла, поскольку здесь нет конфликтов, связанных с ним. Он понадобится вам, если возникнут конфликты (например, если вы добавили вызов функции в стиле C или синтаксис приведения), но в этом случае вы, вероятно, захотите %right, а не %left - person Chris Dodd; 08.09.2013

arrow_upward
0
arrow_downward

Мне нравится определять больше предметов. Вам не нужны элементы% left,% right,% prec.

simple_expr: NUMBER
 | INC simple_expr
 | DEC simple_expr
 | '(' expr ')'
;

term: simple_expr
 | term '*' simple_expr
 | term '/' simple_expr
;

expr: term
 | expr '+' term
 | expr '-' term
;

Поэкспериментируйте с этим подходом.

person David Dolson    schedule 21.05.2009
comment
Я пробовал этот подход раньше, и он мне не нравится. Когда у вас есть гораздо более сложные грамматики выражений (например, для C ++), становится трудно понять, что именно вам нужно делать, если вы хотите изменить это. Использование приоритета намного чище, ИМО. - person Zifre; 22.05.2009

arrow_upward
0
arrow_downward

Эта основная проблема заключается в том, что у вас нет приоритета для токенов INC и DEC, поэтому он не знает, как разрешать неоднозначности, связанные с опережением INC или DEC. Если вы добавите

%right INC DEC

в конце списка приоритетов (вы хотите, чтобы унарные имели более высокий приоритет, а постфикс - выше префикса), он исправит это, и вы даже можете избавиться от всего _6 _ / _ 7_, поскольку это не имеет значения.

person Chris Dodd    schedule 08.09.2013

arrow_upward
-1
arrow_downward

Операторы preincrement и postincrement имеют nonassoc, поэтому определите, что в разделе приоритета и в правилах приоритет этих операторов должен быть высоким, используя %prec

person Gourav Saha    schedule 08.09.2013