Bison - shift/reduce conflict identifier

Question

I have 1 shift/reduce conflict at state 19. I think that there may be a problem with the different occurrences of 'identifier' but I'm struggling to understand the bison report and resolve the conflict. Below is my grammar followed by the bison report with state information:

%{
    #include <cstdio>
    #include <iostream>
    using namespace std;

    extern "C" int yylex();
    extern "C" int yyparse();
    void yyerror(const char *s);
%}

%union{
    int int_val;
    double d_val;
    char *strng;
}

%token TLINEC TBLOCKC TPRINT
%token TASSIGN TCPA TOB TCB TCOMMA TSEMIC
%token TIF TELSE TFOR
%token TINT TFLOAT TD TCHAR
%token TPLUS TMINUS TDIV TMULT
%token TLT TGT TAND TOR TEQUAL TNE
%token<int_val> TINTEGER
%token<d_val> TDOUBLE
%token<strng> TID
%token TOPA

%start program

%%

program : command_list

command_list : declaration
    | command_list declaration

declaration : function_dec
| variable_dec
    | expression

variable_dec : type identifier TSEMIC
| type assignment TSEMIC

assignment : identifier TASSIGN expression

var_list : expression
    | var_list TCOMMA expression
    |

function_dec : type identifier TOPA p_list TCPA scope

p_list : variable_dec
    | p_list TCOMMA variable_dec

type : TINT
    | TD
    | TFLOAT
    | TCHAR


/* inside function scope */

scope : TOB command_list TCB
| TOB TCB


function_call : identifier TOPA var_list TCPA TSEMIC

/* expression rules */

expression : assignment
    | function_call
    | TOPA expression TCPA
    | constant arithmetic_op expression
    | constant logical_op expression
    | constant


constant : identifier
    | num

identifier : TID

num : TINTEGER
| TDOUBLE

arithmetic_op : TPLUS | TMINUS | TDIV | TMULT

logical_op : TLT | TGT | TAND | TOR | TEQUAL | TNE

%%

int main(int, char**){
    int y=0;
    do{
        y=yyparse();
    }while(y);
}

void yyerror(const char *s){
    cout << "parse error! Message: " << s << endl;
    exit(-1);
}

Bison Report:

State 19 conflicts: 1 shift/reduce


Grammar

    0 $accept: program $end

    1 program: command_list

    2 command_list: declaration
    3             | command_list declaration

    4 declaration: function_dec
    5            | variable_dec
    6            | expression

    7 variable_dec: type identifier TSEMIC
    8             | type assignment TSEMIC

    9 assignment: identifier TASSIGN expression

   10 var_list: expression
   11         | var_list TCOMMA expression
   12         | /* empty */

   13 function_dec: type identifier TOPA p_list TCPA scope

   14 p_list: variable_dec
   15       | p_list TCOMMA variable_dec

   16 type: TINT
   17     | TD
   18     | TFLOAT
   19     | TCHAR

   20 scope: TOB command_list TCB
   21      | TOB TCB

   22 function_call: identifier TOPA var_list TCPA TSEMIC

   23 expression: assignment
   24           | function_call
   25           | TOPA expression TCPA
   26           | constant arithmetic_op expression
   27           | constant logical_op expression
   28           | constant

   29 constant: identifier
   30         | num

   31 identifier: TID

   32 num: TINTEGER
   33    | TDOUBLE

   34 arithmetic_op: TPLUS
   35              | TMINUS
   36              | TDIV
   37              | TMULT

   38 logical_op: TLT
   39           | TGT
   40           | TAND
   41           | TOR
   42           | TEQUAL
   43           | TNE


Terminals, with rules where they appear

$end (0) 0
error (256)
TLINEC (258)
TBLOCKC (259)
TPRINT (260)
TASSIGN (261) 9
TCPA (262) 13 22 25
TOB (263) 20 21
TCB (264) 20 21
TCOMMA (265) 11 15
TSEMIC (266) 7 8 22
TIF (267)
TELSE (268)
TFOR (269)
TINT (270) 16
TFLOAT (271) 18
TD (272) 17
TCHAR (273) 19
TPLUS (274) 34
TMINUS (275) 35
TDIV (276) 36
TMULT (277) 37
TLT (278) 38
TGT (279) 39
TAND (280) 40
TOR (281) 41
TEQUAL (282) 42
TNE (283) 43
TINTEGER (284) 32
TDOUBLE (285) 33
TID (286) 31
TOPA (287) 13 22 25


