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.

I would appreciate it if down voters would at least give a reason... — Zifre, May 25 '09 at 22:55

score 3 · Accepted Answer · answered Jun 06 '09 at 11:33

3

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

answered Jun 06 '09 at 11:33

tomjen

3,779
3
29
35

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. – Zifre Jun 06 '09 at 13:14
Okay, I just tried this with David Dolson's method, and it works! – Zifre Jun 06 '09 at 15:54
1

-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. – Chris Dodd Sep 08 '13 at 18:25

score 2 · Answer 2 · answered Jan 21 '10 at 12:16

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

answered Jan 21 '10 at 12:16

goresplatter

21
1

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` – Chris Dodd Sep 08 '13 at 18:11
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` – Chris Dodd Sep 08 '13 at 18:34

score 0 · Answer 3 · answered Sep 08 '13 at 18:23

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.

score 0 · Answer 4 · answered May 21 '09 at 15:45

0

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.

answered May 21 '09 at 15:45

David Dolson

300
2
8

1

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. – Zifre May 21 '09 at 20:27

score -1 · Answer 5 · answered Sep 08 '13 at 13:29

-1

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

answered Sep 08 '13 at 13:29

Gourav Saha

43
3
10

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

5 Answers5

Linked