shift/reduce conflict in my bison grammar

Question

I'd don't know how to resolve the shift/reduce conflict with this grammar for instantiating my classes:

%start root_instance

%token IDENTIFIER
%token FUNCTION
%token FUNCTION_CHUNK
%token NOBIND
%token PROPERTY_CHUNK
%token MULTILINE_PROPERTY_CHUNK

%%

id_comma_list:
    id_comma_list IDENTIFIER {
  }
  | id_comma_list ',' IDENTIFIER {
  }
  | %empty { $$ = id_list(); }
;

id_dot_list:
    id_dot_list IDENTIFIER {
  }
  | id_dot_list '.' IDENTIFIER {
  }
  | %empty { $$ = id_list(); }
;

root_instance:
  id_dot_list '{' instance_body '}' {
  }
;

instance:
  id_dot_list '{' instance_body '}' {
  }
;

instance_body:
    instance_body instance {
  }
  | instance_body function {
  }
  | instance_body property {
  }
  | %empty { $$ = node(); }
;

function:
  FUNCTION IDENTIFIER '(' id_comma_list FUNCTION_CHUNK {
  }
;

property:
    IDENTIFIER PROPERTY_CHUNK {
    }
  | IDENTIFIER MULTILINE_PROPERTY_CHUNK {
    }
  | IDENTIFIER NOBIND PROPERTY_CHUNK {
    }
  | IDENTIFIER NOBIND MULTILINE_PROPERTY_CHUNK {
    }
;
%%

The conflict appears in the "instance_body" rule. The parser can't decide whether to shift IDENTIFIER for "property" or reduce for "id_dot_list". I've tried to enable the GLR parser, which probably could parse this grammar, but there's a bug in bison, that causes an error when GLR is enabled. I don't want to introduce any new keywords, for example, "property", which would ease the decision whether to shift or not.

user1095108 user1095108 · Accepted Answer · 2013-12-20T13:57:19

This appears to do it, a shift will be forced when IDENTIFIER appears, fixing the conflict:

%start root_instance

%token IDENTIFIER
%token FUNCTION
%token FUNCTION_CHUNK
%token NOBIND
%token PROPERTY_CHUNK
%token MULTILINE_PROPERTY_CHUNK

%%

id_comma_list:
    id_comma_list IDENTIFIER {
  }
  | id_comma_list ',' IDENTIFIER {
  }
  | %empty { $$ = id_list(); }
;

id_dot_list:
    id_dot_list IDENTIFIER {
    }
  | id_dot_list '.' IDENTIFIER {
    }
  | %empty { $$ = id_list(); }
;

root_instance:
    id_dot_list '{' instance_body '}' {
    }
;

instance_or_property:
    id_dot_list '{' instance_body '}' {
    }
  | property {
    }
;

instance_body:
    instance_body IDENTIFIER instance_or_property {
      $$ = ::std::move($1);
    }
  | instance_body function {
    }
  | %empty { $$ = node(); }
;

function:
  FUNCTION IDENTIFIER '(' id_comma_list FUNCTION_CHUNK {
  }
;

property:
    PROPERTY_CHUNK {
    }
  | MULTILINE_PROPERTY_CHUNK {
    }
  | NOBIND PROPERTY_CHUNK {
    }
  | NOBIND MULTILINE_PROPERTY_CHUNK {
    }
;

shift/reduce conflict in my bison grammar

1 Answers