Как исправить конфликты сдвига/сокращения 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

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

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

Answer 4

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

%right INC DEC

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

Answer 5

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