Nonterminals, with rules where they appear

$accept (33)
    on left: 0
program (34)
    on left: 1, on right: 0
command_list (35)
    on left: 2 3, on right: 1 3 20
declaration (36)
    on left: 4 5 6, on right: 2 3
variable_dec (37)
    on left: 7 8, on right: 5 14 15
assignment (38)
    on left: 9, on right: 8 23
var_list (39)
    on left: 10 11 12, on right: 11 22
function_dec (40)
    on left: 13, on right: 4
p_list (41)
    on left: 14 15, on right: 13 15
type (42)
    on left: 16 17 18 19, on right: 7 8 13
scope (43)
    on left: 20 21, on right: 13
function_call (44)
    on left: 22, on right: 24
expression (45)
    on left: 23 24 25 26 27 28, on right: 6 9 10 11 25 26 27
constant (46)
    on left: 29 30, on right: 26 27 28
identifier (47)
    on left: 31, on right: 7 9 13 22 29
num (48)
    on left: 32 33, on right: 30
arithmetic_op (49)
    on left: 34 35 36 37, on right: 26
logical_op (50)
    on left: 38 39 40 41 42 43, on right: 27



state 18

   26 expression: constant . arithmetic_op expression
   27           | constant . logical_op expression
   28           | constant .  [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TINTEGER, TDOUBLE, TID, TOPA]
   34 arithmetic_op: . TPLUS
   35              | . TMINUS
   36              | . TDIV
   37              | . TMULT
   38 logical_op: . TLT
   39           | . TGT
   40           | . TAND
   41           | . TOR
   42           | . TEQUAL
   43           | . TNE

    TPLUS   shift, and go to state 26
    TMINUS  shift, and go to state 27
    TDIV    shift, and go to state 28
    TMULT   shift, and go to state 29
    TLT     shift, and go to state 30
    TGT     shift, and go to state 31
    TAND    shift, and go to state 32
    TOR     shift, and go to state 33
    TEQUAL  shift, and go to state 34
    TNE     shift, and go to state 35

    $default  reduce using rule 28 (expression)

    arithmetic_op  go to state 36
    logical_op     go to state 37


state 19

    9 assignment: identifier . TASSIGN expression
   22 function_call: identifier . TOPA var_list TCPA TSEMIC
   29 constant: identifier .  [$end, TCPA, TCB, TCOMMA, TSEMIC, TINT, TFLOAT, TD, TCHAR, TPLUS, TMINUS, TDIV, TMULT, TLT, TGT, TAND, TOR, TEQUAL, TNE, TINTEGER, TDOUBLE, TID, TOPA]

    TASSIGN  shift, and go to state 38
    TOPA     shift, and go to state 39

    TOPA      [reduce using rule 29 (constant)]
    $default  reduce using rule 29 (constant)


state 20

   30 constant: num .

    $default  reduce using rule 30 (constant)

rici rici · Accepted Answer · 2015-03-17T17:25:10

According to the output of bison, from state 19 it is possible to reduce expression on a lookahead of (. How can this be possible? In other words, under what circumstances can expression be followed by an open parenthesis?

A search through the grammar reveals only three uses of TOPA. Two of them (function declarations and function calls) follow identifier and identifier cannot derive expression, so it must be the third one:

expression: TOPA expression TCPA;

However, the only way that a reduction of expression could occur immediately before this instance of ( is if it were possible for two expressions to occur consecutively. Normally, in C-like languages that possibility is eliminated by requiring a ; to separate statements (which might be, start with, or end with expression), and I suppose that was your intention.

However, we see that:

command_list: declaration
            | command_list declaration

declaration: expression

which allows two consecutive expressions without intervening semicolon.

As always, I encourage the use of more readable tokens in a bison grammar. '(' is much easier to understand than TOPA, and I honestly have no idea what COB might be. But it's a question of style.

Bison - shift/reduce conflict identifier

1 Answers