Bison- shift/reduce conflicts

Question

I know that in Bison code, there are some shift/reduce conflicts to be expected, and the normal C grammar produces one for if/else. However, I've got a grammar that produces 330 other shift/reduce conflicts. Is this a sign of a serious problem with my grammar? Should I spend the time hunting down each conflict and attempt to either resolve or verify it's correctness? I'm using a regular LALR parser.

Edit:

Here's my grammar, I stripped all the actions and other stuff.

%token STRING_LITERAL
%token INTEGER
%token FLOAT
%token CHARACTER
%token PTR_OP INC_OP DEC_OP LEFT_OP RIGHT_OP LE_OP GE_OP EQ_OP NE_OP
%token AND_OP OR_OP MUL_ASSIGN DIV_ASSIGN MOD_ASSIGN ADD_ASSIGN
%token SUB_ASSIGN LEFT_ASSIGN RIGHT_ASSIGN AND_ASSIGN
%token XOR_ASSIGN OR_ASSIGN STATIC CATCH DOUBLE_COLON ELLIPSIS FUNCTION VAR
%token SIZEOF
%token GOTO
%token AUTO  
%token THIS VAR_ASSIGN
%token NAMESPACE 
%token TRY 
%token TYPE
%token DECLTYPE
%token PUBLIC 
%token PRIVATE 
%token PROTECTED 
%token USING
%token THROW
%token FRIEND
%token COMPILETIME
%token RUNTIME

%skeleton "lalr1.cc"
%defines
%parse-param { Wide::LexedFile& l }
%parse-param { Wide::ParsedFile&  p }
%lex-param { Wide::LexedFile& l }
%lex-param { Wide::ParsedFile& p }
%define namespace Wide

%token CASE DEFAULT IF ELSE SWITCH WHILE DO FOR CONTINUE BREAK RETURN
%code requires {
#include <string>
#include <vector>
#define YYDEBUG 1
#include "ParsedFile.h"
}
%code provides {
#include "yylex.h"
}
%start program
%locations

%%

program
    : namespace_scope_definitions;

var 
    : ;//VAR;

type_expression
    : expression
    { $$ = $1; }

variable_assignment
    : VAR_ASSIGN;

name_or_qualified_name
    : IDENTIFIER 
    | name_or_qualified_name '.' IDENTIFIER 

namespace_definition
    : NAMESPACE name_or_qualified_name '{' namespace_scope_definitions '}';

accessibility_definition
    : PUBLIC ':'
    | PRIVATE ':' 
    | PROTECTED ':'
    | FRIEND ':';

using_definition
    : USING IDENTIFIER '=' name_or_qualified_name ';' 
    | USING name_or_qualified_name ';';

type_definition
    : TYPE IDENTIFIER type_literal;

namespace_scope_definition
    : namespace_definition 
    | function_definition 
    | variable_definition 
    | accessibility_definition 
    | using_definition 
    | type_definition ;

namespace_scope_definitions
    : namespace_scope_definition
    | namespace_scope_definitions namespace_scope_definition ;

type_scope_definition
    : static_function_definition
    | static_variable_definition
    | destructor_definition
    | accessibility_definition
    | using_definition
    | constructor_definition 
    | type_definition;

type_scope_definitions
    : type_scope_definition
    | type_scope_definitions type_scope_definition ;

destructor_definition
    : '~' THIS '(' ')' compound_statement;

constructor_definition
    : THIS runtime_arguments statements_or_inits;

statement_or_init
    : ':' IDENTIFIER function_call_expression
    | compound_statement;

statements_or_inits
    : statement_or_init
    | statements_or_inits statement_or_init;

compiletime_arguments
    : runtime_arguments
    | ;

runtime_arguments
    : '(' ')'
    | '(' function_argument_list ')';

return_type_expression
    : PTR_OP type_expression 
    | ;

function_definition
    : name_or_qualified_name runtime_arguments compiletime_arguments return_type_expression compound_statement;

function_argument_definition
    : IDENTIFIER 
    | type_expression IDENTIFIER
    | IDENTIFIER variable_assignment expression
    | type_expression IDENTIFIER variable_assignment expression
    | IDENTIFIER variable_assignment '{' expressions '}'
    | type_expression IDENTIFIER variable_assignment '{' expressions '}';

