Search code examples
compiler-construction

yacc - rules never reduced and shift/reduce conflicts

I have faced a problem dealing with yaac, since I keep getting this note:

1 rule never reduced. 29 shift/reduce conflicts.

So, could anyone help me please to fix this problem?

This is the grammar that I am working on:

%start P
%token DEF IF THEN ELSE WHILE DO FOR
%token Punctuation_element
%token Operator
%token EQL_EQL GREATER_THAN_OR_EQUALS LESS_THAN_OR_EQUALS NOT_EQUALS 
%token<sval> Identifier
%token<ival> Literal

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

%%

P :   D ';' P 
|     D
;

D :  DEF Identifier '(' ARGS ')' '=' E ';'
;

ARGS: Identifier ',' ARGS 
|     Identifier
;

E:    Literal
|     Identifier
|     IF E OP E THEN E ELSE E 
|     FOR E DO E
|     DO E WHILE E
|     E '+' E 
|     E '-' E
|     E '*' E
|     E '/' E
|     E '%' E
|     Identifier '(' E ')'
|     E ',' E
;

/* C:   E ',' C 
|   E  
; */

OP:   EQL_EQL 
|     '>' 
|     '<' 
|     GREATER_THAN_OR_EQUALS 
|     LESS_THAN_OR_EQUALS 
|     NOT_EQUALS 
|     '%'
;
Solution

  • You have two fundamental problems:

    1. % is both a comparison operator (OP) and an arithmetic operator (E '%' E). That creates an ambiguity which bison resolves in favour of the arithmetic operator, because bison favours shift over reduce. That resolution makes it impossible to reduce OP : '%', which is the rule not reduced.

    2. You make , an arithmetic operator (E ',' E) but you don't declare a precedence for it. That leads to a lot of shift reduce conflicts for expressions involving , and another operator. I doubt that you actually want , to be an operator at all; I think you added the production involving it in order to allow function calls with multiple arguments. That's not going to work. Create a separate non-terminal for argument lists and use it in the production for function calls instead of using E.

      (In fact, you have such a non-terminal, mysteriously called C, but it's commented out and unused. So uncomment it and use it. And consider giving it a more meaningful name.)

    LALR parser generators like bison generally prefer left recursion to right recursion. You should consider changing both of your list productions (C and ARGS) to left recursion, unless you have a good reason not to.