shift/reduce errors BISON -

i 2 shift/reduce errors when trying compile grammar:

program : declaration_list ; declaration_list : declaration_list declaration | declaration ; declaration : var_declaration | fun_declaration ;   var_declaration: type_specifier var_decl_list ; scoped_var_declaration: scoped_type_specifier var_decl_list; var_decl_list : var_decl_list "," var_decl_initialize | var_decl_initialize ; var_decl_initialize : var_decl_id ; var_decl_id : id | id "[" int_num "]" ; scoped_type_specifier : type_specifier; type_specifier: int | char ; fun_declaration: type_specifier id "(" params ")" statement | id "(" params ")" statement ; params : | param_list ; param_list: param_list ";" param_type_list | param_type_list ; param_type_list : type_specifier param_id_list ;  param_id_list : param_id_list "," param_id | param_id ;  param_id : id | id "[" "]" ;   statement: expression_stmt | compound_stmt | selection_stmt | iteration_stmt | return_stmt | break_stmt ;  compound_stmt : "{" local_declaration statement_list "}" ; local_declaration : | local_declaration scoped_var_declaration ; statement_list : | statement_list statement ; expression_stmt : expression ";" | ";" ; selection_stmt : "if" "(" simple_expression ")" statement | "if" "(" simple_expression ")" statement "else" statement ; iteration_stmt: "while" "(" simple_expression ")" statement ; return_stmt : "return" ";" | "return" expression ; break_stmt : "break" ;   expression : mutable assign expression | mutable einc expression | mutable edec expression | mutable inc | mutable dec | simple_expression ;  simple_expression: simple_expression or and_expression | and_expression ;   and_expression: and_expression , unary_rel_expression | unary_rel_expression ;  unary_rel_expression: "!" unary_rel_expression | rel_expression ;  rel_expression : sum_expression relop sum_expression | sum_expression ;  relop: "<" | ">" | le | ge | comp_op | ne ;  sum_expression : sum_expression sumop term | term ;   sumop : add | sub ;  term: term mulop unary_expression | unary_expression ;  mulop: mult | div | rem ;  unary_expression : unaryop unary_expression | factor ;  unaryop : "-" | "*" ;  factor : immutable | mutable ;  mutable : id | id "[" expression "]" ;  immutable : "(" expression ")" | call | constant ;   call: id "(" args ")" ;  args:  | arg_list;  arg_list : arg_list","expression | expression ;  constant : int_num | stringconst | charconst | 'true' | 'false' ; 

i 2 shift/reduce @

state 38 conflicts: 1 shift/reduce state 139 conflicts: 1 shift/reduce

the specific states :

state 38     81 mutable: id .  [$end, add, sub, div, mult, comp_op, int, char, charconst, stringconst, ge, le, ne, einc, edec, inc, dec, and, or, rem, assign, int_num, id, ",", "]", "(", ")", ";", "{", "}", "if", "else", "while", "return", "break", "!", "<", ">", "-", "*", 't', 'f']    82        | id . "[" expression "]"    86 call: id . "(" args ")"      "["  shift, , go state 77     "("  shift, , go state 78      "("       [reduce using rule 81 (mutable)]     $default  reduce using rule 81 (mutable)     state 139     40 selection_stmt: "if" "(" simple_expression ")" statement .  [$end, int, char, charconst, stringconst, int_num, id, "(", ";", "{", "}", "if", "else", "while", "return", "break", "!", "-", "*", 't', 'f']    41               | "if" "(" simple_expression ")" statement . "else" statement      "else"  shift, , go state 141      "else"    [reduce using rule 40 (selection_stmt)]     $default  reduce using rule 40 (selection_stmt) 

could please explain how fix error, know has precedence.

the shift-reduce conflict in state 38 result of following production:

return_stmt : "return" ";"             | "return" expression             ; 

note production allows statement end expression. other production, statements must end either ; or }. if statement can end expression, grammar becomes ambiguous. consider, example:

return (1+1); 

which return_stmt (returning value of a) followed expression_stmt, or single return_stmt, returning value of function call a(1+1).

most likely, typo in grammar, , intended:

 return_stmt : "return" ";"             | "return" expression ";"             ; 

(but see note below quotes.)

---

the shift-reduce conflict @ state 139 classic c-style if conflict, result of ambiguity in language:

if (c1) if(c2) s1; else s2; 

which if else apply to? of course, expect inner if, sensible answer (because when we're looking @ else have no idea whether or not there else following), grammar allows either.

bison right thing in case, can see. (it chooses shift else, means not reduce inner if without else.) consequently, simplest possible solution ignore particular shift-reduce conflict. (see %expect directive.)

if doesn't appeal you, have 2 alternatives: 1 use precedence declarations explicitly give priority shift , other more explicit in grammar, in order make correct parse mandatory. both of these possibilities explored in 2 answers this question, featuring remarkably similar grammar. (to see precedence solution, have follow link in akim's answer.)

---

if using bison, should aware "word" , 'x' different syntaxes. first 1 uses token has been given human readable name, using declaration this:

%token token_return "return" 

you need all-caps enumeration name scanner, can write (assuming scanner written in flex):

"return" { return token_return; } 

but grammar more readable quoted strings. (for example, einc mean in language? have no idea...)

if don't declare enumeration name token, bison won't complain, , still assign code number token, more difficult figure out code number is.

on other hand, '(' represents single character token, code number ascii code character. (so corresponds usage of ( in c.) in case, code number known, , write in flex:

"(" { return '('; } 

although better off doing fall rule:

 . { return yytext[0]; } 

in short, want change uses of, example, ";" ';', , change 'true' , 'false' "true" , "false". , might want replace of other keyword tokens "le" , "inc" "<=" , "++", adding appropriate %token declarations double-quoted tokens.