Как исправить смещение / уменьшение YACC от оператора постинкрементной обработки?

Question

Я пишу грамматику в 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 ')'
;

%%

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

Answer 1

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

Answer 2

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

%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++--

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

Answer 3

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

%right INC DEC

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

Answer 4

операторы преинкремента и постинкремента имеют nonassoc, поэтому определите, что в разделе приоритетов и в правилах высокий приоритет этих операторов с помощью %prec

Answer 5

Мне нравится определять больше предметов. Вам не нужно использовать% 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
;

Поиграйте с этим подходом.