Shift/reduce with equal precedence

Question

I have to build a compiler for a subset of C. Obviously since this is my first time doing such thing it's not going very well. However. I'm currently trying to build a lexer and parser for said subset.

I decided to build it up piece by piece and fix errors as they come along. So I have a basic grammar as shown below. This grammar parses correctly and I can do simple math, including the comparison operators. Since thsi is a subset of C, and they return integer values, this is possible.

Now comes the tricky part. I also want (need) to model in ! and - as unary operators, meaning -5 + 5 should equal 0.

Since these two unary operators bind the tightest, I figure I need to put them in the term clause of my grammar. So I changed my term clause to the following:

term        :   NUMBER
            |   NOT term { printf("NOT term\n"); $$ = !$2; }
            |   SUB term { printf("MINUS term\n"); $$ = - ($2);}
            |   LEFTPAR exp RIGHTPAR { printf("expression between parents\n");$$ = $2; }
            |   
            ;

However, this makes bison complain about shift/reduce errors. I know the basics of how to going about fixing these, however, this spawns shift/reduce errors in almost every possible state so I'm a bit confused at the moment.

I could add more precedence in my grammar by chosing - over ! but these are equally tight.

Entire grammar

calclist    : /* nothing */
            | COMMENT { printf("Comment\n"); }
            | calclist comp EOL { printf("= %d\n", $2); } 
            ;

comp        :   exp
            |   comp GREATER exp { printf("comp GREATER factor\n");$$ = $1 > $3; }
            |   comp LESS exp { printf("comp LESS factor\n");$$ = $1 < $3; }
            |   comp EQUAL exp { printf("comp EQUAL factor\n");$$ = $1 == $3; }
            |   comp NEQUAL exp { printf("comp NEQUAL factor\n");$$ = $1 != $3; }
            ;

exp         :   factor
            |   exp ADD factor { printf("exp add factor\n");$$ = $1 + $3; }
            |   exp SUB factor { printf("exp sub factor\n");$$ = $1 - $3; }
            ;

factor      :   term       
            |   factor MUL term { printf("factor mul term\n");$$ = $1 * $3; }
            |   factor DIV term { printf("factor div term\n");$$ = $1 / $3; }
            ;           

term        :   NUMBER
            |   NOT term { printf("NOT term\n"); $$ = !$2; }
            |   SUB term { printf("MINUS term\n"); $$ = - ($2);}
            |   LEFTPAR exp RIGHTPAR { printf("expression between parents\n");$$ = $2; }
            |   
            ;

The output of Bison is the following:

bison -dv bison.y
bison.y: conflicts: 12 shift/reduce
flex lex.l
cc -o calc bison.tab.c lex.yy.c -lfl

I'm not going to paste the entire bison.output file here as this is quite a lenghty file.

Edit:

The grammar pasted below did not contain the SUB token. Added it so it can be copy pasted.

chill chill · Accepted Answer · 2014-02-27T22:24:11

term        :   NUMBER
            |   NOT term { printf("NOT term\n"); $$ = !$2; }
            |   LEFTPAR exp RIGHTPAR { printf("expression between parents\n");$$ = $2; }

The problem is here, the empty production. Just remove it.

            |   
            ;

Shift/reduce with equal precedence

1 Answers