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

Question

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.

Leban

I would appreciate it if down voters would at least give a reason... – Leban

Answer 1

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

Sonorous

Wow! I didn't know that... I just tried it out, but I still get shift-reduce conflicts with my original grammar. I'm guessing that Bison's GLR algorithm doesn't cooperate with precedence well, but this might work in combination with David Dolson's answer. – Leban

Okay, I just tried this with David Dolson's method, and it works! – Leban

-1: Using GLR mode is not a good solution for this, as you still need to resolve the ambiguity somehow, and, what's worse, if you DON'T fix the ambiguity, bison will silently accept the grammar without complaint, and give you runtime errors instead, so it's easy to think you've fixed the problem when you haven't. – Lei

Answer 2

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

Ludewig

Actually, since for normal C behavior you want ++var++ to parse as ++(var++) and not be rejected as an error (postfix is higher precedence that prefix), you want %right not %nonassoc – Lei

Also, the precedence for '(' is meaningless as there are no conflicts involving it here. You would need it if there were conflicts (eg, if you added C-style function call or cast syntax), but in that case you likely want %right not %left – Lei

Answer 3

I like to define more items. You shouldn't need the %left, %right, %prec stuff.

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
;

Play around with this approach.

Standpipe

I've tried that approach before, and I don't like it. When you have much more complex expression grammars (like for C++), it becomes hard to understand exactly what you have to do if you want to modify it. Using precedence is much cleaner, IMO. – Leban

Answer 4

This basic problem is that you don't have a precedence for the INC and DEC tokens, so it doesn't know how to resolve ambiguities involving a lookahead of INC or DEC. If you add

%right INC DEC

at the end of the precedence list (you want unaries to be higher precedence and postfix higher than prefix), it will fix it, and you can even get rid of all the PREINC/POSTINC stuff, as it's irrelevant.

Lei

Answer 5

preincrement and postincrement operators have nonassoc so define that in the precedence section and in the rules make the precedence of these operators high by using %prec

Coadjutress