function_argument_list
    : function_argument_definition 
    | function_argument_list ',' function_argument_definition;

static_function_definition
    : STATIC function_definition
    | function_definition;

static_variable_definition
    : STATIC variable_definition 
    | FRIEND variable_definition
    | STATIC FRIEND variable_definition
    | variable_definition;

variable_definition
    : var IDENTIFIER variable_assignment expression ';'
    | var type_expression IDENTIFIER variable_assignment expression ';'
    | var type_expression IDENTIFIER ';'
    | var type_expression IDENTIFIER function_call_expression ';';

base_class_list
    : ':' type_expression
    | base_class_list ',' type_expression;

type_literal
    : base_class_list '{' type_scope_definitions '}'
    | '{' type_scope_definitions '}';
    | '{' '}';

literal_expression
    : INTEGER
    | FLOAT
    | CHARACTER 
    | STRING_LITERAL
    | AUTO
    | THIS
    | TYPE type_literal;

primary_expression
    : literal_expression
    | IDENTIFIER
    | '(' expression ')';

expression
    : variadic_expression;

variadic_expression
    : assignment_expression 
    | assignment_expression ELLIPSIS ;

assignment_operator
    : '=' 
    | MUL_ASSIGN
    | DIV_ASSIGN 
    | MOD_ASSIGN
    | ADD_ASSIGN
    | SUB_ASSIGN
    | LEFT_ASSIGN
    | RIGHT_ASSIGN
    | AND_ASSIGN
    | XOR_ASSIGN
    | OR_ASSIGN;

assignment_expression
    : logical_or_expression
    | unary_expression assignment_operator assignment_expression;

logical_or_expression
    : logical_and_expression
    | logical_or_expression OR_OP logical_and_expression;

logical_and_expression
    : inclusive_or_expression
    | logical_and_expression AND_OP inclusive_or_expression;

inclusive_or_expression
    : exclusive_or_expression
    | inclusive_or_expression '|' exclusive_or_expression;

exclusive_or_expression
    : and_expression
    | exclusive_or_expression '^' and_expression;

and_expression
    : equality_expression
    | and_expression '&' equality_expression;

equality_expression
    : relational_expression
    | equality_expression EQ_OP relational_expression
    | equality_expression NE_OP relational_expression;

comparison_operator
    : '<'
    | '>'
    | LE_OP 
    | GE_OP;

relational_expression
    : shift_expression
    | relational_expression comparison_operator shift_expression;

shift_operator
    : LEFT_OP
    | RIGHT_OP;

shift_expression
    : additive_expression
    | shift_expression shift_operator additive_expression;

additive_operator
    : '+'
    | '-';

additive_expression
    : multiplicative_expression
    | additive_expression additive_operator multiplicative_expression;

multiplicative_operator
    : '*'
    | '/'
    | '%';

multiplicative_expression
    : unary_expression
    | multiplicative_expression multiplicative_operator unary_expression;

lambda_expression 
    : '[' capture_list ']' function_argument_list compound_statement
    | '[' capture_list ']' compound_statement;
    | '[' ']' function_argument_list compound_statement
    | '[' ']' compound_statement;


default_capture
    : '&' | '=' ;

capture_list
    : default_capture comma_capture_list
    | comma_capture_list;

comma_capture_list
    : variable_capture 
    | comma_capture_list ',' variable_capture;

variable_capture
    : '&' IDENTIFIER
    | '=' IDENTIFIER
    | AND_OP IDENTIFIER;

unary_operator
    : '&'
    | '*'
    | '+'
    | '-'
    | '~'
    | '!'
    | INC_OP
    | DEC_OP ;

unary_expression
    : unary_operator unary_expression
    | SIZEOF '(' expression ')'
    | DECLTYPE '(' expression ')'
    | lambda_expression
    | postfix_expression

postfix_expression
    : primary_expression
    | postfix_expression '[' expression ']'
    | postfix_expression function_call_expression 
    | postfix_expression '.' IDENTIFIER
    | postfix_expression PTR_OP IDENTIFIER
    | postfix_expression INC_OP 
    | postfix_expression DEC_OP 
    | postfix_expression FRIEND; 

expressions
    : expression
    | expressions ',' expression;

