Search code examples
c++bisonbisonc++

Bison: reduce/reduce conflict

I'm writing an SQL compiler in bison and having trouble interpreting the state machine bison's producing. Below are the two states which are each causing 1 reduce/reduce error.

I'm guessing the not_qm is causing these reduce/recude 's in like_cond and in_cond(see code below).

I hope someone can point me in the right direction. Please let me know if there's more info needed.

like_cond  : scalar_exp not_qm LIKE scalar_exp escape_scalar_exp_qm
           ;

in_cond    : row_constructor not_qm IN LPAREN table_exp RPAREN
           | scalar_exp not_qm IN LPAREN scalar_exp_list RPAREN
           ;

not_qm     : /* empty */
           | NOT
           ;

### EDITTED SECTION
row_constructor     : scalar_exp
                    | LPAREN scalar_exp_list RPAREN
                    ;

scalar_exp          : un_op_qm scalar_primary
                    | scalar_exp bin_op scalar_primary
                    ;
###


State 193

 35 like_cond: scalar_exp . not_qm LIKE scalar_exp escape_scalar_exp_qm
 37 in_cond: scalar_exp . not_qm IN LPAREN scalar_exp_list RPAREN
 75 row_constructor: scalar_exp .
 78 scalar_exp: scalar_exp . bin_op scalar_primary

 STAR    shift, and go to state 59
 NOT     shift, and go to state 218
 PLUS    shift, and go to state 60
 MINUS   shift, and go to state 61
 DIV     shift, and go to state 62
 CONCAT  shift, and go to state 63

 NOT       [reduce using rule 75 (row_constructor)]
 LIKE      reduce using rule 148 (not_qm)
 IN        reduce using rule 75 (row_constructor)
 IN        [reduce using rule 148 (not_qm)]
 $default  reduce using rule 75 (row_constructor)

 bin_op  go to state 64
 not_qm  go to state 228

State 211

 35 like_cond: scalar_exp . not_qm LIKE scalar_exp escape_scalar_exp_qm
 37 in_cond: scalar_exp . not_qm IN LPAREN scalar_exp_list RPAREN
 75 row_constructor: scalar_exp .
 78 scalar_exp: scalar_exp . bin_op scalar_primary
 123 scalar_exp_list: scalar_exp . scalar_exp_list_star

 STAR    shift, and go to state 59
 NOT     shift, and go to state 218
 PLUS    shift, and go to state 60
 MINUS   shift, and go to state 61
 DIV     shift, and go to state 62
 CONCAT  shift, and go to state 63
 COMMA   shift, and go to state 109

 RPAREN    reduce using rule 124 (scalar_exp_list_star)
 NOT       [reduce using rule 75 (row_constructor)]
 LIKE      reduce using rule 148 (not_qm)
 IN        reduce using rule 75 (row_constructor)
 IN        [reduce using rule 148 (not_qm)]
 $default  reduce using rule 75 (row_constructor)

 bin_op                go to state 64
 scalar_exp_list_star  go to state 110
 not_qm                go to state 228
Solution

  • The problem is with these 3 rules:

    1)row_constructor not_qm IN LPAREN table_exp RPAREN
2)scalar_exp not_qm IN LPAREN scalar_exp_list RPAREN
3)row_constructor     : scalar_exp

    Look what happens if the last element on the stack is scalar_exp and the next token is IN: it can either reduce an empty string to not_qm so that the stack becomes scalar_exp, not_qm or it can reduce scalar_exp to row_constructor. It happens because bison generates a LALR(1) parser, so it takes a decision based only on the top element of the stack and the next token. That's why it cannot distinguish between 1) and 2) rules at this point, eventhough they are different. So you need to change your grammar in such a way that it becomes LALR(1)-parsable.