How do I find reduce/shift conflicts in my yacc code?

Question

I'm writing a flex/yacc program that should read some tokens and easy grammar using cygwin. I'm guessing something is wrong with my BNF grammar, but I can't seem to locate the problem. Below is some code

%start statement_list

%%
statement_list: statement
           |statement_list statement
           ;

statement: condition|simple|loop|call_func|decl_array|decl_constant|decl_var;

call_func: IDENTIFIER'('ID_LIST')' {printf("callfunc\n");} ;

ID_LIST: IDENTIFIER
       |ID_LIST','IDENTIFIER
       ; 


simple:   IDENTIFIER'['NUMBER']' ASSIGN expr
      |PRINT STRING
      |PRINTLN STRING
      |RETURN expr
      ;

bool_expr: expr E_EQUAL expr
      |expr NOT_EQUAL expr
      |expr SMALLER expr
      |expr E_SMALLER expr
      |expr E_LARGER expr
      |expr LARGER expr
      |expr E_EQUAL bool
      |expr NOT_EQUAL bool
      ;

expr: expr ADD expr {$$ = $1+$3;}
| expr MULT expr {$$ = $1-$3;}
| expr MINUS expr {$$ = $1*$3;}
| expr DIVIDE expr {if($3 == 0) yyerror("divide by zero");
                 else $$ = $1 / $3;}
|expr ASSIGN expr
| NUMBER
| IDENTIFIER    
;

bool: TRUE 
 |FALSE 
 ;

decl_constant: LET IDENTIFIER ASSIGN expr 
          |LET IDENTIFIER COLON "bool" ASSIGN bool 
          |LET IDENTIFIER COLON "Int" ASSIGN NUMBER 
          |LET IDENTIFIER COLON "String" ASSIGN STRING 
          ;

decl_var: VAR IDENTIFIER 
|VAR IDENTIFIER ASSIGN NUMBER 
|VAR IDENTIFIER ASSIGN STRING 
|VAR IDENTIFIER ASSIGN bool 
|VAR IDENTIFIER COLON "Bool" ASSIGN bool 
|VAR IDENTIFIER COLON "Int" ASSIGN NUMBER 
|VAR IDENTIFIER COLON "String" ASSIGN STRING 
;

decl_array: VAR IDENTIFIER COLON "Int" '[' NUMBER ']'
  |VAR IDENTIFIER COLON "Bool" '[' NUMBER ']'
  |VAR IDENTIFIER COLON "String" '[' NUMBER ']'
  ;

condition: IF '(' bool_expr ')' statement ELSE statement;

loop: WHILE '(' bool_expr ')' statement;

I've tried changing statement into

statement:';';

,reading a simple token to test if it works, but it seems like my code refuses to enter that part of the grammar.

Also when I compile it, it tells me there are 18 shift/reduce conflicts. Should I try to locate and solve all of them ?

EDIT: I have edited my code using Chris Dodd's answer, trying to solve each conflict by looking at the output file. The last few conflicts seem to be located in the below code.

expr: expr ADD expr {$$ = $1+$3;}
| expr MULT expr {$$ = $1-$3;}
| expr MINUS expr {$$ = $1*$3;}
| expr DIVIDE expr {if($3 == 0) yyerror("divide by zero");
                 else $$ = $1 / $3;}
|expr ASSIGN expr
| NUMBER
| IDENTIFIER    
;

And here is part of the output file telling me what's wrong.

state 60

28 expr: expr . ADD expr
29     | expr . MULT expr
30     | expr . MINUS expr
31     | expr . DIVIDE expr
32     | expr . ASSIGN expr
32     | expr ASSIGN expr .

ASSIGN  shift, and go to state 36
ADD     shift, and go to state 37
MINUS   shift, and go to state 38
MULT    shift, and go to state 39
DIVIDE  shift, and go to state 40

ASSIGN   [reduce using rule 32 (expr)]
ADD      [reduce using rule 32 (expr)]
MINUS    [reduce using rule 32 (expr)]
MULT     [reduce using rule 32 (expr)]
DIVIDE   [reduce using rule 32 (expr)]
$default  reduce using rule 32 (expr)

I don't understand, why would it choose rule 32 when it read ADD, MULT, DIVIDE or other tokens ? What's wrong with this part of my grammar?

Also, even though that above part of the grammar is wrong, shouldn't my compiler be able to read other grammar correctly ? For instance,

 let a = 5

should be readable, yet the program returns syntax error ?

Chris Dodd Chris Dodd · Accepted Answer · 2015-05-25T06:46:32

Your grammar looks reasonable, though it does have ambiguities in expressions, most of which could be solved by precedence. You should definitely look at ALL the conflicts reported and understand why they occur, and preferrably change the grammar to get rid of them.

As for your specific issue, if you change it to have statement: ';' ;, it should accept that. You don't show any of your lexing code, so the problem may be there. It may be helpful to compile you parser with -DYYDEBUG=1 to enable the debugging code generated by yacc/bison, and set the global variable yydebug to 1 before calling yyparse, which will dump a trace of everything the parser is doing to stderr.

How do I find reduce/shift conflicts in my yacc code?

1 Answers