Bison shift-reduce conflict when operators are grouped as a non-terminal

Question

Assuming I have the following rules in my grammar.

expr: expr op expr
    | NUMBER

op: '+' | '-' | '*' | '/'

And I have the following declarations done

%token NUMBER

%left '+' '-'
%right '*' '/'

This causes 4 shift-reduce conflicts at

State 12

    4 expr: expr . op expr
    4     | expr op expr .

    '+'  shift, and go to state 6
    '-'  shift, and go to state 7
    '*'  shift, and go to state 8
    '/'  shift, and go to state 9

    '+'       [reduce using rule 4 (expr)]
    '-'       [reduce using rule 4 (expr)]
    '*'       [reduce using rule 4 (expr)]
    '/'       [reduce using rule 4 (expr)]
    $default  reduce using rule 4 (expr)

    op   go to state 11

However, if I rewrite my grammar as

expr: expr '+' expr
    | expr '-' expr
    | expr '*' expr
    | expr '/' expr
    | NUMBER

the precedence rules kick in and the conflicts are resolved. I believe the conflicts arise because when bison encounters an op, it doesn't keep track of the previous op that was shifted into the stack. Is there a way I could group all the operators and still resolve the conflicts?

possible duplicate of [Yacc/Bison, minimize amount by grouping math ops](http://stackoverflow.com/questions/1410875/yacc-bison-minimize-amount-by-grouping-math-ops) — Brian Tompsett - 汤莱恩, Feb 16 '15 at 21:44

score 1 · Answer 1 · edited May 23 '17 at 10:24

1

Apparently, this has been answered here1.

By grouping operators, one loses precedence information.

edited May 23 '17 at 10:24

Community

1
1

answered Jan 25 '13 at 02:45

borncrusader

263
3
8

Bison shift-reduce conflict when operators are grouped as a non-terminal

1 Answers1