function_argument
    : expression
    | IDENTIFIER variable_assignment '{' expressions '}'

    | IDENTIFIER variable_assignment expression;

function_arguments
    : function_argument
    | function_arguments ',' function_argument;

function_call_expression
    : '(' function_arguments ')' 
    | '(' ')';

initializer_statement
    : expression
    | var IDENTIFIER variable_assignment expression
    | var type_expression IDENTIFIER variable_assignment expression;

return_statement
    : RETURN expression ';' 
    | RETURN ';';

try_statement
    : TRY compound_statement catch_statements;

catch_statement
    : CATCH '(' type_expression IDENTIFIER ')' compound_statement;

catch_statements
    : catch_statement 
    | catch_statements catch_statement
    | CATCH '(' ELLIPSIS ')' compound_statement
    | catch_statements CATCH '(' ELLIPSIS ')' compound_statement;

for_statement_initializer
    : initializer_statement ';'
    | ';';

for_statement_condition
    : expression ';'
    | ';';

for_statement_repeat
    : expression
    |;

for_statement
    : FOR '(' for_statement_initializer for_statement_condition for_statement_repeat ')' statement;

while_statement
    : WHILE '(' initializer_statement ')' statement;

do_while_statement
    : DO statement WHILE '(' expression ')';

switch_statement
    : SWITCH '(' initializer_statement ')' '{' case_statements '}';

default_statement
    : DEFAULT ':' statements;

case_statement
    : CASE expression DOUBLE_COLON statements;

case_statements
    : case_statement
    | case_statements case_statement
    | case_statements default_statement;

if_statement
    : IF '(' initializer_statement ')' statement
    | IF '(' initializer_statement ')' statement ELSE statement;

continue_statement
    : CONTINUE ';';

break_statement
    : BREAK ';';

label_statement
    : IDENTIFIER ':';

goto_statement
    : GOTO IDENTIFIER ';';

throw_statement
    : THROW ';'
    | THROW expression ';';

runtime_statement
    : RUNTIME compound_statement;

compiletime_statement
    : COMPILETIME compound_statement;

statement
    : compound_statement 
    | return_statement 
    | try_statement 
    | expression ';' 
    | static_variable_definition
    | for_statement
    | while_statement 
    | do_while_statement
    | switch_statement
    | if_statement
    | continue_statement
    | break_statement
    | goto_statement
    | label_statement
    | using_definition
    | throw_statement
    | compiletime_statement
    | runtime_statement;

statements
    : statement
    | statements statement;

compound_statement
    : '{' '}'
    | '{' statements '}';

I made a little headway. You were right- it was the same conflict over and over. Turns out that I was attempting to remove a keyword from the grammar by commenting out the contents of the rule (the var rule, specifically) so whenever Bison encountered something that used to use it, it didn't know whether or not to reduce the empty rule. Now I only have three shift/reduce... and two reduce/reduce... conflicts.

So I guess my answer to the original question was yes, it is a really bad sign to have 330 shift/reduce conflicts.

It's been a while since I've had to debug these, but usually when you fix one of these you fix a lot (or they are usually of a similar kind). IMO it's at least worth it to try to figure out and understand why they happen. Depending on your application it might just be a matter of defining operator precedence in which case it is easily fixed. — user786653

templatetypedef templatetypedef · Accepted Answer · 2011-08-06T18:45:20

Wthout seeing your grammar file I can't say whether or not this is a problem. If you're getting this many shift/reduce conflicts, it almost certainly means that the grammar as written is ambiguous. However, it's very likely that what's going on here, at least if you're writing a C-like language, is that you haven't specified precedences for arithmetic expressions. Did you assign priorities to all your operators?

BTW, are you having bison create a y.output file containing a human-readable version of the parser states and transitions? If not, I'd strongly suggest doing so, as it's virtually impossible to debug shift/reduce conflicts without that extra info.

It is probably worth fixing these sorts of errors, since with this many conflicts I'm assuming that there is a single problem being replicated multiple times. Alternatively, you could switch to a more general parser like a GLR parser (also supported by bison), but with this many conflicts I'm assuming the issue is ambiguity, which the more powerful parsers can't resolve.

Bison- shift/reduce conflicts

1 Answers