How to resolve reduce reduce conflicts in bison?

385 views Asked by At

Firstly, I have already referred to many similar questions here, but unable to resolve the conflicts.

I have this piece in my .y file

.
.
.
obj
    : INT { $$ = objNew($1, INT_T); }
    | FLOAT { $$ = objNew($1, FLOAT_T); }
    | STR { $$ = objNew($1, STR_T); }
    ;

var
    : IDEN { $$ = varLookup($1); }
    ;

atom
    : '(' expression ')' { $$ = $2; }
    ;

index
    : '[' obj ']' { $$ = $2; }
    ;

primary_expr
    : obj { $$ = objExpr($1); }
    | var { $$ = varExpr($1); }
    | atom { $$ = atmExpr($1); }
    | expression index { $$ = idxExpr($1, $2); }
    ;

unary_expr
    : primary_expr { $$ = $1; }
    | '+' unary_expr { $$ = unExpr(UPLUS, $2); }
    | '-' unary_expr { $$ = unExpr(UMINUS, $2); }
    ;

power_expr
    : unary_expr { $$ = $1; }
    | power_expr '^' unary_expr { $$ = biExpr('^', $1, $3); }
    ;

multiplicative_expr
    : power_expr { $$ = $1; }
    | multiplicative_expr '*' power_expr { $$ = biExpr('*', $1, $3); }
    | multiplicative_expr '/' power_expr { $$ = biExpr('/', $1, $3); }
    ;

additive_expr
    : multiplicative_expr { $$ = $1; }
    | additive_expr '+' multiplicative_expr { $$ = biExpr('+', $1, $3); }
    | additive_expr '-' multiplicative_expr { $$ = biExpr('-', $1, $3); }
    ;

relational_expr
    : additive_expr { $$ = $1; }
    | relational_expr '>' additive_expr { $$ = biExpr('>', $1, $3); }
    | relational_expr '<' additive_expr { $$ = biExpr('<', $1, $3); }
    | relational_expr '=' additive_expr { $$ = biExpr('=', $1, $3); }
    ;

referential_expr
    : relational_expr { $$ = $1; }
    | referential_expr IS relational_expr { $$ = biExpr(IS, $1, $3); }
    ;

conjunction_expr
    : referential_expr { $$ = $1; }
    | conjunction_expr AND referential_expr { $$ = biExpr(AND, $1, $3); }
    ;

disjunction_expr
    : conjunction_expr { $$ = $1; }
    | disjunction_expr OR conjunction_expr { $$ = biExpr(OR, $1, $3); }
    ;

conditional_expr
    : disjunction_expr { $$ = $1; }
    | disjunction_expr '?' disjunction_expr ':' conditional_expr { $$ = trExpr('?', $1, $3, $5); }
    ;

sequence
    : conditional_expr { $$ = seqChain(NULL, $1); }
    | sequence ',' conditional_expr { $$ = seqChain($1, $3); }
    ;

assignment_expr
    : sequence { $$ = seqAssign($1, NULL); }
    | sequence ASS assignment_expr { $$ = seqAssign($1, $3); }
    ;

expression
    : assignment_expr { $$ = $1; }
    ;

statement
    : ';' { $$ = NULL; }
    | expression ';' { $$ = exprStmt($1); }
    ;

routine
    : routine statement { $$ = rtnChain($1, $2); }
    | { $$ = NULL; }
    ;

program
    : routine { compile($1); exit(0); }
    ;

.
.
.

This grammer is producing lots of reduce\reduce conflicts. Eg:

State 81

   18 power_expr: unary_expr .
   19           | power_expr '^' unary_expr .

    '+'       reduce using rule 18 (power_expr)
    '+'       [reduce using rule 19 (power_expr)]

I have lots of conflicts exactly similar to this. But I'm failing to understand this.
According to my knowledge, it is saying that, when the production is unary_expr or when it is power_expr '^' unary_expr and then it looks a '+', it is facing a reduce\reduce conflict. But why there is a reduce\reduce conflict? When it has power_expr '^' part, it can use rule 19 (and should use since otherwise production will be power_expr '^' power_expr which is not defined in grammer.) and when does not have power_expr '^' part, it has to use rule 18. Where does the ambiguity arises here, and how to resolve it.

1

There are 1 answers

3
rici On BEST ANSWER

The problem stems from the rule

primary_expr: expression index 

That rule cannot be correct, since it implies that a+b[3] could be parsed by applying the [3] to the expression a+b. But it could also be parsed as though written a+(b[3]). This ambiguity produces the reduce-reduce conflicts.

We know that only the second interpretation is correct, which strongly suggests that the rule should be

primary_expr: primary_expr index 

I believe that change will resolve your conflicts.