Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to fix YACC shift/reduce conflicts from post-increment operator?

I'm writing a grammar in YACC (actually Bison), and I'm having a shift/reduce problem. It results from including the postfix increment and decrement operators. Here is a trimmed down version of the grammar:

%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 tells me there are 12 shift/reduce conflicts, but if I comment out the lines for the postfix increment and decrement, it works fine. Does anyone know how to fix this conflict? At this point, I'm considering moving to an LL(k) parser generator, which makes it much easier, but LALR grammars have always seemed much more natural to write. I'm also considering GLR, but I don't know of any good C/C++ GLR parser generators.

like image 956
Zifre Avatar asked May 20 '09 20:05

Zifre


2 Answers

Bison/Yacc can generate a GLR parser if you specify %glr-parser in the option section.

like image 135
tomjen Avatar answered Sep 21 '22 06:09

tomjen


Try this:

%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 ')'
;

%%

The key is to declare postfix operators as non associative. Otherwise you would be able to

++var++--

The parenthesis also need to be given a precedence to minimize shift/reduce warnings

like image 27
goresplatter Avatar answered Sep 20 '22 06:09

goresplatter